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 On Tue, Feb 16, 2010 at 9:17 AM, Joerg Arndt <arndt@jjj.de> wrote:
[a homework question]
The following method is straightforward (from my thesis (and from my own brain)):
--------------------- An algorithm for generating a random object $x$ where $x \in U \subset V$ ($U$ is the subset of all objects in $V$ that have a required property) is as follows.
1) Generate a random object $x \in V$. 2) If $x \in U$ then return it ($x$ is of the required type). 3) Go to step 1. ---------------------
Now I have been asked (by one examiner) for a reference for this method, but surprisingly I cannot find anything.
So trivial no one ever bothered to write down?
Anyone?
Btw. I call this thing the "rejection method".
The example (square in a circle) at the bottom of the page http://en.wikipedia.org/wiki/Rejection_sampling would suggest that my algorithm is a special case of what is described on this page. However, I cannot see how it can be specialised from the Algorithm given just above it.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun