Velocity Reviews > Good binary PRNG

# Good binary PRNG

Rod Pemberton
Guest
Posts: n/a

 05-18-2006

"Keith Thompson" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> 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

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

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

Rod Pemberton
Guest
Posts: n/a

 05-18-2006

<(E-Mail Removed)> wrote in message
news:(E-Mail Removed) oups.com...
> 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

Eric Sosman
Guest
Posts: n/a

 05-18-2006

http://www.velocityreviews.com/forums/(E-Mail Removed) wrote On 05/18/06 16:27,:
> 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
starts to sputter and wheeze.

--
(E-Mail Removed)

Keith Thompson
Guest
Posts: n/a

 05-18-2006
"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".

--
Keith Thompson (The_Other_Keith) (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.

Rod Pemberton
Guest
Posts: n/a

 05-19-2006

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

Rod Pemberton

Richard Heathfield
Guest
Posts: n/a

 05-19-2006
Rod Pemberton said:

> "Keith Thompson" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...
>>
>> Apparently you missed the word "probably".

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

--
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-19-2006

"Richard Heathfield" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> Rod Pemberton said:
>
> > "Keith Thompson" <(E-Mail Removed)> wrote in message
> > news:(E-Mail Removed)...
> >>
> >> Apparently you missed the word "probably".

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

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

pinkfloydhomer@gmail.com
Guest
Posts: n/a

 05-19-2006
Eric Sosman wrote:
>
> 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

Eric Sosman
Guest
Posts: n/a

 05-19-2006

(E-Mail Removed) wrote On 05/19/06 14:55,:
> Eric Sosman wrote:
>
>> 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.

--
(E-Mail Removed)

Richard Heathfield
Guest
Posts: n/a

 05-19-2006
Rod Pemberton said:

>
> "Richard Heathfield" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...
>> Rod Pemberton said:
>>
>> > "Keith Thompson" <(E-Mail Removed)> wrote in message
>> > news:(E-Mail Removed)...
>> >>
>> >> Apparently you missed the word "probably".
>> >
>> > 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.

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

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

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