Velocity Reviews > Good binary PRNG

# Good binary PRNG

Keith Thompson
Guest
Posts: n/a

 05-19-2006
"Rod Pemberton" <(E-Mail Removed)> writes:
> "Keith Thompson" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...
>> "Rod Pemberton" <(E-Mail Removed)> writes:
>> > "Keith Thompson" <(E-Mail Removed)> wrote in message
>> > news:(E-Mail Removed)...

>> [...]
>> >> 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.
>> >
>> > No. You could get all heads (or tails) with an unbiased coin.
>> > It's possible, but the probability of all heads (or tails) is
>> > extremely low. The probability of half-heads/half-tails is much
>> > higher by comparison.

>>
>> Apparently you missed the word "probably".

>
> Apparently you are trying to say "the coin's probability is biased."

Just in case anyone other than Mr. Pemberton is having trouble with
this, I'll explain further.

I meant exactly what I wrote. Mr. Pemberton's reply, the paragraph
quoted above beginning with "No. You could get all heads", would have
been perfectly correct if the word "No" had been replaced with "Yes".

You can't actually judge the exact probability that a coin is biased
just by observing its behavior. Another factor in that calculation is
the *a priori* probability that it's biased. If I flip a coin 10
times, there's a 1.0/1024.0 probability that I'll get heads 10 times
in a row *if the coin is unbiased*. If I was certain beyond
reasonable doubt before I started that the coin is unbiased, I'll
assume with high probability that it's a coincidence. If I grabbed
the coin from a bag containing 50 unbiased coins and 50 coins with
double heads, I'll assume with high probability that the coin is
biased, though there's still a non-zero probability that it isn't.
(I'm ignoring factors other than the coin that could lead to bias; for
example, some people can flip a fair coin and control how it lands.)

Consider a single run of 100000 flips. Assuming an unbiased coin,
there's a small probability of an even 50000/50000 split, a
probability of just under 50% of more tails than heads, and an equal
probability just under 50% of more heads than tails.

If I perform 1000 such runs (that's 100 million flips), I should
expect to get more heads than tails approximately 500 times, and more
tails than heads approximately 500 times. Each run, if I look only at
whether I got more heads or tails, acts very much like a single flip,
with the added small possibility of an even split. (That could be
eliminated by doing an odd number of flips on each run.) Assuming an
unbiased coin, the probability of getting (even slightly) more heads
than tails on *every one* of the 1000 runs is less than 1.0/2.0**1000
("less than" because of the small probability of an even split on some
runs). If there's any possibility at all that the coin could have
been biased, this observation leads to the conclusion that it almost
certainly *is* biased. (If, instead of flipping a coin, I'm observing
some physical phenomenon that theoretically gives me completely random
0/1 values, and I see this kind of result, it's almost certain that
something is wrong with either the experiment or the theory.)

If, rather than seeing more heads than tails on every run, I see more
heads than tails on significantly more runs than would be expected by
random chance, then the coin is *probably* biased. Which is what I
said in the first place. (What constitutes "significantly more runs"
depends to some extent on how much I trust the coin in the first
place.)

The quality of a pseudo-random number generator can be judged, in
part, by how closely it obeys these rules -- but of course observation
can never give 100% confidence. With pseudo-random number generators,
we have the advantage of being able to analyze the algorithm itself.

--
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.

CBFalconer
Guest
Posts: n/a

 05-19-2006
Richard Heathfield wrote:
> Rod Pemberton said:
>

.... snip ...
>
>> In the English language, my statement above can be rewritten as
>> "the probability of the coin is biased" without any change in meaning.

>
> Indeed it can - and when it is rewritten in that way, without any
> change in meaning, it repeats your previous error of assigning a
> probability to the coin itself.
>
> What you may have intended to say is that there exists a significant
> probability that the coin is biased. But this is not what you did in
> fact say.

--
+-------------------+ .:\:\:/:/:.
| PLEASE DO NOT F :.:\:\:/:/:.:
| FEED THE TROLLS | :=.' - - '.=:
| | '=(\ 9 9 /)='
| Thank you, | ( (_) )
| Management | /`-vvv-'\
+-------------------+ / \
| | @@@ / /|,,,,,|\ \
| | @@@ /_// /^\ \\_\
@x@@x@ | | |/ WW( ( ) )WW
\||||/ | | \| __\,,\ /,,/__
\||/ | | | jgs (______Y______)
/\/\/\/\/\/\/\/\//\/\\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
================================================== ============

fix (vb.): 1. to paper over, obscure, hide from public view; 2.
to work around, in a way that produces unintended consequences
that are worse than the original problem. Usage: "Windows ME
fixes many of the shortcomings of Windows 98 SE". - Hutchison