Good binary PRNG

R

Rod Pemberton

Keith Thompson said:
Then please interpret the phrase "consistently get more heads than
tails" so as to make my statement correct. :cool:}

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.


Rod Pemberton
 
R

Rod Pemberton

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 :)

What happens to the split you try a larger sample size? say 1Million versus
100,000?


Rod Pemberton
 
E

Eric Sosman

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 :)

Note that the method you are using (that is, extracting
just the low-order bit of each pseudo-random variate) is known
to expose a vulnerability shared by many PRNG's. In a linear
congruential PRNG of maximum period, the lower-order bits are
"less random" than the higher-order bits -- so when you isolate
the lowest-order bit of all, you're using the "least random"
part of the sequence of numbers. (This particular weakness is
not shared by all PRNG's, nor even by all linear congruential
PRNGs, and may or may not be a problem for your prng() function;
you didn't show us how it was implemented. Still, maximum-
period linear congruential PRNG's are common, so the wise
programmer tries to let the higher-order bits influence the
behavior of his program.)
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.

See Richard Heathfield's post for a description of how to
"de-bias" a biased source. (The method is not new; ISTR it was
originally devised by John von Neumann.)
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.

A source of random bits is not necessarily a good source
of random multi-bits. Quoth Knuth:

"Caution: Several people have been trapped into
believing that [R.C. Tausworthe's random bit
generator] can be used to generate random whole-
word fractions [...] but it is actually a poor
source of random fractions, even though the bits
are individually quite random! (See exercise 18.)"

-- "The Art of Computer Programming, Volume II:
Seminumerical Algorithms," section 3.2.2.

If you want to learn more, I'm afraid all I can suggest
is "See exercise 18;" it's at about this point that my math
starts to sputter and wheeze.
 
K

Keith Thompson

Rod Pemberton said:
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".
 
R

Richard Heathfield

Rod Pemberton said:
Apparently you are trying to say "the coin's probability is biased."

That's unlikely, since Keith is well aware that coins don't possess
probability.
 
R

Rod Pemberton

Richard Heathfield said:
Rod Pemberton said:


That's unlikely, since Keith is well aware that coins don't possess
probability.

And, so am I. Do you comprehend what is written? I know from past posts
you have difficulty in this area and you seem to be expressing the exact
same difficulty now. It's like you are translating from English to another
language and losing something in the translation. In the English language,
my statement above can be rewritten as "the probability of the coin is
biased" without any change in meaning.


Rod Pemberton
 
P

pinkfloydhomer

Eric said:
A source of random bits is not necessarily a good source
of random multi-bits. Quoth Knuth:

"Caution: Several people have been trapped into
believing that [R.C. Tausworthe's random bit
generator] can be used to generate random whole-
word fractions [...] but it is actually a poor
source of random fractions, even though the bits
are individually quite random! (See exercise 18.)"

-- "The Art of Computer Programming, Volume II:
Seminumerical Algorithms," section 3.2.2.

Hmm. This is interesting and counterintuitive. Does anyone have a
"simple" explanation why choosing random bits and stringing them
together wont make a random word??

/David
 
E

Eric Sosman

Eric said:
A source of random bits is not necessarily a good source
of random multi-bits. Quoth Knuth:

"Caution: Several people have been trapped into
believing that [R.C. Tausworthe's random bit
generator] can be used to generate random whole-
word fractions [...] but it is actually a poor
source of random fractions, even though the bits
are individually quite random! (See exercise 18.)"

-- "The Art of Computer Programming, Volume II:
Seminumerical Algorithms," section 3.2.2.


Hmm. This is interesting and counterintuitive. Does anyone have a
"simple" explanation why choosing random bits and stringing them
together wont make a random word??

"See exercise 18," and decide for yourself whether
it qualifies as "simple." (Knuth gives it an M22 rating,
meaning that it requires some mathematical sophistication
but should only take about half an hour to solve.)

This thread was only marginally topical for comp.lang.c
to begin with, and has become less so. Further discussion
probably belongs elsewhere, unless and until C-related
questions crop up again. comp.programming, perhaps.
 
R

Richard Heathfield

Rod Pemberton said:
And, so am I.

You have not succeeded in demonstrating this.
Do you comprehend what is written?

Yes, but you appear not to comprehend what you yourself write.
I know from past posts
you have difficulty in this area

No, what we have seen from past posts is that you mistakenly think I have
difficulty in this area.

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

Keith Thompson

Rod Pemberton said:
Keith Thompson said:
Rod Pemberton said:
news:[email protected]... [...]
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.
 
C

CBFalconer

Richard said:
Rod Pemberton said:
.... snip ...


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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top