Velocity Reviews > Good binary PRNG

# Good binary PRNG

Richard Heathfield
Guest
Posts: n/a

 05-18-2006
Keith Thompson said:

> Eric Sosman <(E-Mail Removed)> writes:
>
>> Flip a coin twice. If get something other than heads once
>> and tails once, do you conclude that the coin is biased?

>
> No, but if I consistently get more heads than tails, it probably is
> biased.

Not so. The "law of averages" does not work by evening out differences, but
by swamping them.

Coin-flipping is isomorphic to a random walk in one dimension. Start at 0.
If you toss heads, go right one step. If you toss tails, go left one step.
The most probable number of sign changes in a walk is actually 0. The next
most probable is 1, then 2, and so on. So consistently getting more heads
than tails does not necessarily, or even probably, mean that the coin is
biased.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

Jordan Abel
Guest
Posts: n/a

 05-18-2006
On 2006-05-18, pete <(E-Mail Removed)> wrote:
> Keith Thompson wrote:
>
>> If a single run of 100000 trials differs from a 50/50 split by a
>> fraction of a percent, it's not just harmless, it's expected. But if
>> N runs of 100000 are *consistently* over 50%, there's probably a
>> systematic error. (I'm deliberately leaving the value of N vague.)
>>
>> I suspect that the OP hasn't done enough runs to demonstrate an actual
>> bias, but I'm only guessing.
>>
>> [...]
>>
>> > Flip a coin twice. If get something other than heads once
>> > and tails once, do you conclude that the coin is biased?

>>
>> No, but if I consistently get more heads than tails, it probably is
>> biased.

>
> If you consistently get heads and tails alternating,
> that's not very good either.
>
> 1, 2300471611
> 0, 3253914372
> 1, 1858424313
> 0, 116628778
> 1, 2369750119
> 0, 3657615680
> 1, 2176380933
> 0, 894631110
> 1, 3876978771
> 0, 721092924

Consistently heads and tails alternating would be
2863311530
2863311530
2863311530
2863311530
2863311530
2863311530
2863311530
2863311530

Yours is more like
HTTTHTTHTTTHHHHTTHHTHTTHTTHHHTHH HHTTTTTHHHHHTTHTHHTTHTHHTTTTTHTT
THHTHHHTHHTTTHTHTHTTHHTHHHHHHTTH TTTTTHHTHHHHTTHHHTTHHHTHTTHTHTHT

It's hardly the algorithm's fault you're only taking every 32nd result.
It may be its fault that it's biased in such a pattern, but it wouldn't
be as noticeable if you wouldn't use it that way.

>
>
> /* BEGIN new.c */
>
> #include <stdio.h>
>
> #define LU_RAND(S) ((S) * 69069 + 362437 & 0XFFFFFFFFLU)
>
> int main(void)
> {
> long unsigned lu_seed = 12345678LU;
> int x;
>
> for (x = 0; x != 10; ++x) {
> lu_seed = LU_RAND(lu_seed);
> printf("%lu, %lu\n", lu_seed % 2, lu_seed);
> }
> return 0;
>}
>
> /* END new.c */
>

Jordan Abel
Guest
Posts: n/a

 05-18-2006
On 2006-05-18, Richard Heathfield <(E-Mail Removed)> wrote:
> Keith Thompson said:
>
>> Eric Sosman <(E-Mail Removed)> writes:
>>
>>> Flip a coin twice. If get something other than heads once
>>> and tails once, do you conclude that the coin is biased?

>>
>> No, but if I consistently get more heads than tails, it probably is
>> biased.

>
> Not so. The "law of averages" does not work by evening out differences, but
> by swamping them.
>
> Coin-flipping is isomorphic to a random walk in one dimension. Start at 0.
> If you toss heads, go right one step. If you toss tails, go left one step.
> The most probable number of sign changes in a walk is actually 0. The next
> most probable is 1, then 2, and so on. So consistently getting more heads
> than tails does not necessarily, or even probably, mean that the coin is
> biased.

But if you consistently get a particular _percentage_ more, it does.

[i.e. 501 in a trial run of 1000, 5032 in a trial run of 10000, 50290 in
a trial run of 1000000, etc] that _can_ be indicative of bias. So is an
average of 510 across a large number of independent runs of 1000. What
you're saying, i think, is that 510 in 1000, then a total of 5012 in
that and the next 9000, then a total of 50008 in that and the next
90000, doesn't indicate bias - and it doesn't. But that's not the only,
or even the most obvious, thing that "consistently getting more heads"
can mean.

[incidentally, you say the most probable number of sign changes is
actually 0 - that sounds a bit misleading - is 0 really more probable
than all other numbers of sign changes combined? What _is_ the
probability of there being 0 sign changes, in a random walk of arbitrary
length?]

Richard Heathfield
Guest
Posts: n/a

 05-18-2006
Jordan Abel said:

> On 2006-05-18, Richard Heathfield <(E-Mail Removed)> wrote:
>> So consistently getting
>> more heads than tails does not necessarily, or even probably, mean that
>> the coin is biased.

>
> But if you consistently get a particular _percentage_ more, it does.

Correct.

<snip>

> [incidentally, you say the most probable number of sign changes is
> actually 0 - that sounds a bit misleading - is 0 really more probable
> than all other numbers of sign changes combined?

I didn't mean to imply that, and I don't know whether or not it's true.

> What _is_ the
> probability of there being 0 sign changes, in a random walk of arbitrary
> length?]

Scary and hard to transcribe in text!

http://mathworld.wolfram.com/RandomW...mensional.html may help the more
mathematical amongst us (i.e. not me) to get a clue. Failing that, I can
probably lay my hands on a less scary formula, given a few days to plough
through all my Ian Stewarts...

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

Rod Pemberton
Guest
Posts: n/a

 05-18-2006

"pete" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> Keith Thompson wrote:
> >
> > "Rod Pemberton" <(E-Mail Removed)> writes:
> > [...]
> > > srand(NULL);

> >
> > srand(time(NULL));

>
> A cast would supress warnings that might be generated
> if time_t is higher ranking than unsigned.
>
> srand((unsigned)time(NULL));

True. srand(time(NULL)) was unintentionally dropped during an edit.

My original statements:

"Many PRNG's (Mersienne Twister, ISO C, etc.) seem to hit a binary "sweet
spot" after calling rand() about 7 million times."

won't apply when srand() is seeded correctly.

Rod Pemberton

Keith Thompson
Guest
Posts: n/a

 05-18-2006
Richard Heathfield <(E-Mail Removed)> writes:
> Keith Thompson said:
>> Eric Sosman <(E-Mail Removed)> writes:
>>> Flip a coin twice. If get something other than heads once
>>> and tails once, do you conclude that the coin is biased?

>>
>> No, but if I consistently get more heads than tails, it probably is
>> biased.

>
> Not so. The "law of averages" does not work by evening out differences, but
> by swamping them.
>
> Coin-flipping is isomorphic to a random walk in one dimension. Start at 0.
> If you toss heads, go right one step. If you toss tails, go left one step.
> The most probable number of sign changes in a walk is actually 0. The next
> most probable is 1, then 2, and so on. So consistently getting more heads
> than tails does not necessarily, or even probably, mean that the coin is
> biased.

tails" so as to make my statement correct. }

For example, if I do multiple runs of 100000 flips, and I consistently
get (even just slightly) more heads than tails on each run, the coin
is probably biased.

--
Keith Thompson (The_Other_Keith) http://www.velocityreviews.com/forums/(E-Mail Removed) <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

Richard Heathfield
Guest
Posts: n/a

 05-18-2006
Keith Thompson said:

> Richard Heathfield <(E-Mail Removed)> writes:
>> So consistently getting
>> more heads than tails does not necessarily, or even probably, mean that
>> the coin is biased.

>
> tails" so as to make my statement correct. }

Righty-ho, squire - re-interpreting now...

Oh gosh yes, you're right, aren't you?

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

pinkfloydhomer@gmail.com
Guest
Posts: n/a

 05-18-2006
The problems is not that I don't get exactly 50/50 (which would be
improbable), but that the skew is _always_ towards the 0's, no matter
what seed I use. I need a PRNG that at least biases 0's and 1's
equally. That is, the number of runs where 0's win vs the number of
runs where 1's win should be 50/50 given enough runs

