There are lots of variations of rejection sampling. In particular if it happens that the measures on the two spaces are different then usually another independent random variable is used to "correct" it. The one thing that's necessary is that the target measure is absolutely continuous with respect to the other. So if U is the target space and V is space that you can easily generate random elements of, and you know a function f with values in [0,1], so that the V probability of S a subset of U is integral_S f(x) d mu(x), where mu(x) is the measure on U, So pick x at random with respect to mu, then evaluate f(x) and accept x by generating a random y in [0,1] and accepting if f(x) <= y. Victor On Tue, Feb 16, 2010 at 4:41 PM, Allan Wechsler <acwacw@gmail.com> wrote:
Something is troubling me about this. You might say it gives me measure-heebie-jeebies.
Obviously it works fine when the spaces being sampled are finite.
When the spaces are infinite, however, there needs to be a something-or-other -- a measure? a sigma-algebra? -- in order for it to be well-defined to sample the larger space. Furthermore, the measure of the small space in the big space has to be biggish to make the algorithm efficient. (You don't want to have to sample the big space a trillion times to get one hit in the small space.)
The thing that is really bothering me, though, is the fear that although the small space might be a subset of the big one, the natural measures on the two might disagree, so that evenly-distributed samples of the big space might map into unevenly-distributed samples of the small. Perhaps somebody can convince me that this failure mode never occurs in practice. Or perhaps somebody can tell me that I've gone wrong much earlier in my thinking.
On Tue, Feb 16, 2010 at 4:30 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
My first reaction was that this all seemed rather trivial --- closer inspection reveals interesting and useful stuff here, that ought to be more widely known about! WFL
On 2/16/10, Joerg Arndt <arndt@jjj.de> wrote:
Thanks a lot!
I cannot access neither the Neumann paper nor Knuth's TAOCP (because these are on some ship following me to Europe).
So I'll just cite Neumann (first time citing a paper I haven't actually seen 8-) )
* Victor Miller <victorsmiller@gmail.com> [Feb 16. 2010 19:03]:
Joerg, I think that the reference given in that page (which is also in > von Neumann's collected works) J. von Neumann, "Various techniques > used in connection with random digits. Monte Carlo methods", Nat. > Bureau Standards, 12 (1951), pp. 36–38. > > is what you want. For example, Knuth if TAOCP vol. 2 page 120 > referers to it (but surprisingly for Knuth doesn't give the exact > reference). > > Victor >
[...]
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun