Re: Deterministic Algorithm for Random Number Generation Using Coin Flips


"david bandel" <sharpnova@xxxxxxxxx> wrote in message
news:7c1b5b4d-0919-4c53-b4e4-08db3f115cdf@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
On Jun 25, 2:40 am, Ray Vickson <rgvick...@xxxxxxxxx> wrote:
On Jun 25, 12:24 am, david bandel <sharpn...@xxxxxxxxx> wrote:



Or a subset of the general problem.

Is there some algorithm, using only coin flips (and assuming that the
coin only lands on either face with exactly 0.5 probability) to
generate an integer on the interval [1,3]. Such that:

-all three values have equal chance
-the algorithm can guarantee that there is 0 probability that the
algorithm will run forever.

For example, I could flip all three coins until they didn't all match.
At this point, the differing coin (be it coin #1, coin #2, or coin #3
(or assuming the coins were not labeled: toss #1, toss #2, or toss
#3) ) would correspond to our answer.

But whenever you toss the three coins there is a 1/4 chance that they
will all be the same.

If you toss them all n times, there will be a 1/4^n chance that they
all matched every toss. 1/4^n will never be 0 for a finite amount of
tosses.

I suspect that this algorithm does not exist. Would there be a way to
prove it?

Take a red coin and a green coin (each with P{heads} = 1/2) and toss
them independently. Outcomes are: {both H} --> 1, {red H, green T} -->
2, {red T, green H} --> 3, {both T} --> 4. If you get outcome 4,
reject the outcome and toss again. P{accept} = 3/4 on each trial, so P
{never accept} = 0. That is, with probability 1 you will "accept" a
result, and when you do it is equally likely to be 1, 2 or 3. (This is
actually an standard methodology in simulation, known as the
"rejection method(ology)".) Of course, the method does not have any
finite bound on the number of trials before acceptance, but the
expected number of trials needed = 4/3. The probability of not getting
an acceptance in n trials is (1/4)^n; for n = 10 this is .
9536743164e-6 while for n = 20 it is .9094947018e-12. Again: the
probability of never getting an acceptance = 0, just as you wanted.

R.G. Vickson

Uhm... no. That's exactly equivelant to the algorithm I suggested. And
as you copied from my post, the chance of it failing is 1/4 everytime.

Does anyone have any idea for a [1,3] algorithm using a [1,2]
generator that is guaranteed to terminate after finite throws?

And please R.G. Vickson, don't reply again. That was disgusting and
annoying.

--- For psuedorandom generators it would be gauranteed to work in a finite
amount of time. If not the psuedo-random generator would be neither psuedo
nor random as it would have the same output for every throw. Since
ultimately every prng is periodic it would mean that it would be constant.
Since prng's are obviously not constant you'll get what you want if using a
computer.

After all, eventually the probability of getting such a long string of
tails(in the given algorithm above) is 1/4^n and 1/4^n will eventually be
below the precision of any computer it will become 0. Hence for a finite
precision rng one will never get arbitrarily long constant outputs after a
certain point. (again, it's impossible because the probability will
ultimately be 0)

So, for all practical purposes Vickson's "algorithm" works. Theoretically it
won't... although it is really a bit of a grey field because if you did get
such a string of tails that made it not work and it was infinite then would
the rng be random? I think not so his argument does work.

Hence we should say that all arbitrarily long constant output's of an rng
must be finite... or by definition the rng is not an rng.


.

Loading