 |
|
| Science Forum Index » Statistics - Math Forum » Use of random bits... |
|
Page 2 of 2 Goto page Previous 1, 2 |
|
| Author |
Message |
| Scott Hemphill... |
 Posted: Sat Oct 24, 2009 8:54 am |
|
|
|
Guest
|
Ray Koopman <koopman at (no spam) sfu.ca> writes:
[quote]On Oct 22, 12:10 pm, Mok-Kong Shen <mok-kong.s... at (no spam) t-online.de> wrote:
[...] I have in the mean time a little discussion with my
acquaintances and we came up with the idea of utilizing the
(in the above scheme) discarded bits as follows: Save these
in a queue and use them when later one needs random numbers
in situations other than those for ranges that need exactly
k bits. (This is typically the case with Algorithm P in Knuth's
book, where one needs first to employ k bits a number of times
and later k-1 bits, etc.) Is this principally o.k. or not?
Thanks,
M. K. Shen
Even if the bits in the original stream are i.i.d. Bernoulli(1/2),
the saved bits will not be.
However, here is one way in which you can cut down on the number of
bits you use. Suppose you want a random value in the interval
[0,719], which requires ten bits. Instead of taking ten bits from the
stream all at once and then checking to see if the number is in range,
take bits from the stream one at a time and compare them to the binary
representation -- in this case, 1011001111 -- as they are taken.
If the first bit is 0 then you can take nine more without checking.
Otherwise if the second bit is 1 then the number will be too big;
start over. Otherwise if the third bit is 0 then you can take seven
more without checking. Otherwise if the fourth bit is 0 then you can
take six more without checking. Otherwise if the fifth bit is 1 then
the number will be too big; start over. Etc. When you do have to start
over, you can't do anything with the bits you've checked, but at least
you won't be throwing away as many as you would if you generated all
k bits before checking.
[/quote]
The expected number of bits used in generating a random number between
0 and 719 using this "partial rejection" method is 166/15 ~= 11.0667.
The "interval" method I described in an earlier post would use 91/8 =
11.375.
For a choice among m numbers (m=720 in this case) the partial
rejection method's worst case is bounded by log2(m)+4. The worst
cases are all of the form m=2^j+1. My interval method is bounded by
log2(m)+2, but most m's fit the bound closely, while your partial
rejection method uses numbers of bits that are more evenly
distributed between log2(m)+0 and log2(m)+4. In each interval between
2^j and 2^(j+1), the interval method uses fewer bits for the first
third of the numbers and the partial rejection method uses fewer bits
for the last two-thirds. So, depending on where you stop counting,
the partial rejection method outperforms the interval method one-half
to two-thirds of the time. (The tallies of wins and losses are
exactly equal if you count from m = 1 to floor(4/3*2^j).)
The advantage of the interval method, and the reason I came up with it
is to retain partial bit information between calls, so as to achieve
log2(m)+0 performance over the long run. For example, if a second
random number with m=720 is required, the interval method needs only
1229/128 = 9.60156 bits, using the leftover state from the first call.
Of course, if you knew that you wanted two numbers with m=720, you
could just have well used partial rejection with m=720^2, and you
would win by almost two bits (19.0884 compared with 20.9766). My
method is only an advantage if you don't know ahead of time what m's
you want. My method does not save you from having to use arbitrary
precision arithmetic on similar sized numbers. In fact, you need
arbitrary precision arithmetic for even small m's given the unbounded
nature of my inner loop.
Scott
--
Scott Hemphill hemphill at (no spam) alumni.caltech.edu
"This isn't flying. This is falling, with style." -- Buzz Lightyear |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Fri Dec 11, 2009 12:23 pm
|
|