At 05:48 PM 11/6/2000, Fitzpatrick, Joe wrote:
>I'm not sure that I see the difference. Taking 0x7FFF as an example, and
>assuming a true random value (not the case, but assuming...) the values 0-67
>are slightly more likely than 68-99 since, as you mention, the max is not
>evenly divisible.
While pseudo random generators aren't truly random, they do at least have a perfectly
uniform probability of generating all possible values, since they just cycle through
them all in some order.
>However, I don't see how truncating and retrying as you describe will
>correct this. Retrying if you are greater than 100 will not clip off the
>extra occurrence of 0-67, since they will pass the test and be included as
>legal values. It seems that 68-99 would continue to appear 0x7F times, but
>0-67 0x80 times over the range.
>
>I suppose if you are worried about the extra probability you could retry
>whenever the value is greater than 32700, then modulo. Personally, I don't
>worry about it, since the probability error in the random function itself is
>already pretty high.
I agree that this may not be a problem in practice, especially if you want random
numbers in a fairly small range, such as for rolling dice. The larger the modulo, the
worse the distribution gets. For a modulo of 32767, the worst possible case, the
probability of a zero would be twice that of every other outcome.
Now, for my proposed solution. First, I mask off the bits I don't need. The idea is
that if I take a subset of the bits, these will be uniformly random (all values
equally likely). For example, to get a value from 0 to 99, you'd mask off bits to get
a uniform random number between 0 and 127. Since the original generator generated all
values between 0 and 32767 exactly once before repeating, the masked values between 0
and 127 will each be generated exactly 8 times each before repeating. So, it is indeed
uniform. Now, if I throw away those values > 127, I should have a uniform distribution
for the remaining values because they all occur equally often. My probability theory
is pretty rusty, so maybe I'm confused.
--
Peter Epstein
Palm Inc. Developer
--
For information on using the Palm Developer Forums, or to unsubscribe, please see
http://www.palmos.com/dev/tech/support/forums/
