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

is "See exercise 18;" it's at about this point that my math

starts to sputter and wheeze.

--

(E-Mail Removed)