Let's say you had to make a _fair_ system that randomly chooses which
of two people should get a dollar on each run (the scenario might be
much more serious, making the fairness infinitely important). What
would you do? If your PRNG always slightly favors one, then it cannot
be called fair.

But on the other hand, it occurs to me, if we had a fair binary PRNG,
then we would have a perfect general PRNG since we could just string
the results of the binary PRNG together to make multibit words. And
since a perfect PRNG doesn't exist yet, neither does a solution to the
above problem, I guess.

/David

Ben Pfaff
Guest
Posts: n/a

 05-18-2006
"(E-Mail Removed)" <(E-Mail Removed)> writes:

> The problems is not that I don't get exactly 50/50 (which would be
> improbable), but that the skew is _always_ towards the 0's, no matter
> what seed I use. I need a PRNG that at least biases 0's and 1's
> equally. That is, the number of runs where 0's win vs the number of
> runs where 1's win should be 50/50 given enough runs

There's a PRNG that should have equal bias on my webpage:
http://benpfaff.org/writings/clc/random.html
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}

Richard Heathfield
Guest
Posts: n/a

 05-18-2006
(E-Mail Removed) said:

> The problems is not that I don't get exactly 50/50 (which would be
> improbable), but that the skew is _always_ towards the 0's, no matter
> what seed I use. I need a PRNG that at least biases 0's and 1's
> equally. That is, the number of runs where 0's win vs the number of
> runs where 1's win should be 50/50 given enough runs

Oh, that's easy to fix. To toss an unfair coin fairly: let p be the
probability that you get heads, and q the probability that you get tails.

Probability of HH = p * p
Probability of HT = p * q
Probability of TH = q * p
Probability of TT = q * q

But q = 1 - p, so:

Probability of HH = p^2
Probability of HT = p * (1 - p) = p - p^2
Probability of TH = (1 - p) * p = p - p^2
Probability of TT = (1 - p) * (1 - p) = 1 - 2p + p^2

Note that the probability of HT and the probability of TH are equal, despite
p not necessarily equalling q. So if you get HT or TH, call the first of
them heads and the second tails. If you get anything else, discard the two
tosses, and toss again.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)