cipher@mmm.UUCP (Andre Guirard) (11/16/85)
In article <787@mhuxt.UUCP> js2j@mhuxt.UUCP (sonntag) writes: >> This isn't quite the answer yet. For one thing, I doubt it's >> uniformly distributed. Also, this answer is from 0 to infinity, and >> I'm looking for negative infinity to positive infinity. > > Now he tells us that it's got to be uniformly distributed? If such >a function exists, the probability of it generating a number between any >two arbitrarily large, but finite limits is exactly 0! Why would ^^^^^^^^^ >anyone want a random number generator like that? Not zero, since the random number generator will in fact come up with a number. The chances are infinitesimal. The difference is admittedly very subtle. How would you implement such an algorithm if you had it? Where would you store the result? You would have to use a "Celestial 360". If you had a generator for integers in the range 0 to infinity, you could extend it to -infinity to infinity or any other enumerable set of size aleph-null by some transformation. For instance, if RAND is from zero to infinity, then: TEMP <- RAND(OLD) IF TEMP/2 = TRUNC(TEMP/2) THEN NEW = TEMP/2 ELSE NEW = -1 * ((TEMP+1)/2) is from -infinity to infinity. How would you establish that the distribution was even? This worries me. I assume one would wish that there should be no relation in the size of the input or "seed" of the random-number generator and the size of the result, that is that there does not exist any function f(x):N -> N s.t. (f(x) >= RAND(x) for all x). Unfortunately this is not possible since RAND(x) is itself a function on N, and thus furnishes an upper bound on the size of the result. If you don't care about "connectedness" between the seed and the result, I suggest the following: procedure RAND(x) return (x+1) There is another possible algorithm, but this one requires a time-recursive computing environment as well as infinite storage. A time-recursive language has the added function WAIT (which waits for a message from the future in the form of an element of N) and SEND(x) statement which sends the value x back to the last WAIT function executed. Then the following program: RAND () integer x x = WAIT() SEND(x) should generate a random number. But beware of the similar program: SIMILAR() integer x x = WAIT() SEND(x+1) which will or course crash the system. -- /''`\ Andre Guirard ([]-[]) De Tuss from de Tonn \ o / ihnp4!mmm!cipher `-'
ags@pucc-h (Dave Seaman) (11/17/85)
In article <321@mmm.UUCP> cipher@mmm.UUCP (Andre Guirard) writes: >In article <787@mhuxt.UUCP> js2j@mhuxt.UUCP (sonntag) writes: >>> This isn't quite the answer yet. For one thing, I doubt it's >>> uniformly distributed. Also, this answer is from 0 to infinity, and >>> I'm looking for negative infinity to positive infinity. >> >> Now he tells us that it's got to be uniformly distributed? If such >>a function exists, the probability of it generating a number between any >>two arbitrarily large, but finite limits is exactly 0! Why would > ^^^^^^^^^ >>anyone want a random number generator like that? > >Not zero, since the random number generator will in fact come up with a >number. The chances are infinitesimal. The difference is admittedly >very subtle. To say that an event has probability zero does not mean the event is impossible. Anle. Analogously, to say that a set has measure zero does not mean the set is empty. The Cantor set has uncountably many points in it, but its measure is zero. A uniformly-distributed random variable on the unit interval has probability zero of being in the Cantor set, though such an event is obviously possible. There is no such thing as an infinitesimal probability. -- Dave Seaman ..!pur-ee!pucc-h!ags