 |
|
| Science Forum Index » Statistics - Math Forum » Use of random bits... |
|
Page 1 of 2 Goto page 1, 2 Next |
|
| Author |
Message |
| Mok-Kong Shen... |
 Posted: Wed Oct 21, 2009 7:13 am |
|
|
|
Guest
|
Hi,
If one has a good sequence of random bits and desires random numbers
in [0,m-1], one could take k bits with 2^k >= m > 2^(k-1), discarding
them and taking another k bits, in case the number obtained is not in
the desired range. Is there perhaps a better procedure that economizes
the use of the given bits, since the bits discarded are in fact well
random?
Thanks,
M. K. Shen |
|
|
| Back to top |
|
|
|
| Gordon Sande... |
| Posted: Wed Oct 21, 2009 7:25 am |
|
|
|
Guest
|
On 2009-10-21 10:13:25 -0300, Mok-Kong Shen <mok-kong.shen at (no spam) t-online.de> said:
[quote]Hi,
If one has a good sequence of random bits and desires random numbers
in [0,m-1], one could take k bits with 2^k >= m > 2^(k-1), discarding
them and taking another k bits, in case the number obtained is not in
the desired range. Is there perhaps a better procedure that economizes
the use of the given bits, since the bits discarded are in fact well
random?
Thanks,
M. K. Shen
[/quote]
If you are just worrying about "complexity" issues then find r so that
r*m is closer to but still smaller than some 2^K. You can determine
r values mod m at once with higher rejection efficiency. It is good
for a complexity result but not very practical if you are waiting online.
Find a value mod r*m and then treat it as an r digit value in base m. |
|
|
| Back to top |
|
|
|
| Mok-Kong Shen... |
| Posted: Wed Oct 21, 2009 8:55 am |
|
|
|
Guest
|
Gordon Sande wrote:
[quote]Mok-Kong Shen <mok-kong.shen at (no spam) t-online.de
If one has a good sequence of random bits and desires random numbers
in [0,m-1], one could take k bits with 2^k >= m > 2^(k-1), discarding
them and taking another k bits, in case the number obtained is not in
the desired range. Is there perhaps a better procedure that economizes
the use of the given bits, since the bits discarded are in fact well
random?
If you are just worrying about "complexity" issues then find r so that
r*m is closer to but still smaller than some 2^K. You can determine
r values mod m at once with higher rejection efficiency. It is good
for a complexity result but not very practical if you are waiting online.
Find a value mod r*m and then treat it as an r digit value in base m.
[/quote]
The application I have in mind is the Algorithm P in Knuth's book
to obtain random permutations of n objects. It is assumed that a
good quality random bit sequence is available for generating the
random numbers needed in the algorithm. The question is whether
there is a highly optimal/economic way of practically utilizing the
given bit sequence.
Thanks,
M. K. Shen |
|
|
| Back to top |
|
|
|
| Gordon Sande... |
| Posted: Wed Oct 21, 2009 10:47 am |
|
|
|
Guest
|
On 2009-10-21 11:55:05 -0300, Mok-Kong Shen <mok-kong.shen at (no spam) t-online.de> said:
[quote]Gordon Sande wrote:
Mok-Kong Shen <mok-kong.shen at (no spam) t-online.de
If one has a good sequence of random bits and desires random numbers
in [0,m-1], one could take k bits with 2^k >= m > 2^(k-1), discarding
them and taking another k bits, in case the number obtained is not in
the desired range. Is there perhaps a better procedure that economizes
the use of the given bits, since the bits discarded are in fact well
random?
If you are just worrying about "complexity" issues then find r so that
r*m is closer to but still smaller than some 2^K. You can determine
r values mod m at once with higher rejection efficiency. It is good
for a complexity result but not very practical if you are waiting online.
Find a value mod r*m and then treat it as an r digit value in base m.
The application I have in mind is the Algorithm P in Knuth's book
to obtain random permutations of n objects. It is assumed that a
good quality random bit sequence is available for generating the
random numbers needed in the algorithm. The question is whether
there is a highly optimal/economic way of practically utilizing the
given bit sequence.
Thanks,
M. K. Shen
[/quote]
I think the point being made was that finding random permutations is
a rather demanding task as you are choosing 1 out of N! posibilities.
For a typical PRNG that translates into a very very long period and
good properties over that period. You would need a very very very good
bit generator to have an equivalent of the the very very long period.
It will be much harder to find a good bit generator than to find an
efficient way of using it. |
|
|
| Back to top |
|
|
|
| Art Kendall... |
| Posted: Wed Oct 21, 2009 1:00 pm |
|
|
|
Guest
|
If one just generates n random numbers, and sorts them, isn't the list a
random permutation of the n items?
SPSS syntax.
set seed = 20091021.
input program.
loop item = 1 to 10.
compute random_number = rv.uniform(0,2**31).
end case.
end loop.
end file.
end input program.
sort cases by random_number.
compute picked_order= $casenum.
formats item picked_order (f3).
list vars = item picked_order.item picked_order
the result with this seed is.
3 1
4 2
5 3
8 4
1 5
2 6
10 7
6 8
7 9
9 10
Art Kendall
Gordon Sande wrote:
[quote]On 2009-10-21 11:55:05 -0300, Mok-Kong Shen
mok-kong.shen at (no spam) t-online.de> said:
Gordon Sande wrote:
Mok-Kong Shen <mok-kong.shen at (no spam) t-online.de
If one has a good sequence of random bits and desires random numbers
in [0,m-1], one could take k bits with 2^k >= m > 2^(k-1), discarding
them and taking another k bits, in case the number obtained is not in
the desired range. Is there perhaps a better procedure that economizes
the use of the given bits, since the bits discarded are in fact well
random?
If you are just worrying about "complexity" issues then find r so that
r*m is closer to but still smaller than some 2^K. You can determine
r values mod m at once with higher rejection efficiency. It is good
for a complexity result but not very practical if you are waiting
online.
Find a value mod r*m and then treat it as an r digit value in base m.
The application I have in mind is the Algorithm P in Knuth's book
to obtain random permutations of n objects. It is assumed that a
good quality random bit sequence is available for generating the
random numbers needed in the algorithm. The question is whether
there is a highly optimal/economic way of practically utilizing the
given bit sequence.
Thanks,
M. K. Shen
I think the point being made was that finding random permutations is
a rather demanding task as you are choosing 1 out of N! posibilities.
For a typical PRNG that translates into a very very long period and
good properties over that period. You would need a very very very good
bit generator to have an equivalent of the the very very long period.
It will be much harder to find a good bit generator than to find an
efficient way of using it.
[/quote] |
|
|
| Back to top |
|
|
|
| Art Kendall... |
| Posted: Wed Oct 21, 2009 1:04 pm |
|
|
|
Guest
|
It seems that just about any stat package would do with you want
generating pseudorandom numbers.
here is an example.
If one just generates n random numbers, and sorts them, isn't the list a
random permutation of the n items?
SPSS syntax.
set seed = 20091021.
input program.
loop item = 1 to 10.
compute random_number = rv.uniform(0,2**31).
end case.
end loop.
end file.
end input program.
sort cases by random_number.
compute picked_order= $casenum.
formats item picked_order (f3).
list vars = item picked_order.item picked_order
the result with this seed is.
3 1
4 2
5 3
8 4
1 5
2 6
10 7
6 8
7 9
9 10
Art Kendall
Gordon Sande wrote:
[quote]On 2009-10-21 11:55:05 -0300, Mok-Kong Shen
mok-kong.shen at (no spam) t-online.de> said:
Gordon Sande wrote:
Mok-Kong Shen <mok-kong.shen at (no spam) t-online.de
If one has a good sequence of random bits and desires random numbers
in [0,m-1], one could take k bits with 2^k >= m > 2^(k-1), discarding
them and taking another k bits, in case the number obtained is not in
the desired range. Is there perhaps a better procedure that economizes
the use of the given bits, since the bits discarded are in fact well
random?
If you are just worrying about "complexity" issues then find r so that
r*m is closer to but still smaller than some 2^K. You can determine
r values mod m at once with higher rejection efficiency. It is good
for a complexity result but not very practical if you are waiting
online.
Find a value mod r*m and then treat it as an r digit value in base m.
The application I have in mind is the Algorithm P in Knuth's book
to obtain random permutations of n objects. It is assumed that a
good quality random bit sequence is available for generating the
random numbers needed in the algorithm. The question is whether
there is a highly optimal/economic way of practically utilizing the
given bit sequence.
Thanks,
M. K. Shen
I think the point being made was that finding random permutations is
a rather demanding task as you are choosing 1 out of N! posibilities.
For a typical PRNG that translates into a very very long period and
good properties over that period. You would need a very very very good
bit generator to have an equivalent of the the very very long period.
It will be much harder to find a good bit generator than to find an
efficient way of using it.
[/quote] |
|
|
| Back to top |
|
|
|
| Gordon Sande... |
| Posted: Wed Oct 21, 2009 1:17 pm |
|
|
|
Guest
|
On 2009-10-21 16:00:56 -0300, Art Kendall <Art at (no spam) DrKendall.org> said:
[quote]If one just generates n random numbers, and sorts them, isn't the list
a random permutation of the n items?
[/quote]
It will be a permutation but only if the random number generator is very good
will it be one chosen with equal probability from all permutations. The
number of
possible permutations grows very quickly and is soon much greater than the
cycle length of all but the most long period PRNGs. So only a few of
the possible
permutations will every be realized leaving many with zero probability
of being picked.
Shuffling cards well is MUCH harder than one expects because of the
growth in the
sizes of the counts involved.
A poor random number generator is quite OK for an amusing simulation of cards
for a children's game. But not for serous applications.
[quote]SPSS syntax.
set seed = 20091021.
input program.
loop item = 1 to 10.
compute random_number = rv.uniform(0,2**31).
end case.
end loop.
end file.
end input program.
sort cases by random_number.
compute picked_order= $casenum.
formats item picked_order (f3).
list vars = item picked_order.item picked_order
the result with this seed is.
3 1
4 2
5 3
8 4
1 5
2 6
10 7
6 8
7 9
9 10
Art Kendall
Gordon Sande wrote:
On 2009-10-21 11:55:05 -0300, Mok-Kong Shen <mok-kong.shen at (no spam) t-online.de> said:
Gordon Sande wrote:
Mok-Kong Shen <mok-kong.shen at (no spam) t-online.de
If one has a good sequence of random bits and desires random numbers
in [0,m-1], one could take k bits with 2^k >= m > 2^(k-1), discarding
them and taking another k bits, in case the number obtained is not in
the desired range. Is there perhaps a better procedure that economizes
the use of the given bits, since the bits discarded are in fact well
random?
If you are just worrying about "complexity" issues then find r so that
r*m is closer to but still smaller than some 2^K. You can determine
r values mod m at once with higher rejection efficiency. It is good
for a complexity result but not very practical if you are waiting online.
Find a value mod r*m and then treat it as an r digit value in base m.
The application I have in mind is the Algorithm P in Knuth's book
to obtain random permutations of n objects. It is assumed that a
good quality random bit sequence is available for generating the
random numbers needed in the algorithm. The question is whether
there is a highly optimal/economic way of practically utilizing the
given bit sequence.
Thanks,
M. K. Shen
I think the point being made was that finding random permutations is
a rather demanding task as you are choosing 1 out of N! posibilities.
For a typical PRNG that translates into a very very long period and
good properties over that period. You would need a very very very good
bit generator to have an equivalent of the the very very long period.
It will be much harder to find a good bit generator than to find an
efficient way of using it.[/quote] |
|
|
| Back to top |
|
|
|
| Art Kendall... |
| Posted: Wed Oct 21, 2009 1:50 pm |
|
|
|
Guest
|
Of course a lot depends on what the permutation will be used for. On the
other hand the Mersenne Twister Random Number Generator used e.g., in
SPSS, is considered a very good one for many purposes.
Matsumoto, M., and T. Nishimura. 1998. Mersenne Twister, A
623--dimensionally equidistributed uniform pseudorandom number
generator. /ACM Trans. on Modeling and Computer Simulation, /8:1, 3-30.
Matsumoto, M., and Y. Kurita. 1994. Twisted GFSR generators II. /ACM
Trans. on Modeling and Computer Simulation, /4:3, 254-266.
Art Kendall
Social Research Consultants
Gordon Sande wrote:
[quote]On 2009-10-21 16:00:56 -0300, Art Kendall <Art at (no spam) DrKendall.org> said:
If one just generates n random numbers, and sorts them, isn't the
list a random permutation of the n items?
It will be a permutation but only if the random number generator is
very good
will it be one chosen with equal probability from all permutations.
The number of
possible permutations grows very quickly and is soon much greater than
the
cycle length of all but the most long period PRNGs. So only a few of
the possible
permutations will every be realized leaving many with zero probability
of being picked.
Shuffling cards well is MUCH harder than one expects because of the
growth in the
sizes of the counts involved.
A poor random number generator is quite OK for an amusing simulation
of cards
for a children's game. But not for serous applications.
SPSS syntax.
set seed = 20091021.
input program.
loop item = 1 to 10.
compute random_number = rv.uniform(0,2**31).
end case.
end loop.
end file.
end input program.
sort cases by random_number.
compute picked_order= $casenum.
formats item picked_order (f3).
list vars = item picked_order.item picked_order
the result with this seed is.
3 1
4 2
5 3
8 4
1 5
2 6
10 7
6 8
7 9
9 10
Art Kendall
Gordon Sande wrote:
On 2009-10-21 11:55:05 -0300, Mok-Kong Shen
mok-kong.shen at (no spam) t-online.de> said:
Gordon Sande wrote:
Mok-Kong Shen <mok-kong.shen at (no spam) t-online.de
If one has a good sequence of random bits and desires random numbers
in [0,m-1], one could take k bits with 2^k >= m > 2^(k-1),
discarding
them and taking another k bits, in case the number obtained is
not in
the desired range. Is there perhaps a better procedure that
economizes
the use of the given bits, since the bits discarded are in fact well
random?
If you are just worrying about "complexity" issues then find r so
that
r*m is closer to but still smaller than some 2^K. You can determine
r values mod m at once with higher rejection efficiency. It is good
for a complexity result but not very practical if you are waiting
online.
Find a value mod r*m and then treat it as an r digit value in base m.
The application I have in mind is the Algorithm P in Knuth's book
to obtain random permutations of n objects. It is assumed that a
good quality random bit sequence is available for generating the
random numbers needed in the algorithm. The question is whether
there is a highly optimal/economic way of practically utilizing the
given bit sequence.
Thanks,
M. K. Shen
I think the point being made was that finding random permutations is
a rather demanding task as you are choosing 1 out of N! posibilities.
For a typical PRNG that translates into a very very long period and
good properties over that period. You would need a very very very good
bit generator to have an equivalent of the the very very long period.
It will be much harder to find a good bit generator than to find an
efficient way of using it.
[/quote] |
|
|
| Back to top |
|
|
|
| Mok-Kong Shen... |
| Posted: Wed Oct 21, 2009 2:15 pm |
|
|
|
Guest
|
Gordon Sande schrieb:
[quote]On 2009-10-21 11:55:05 -0300, Mok-Kong Shen <mok-kong.shen at (no spam) t-online.de
said:
Gordon Sande wrote:
Mok-Kong Shen <mok-kong.shen at (no spam) t-online.de
If one has a good sequence of random bits and desires random numbers
in [0,m-1], one could take k bits with 2^k >= m > 2^(k-1), discarding
them and taking another k bits, in case the number obtained is not in
the desired range. Is there perhaps a better procedure that economizes
the use of the given bits, since the bits discarded are in fact well
random?
If you are just worrying about "complexity" issues then find r so that
r*m is closer to but still smaller than some 2^K. You can determine
r values mod m at once with higher rejection efficiency. It is good
for a complexity result but not very practical if you are waiting
online.
Find a value mod r*m and then treat it as an r digit value in base m.
The application I have in mind is the Algorithm P in Knuth's book
to obtain random permutations of n objects. It is assumed that a
good quality random bit sequence is available for generating the
random numbers needed in the algorithm. The question is whether
there is a highly optimal/economic way of practically utilizing the
given bit sequence.
Thanks,
M. K. Shen
I think the point being made was that finding random permutations is
a rather demanding task as you are choosing 1 out of N! posibilities.
For a typical PRNG that translates into a very very long period and
good properties over that period. You would need a very very very good
bit generator to have an equivalent of the the very very long period.
It will be much harder to find a good bit generator than to find an
efficient way of using it.
[/quote] |
|
|
| Back to top |
|
|
|
| Mok-Kong Shen... |
| Posted: Wed Oct 21, 2009 2:20 pm |
|
|
|
Guest
|
Gordon Sande wrote:
[quote]I think the point being made was that finding random permutations is
a rather demanding task as you are choosing 1 out of N! posibilities.
For a typical PRNG that translates into a very very long period and
good properties over that period. You would need a very very very good
bit generator to have an equivalent of the the very very long period.
It will be much harder to find a good bit generator than to find an
efficient way of using it.
[/quote]
If I don't err, there have been since long hardware methods of
generating high quality random bits.
M. K. Shen |
|
|
| Back to top |
|
|
|
| Scott Hemphill... |
| Posted: Wed Oct 21, 2009 3:31 pm |
|
|
|
Guest
|
Mok-Kong Shen <mok-kong.shen at (no spam) t-online.de> writes:
[quote]Gordon Sande wrote:
Mok-Kong Shen <mok-kong.shen at (no spam) t-online.de
If one has a good sequence of random bits and desires random numbers
in [0,m-1], one could take k bits with 2^k >= m > 2^(k-1), discarding
them and taking another k bits, in case the number obtained is not in
the desired range. Is there perhaps a better procedure that economizes
the use of the given bits, since the bits discarded are in fact well
random?
If you are just worrying about "complexity" issues then find r so that
r*m is closer to but still smaller than some 2^K. You can determine
r values mod m at once with higher rejection efficiency. It is good
for a complexity result but not very practical if you are waiting online.
Find a value mod r*m and then treat it as an r digit value in base m.
The application I have in mind is the Algorithm P in Knuth's book
to obtain random permutations of n objects. It is assumed that a
good quality random bit sequence is available for generating the
random numbers needed in the algorithm. The question is whether
there is a highly optimal/economic way of practically utilizing the
given bit sequence.
[/quote]
OK, I'm taking a stab at the problem of minimizing the number of
random bits required:
Suppose you want a random number between 0 and k-1. With floating
point arithmetic, you would just use floor(k*drand()) and be done with
it. Here's an algorithm that calculates the same result with a random
bit sequence.
The idea is to construct an interval (a..b) which has the initial
value (0..k) and is subdivided every time we look at a random bit. If
we see a zero bit, we take the left half-interval, and if we see a one
bit, we take the right half-interval. This continues until (a..b)
lies entirely within one of the k intervals (0..1), (1..2), ...,
(k-1..k). We then return the left endpoint of the interval as our
random number.
Here's some pseudo-C code:
double a, b, mid;
int bit;
a = 0;
b = k;
while (floor(a) < ceiling(b-1)) {
mid = (a+b) / 2;
bit = randombit();
if (bit == 0) b = mid; else a = mid;
}
return floor(a);
(Implementation comments come later. :-)
So in principle, you could generate one random number "r" with k=n!
to select which permutation you want. Since the Fisher-Yates shuffle
(algorithm P in Knuth vol 2, section 3.4.2) wants a choice between n
items the first time through the loop, n-1 the second, etc., you could
peel these choices from r by taking r mod n the first time, and then
setting r = r / n (integer division). You could then choose among n-1
items by taking the new r mod (n-1), etc.
But if you didn't want to generate a random number with k=n!, but
instead wanted to generate one with k=n, another with k=n-1, etc. Can
you do this with out requiring any more random bits? The answer is
"yes", and here's how to do it with a smaller problem:
Suppose we want to generate random numbers with k=3. You might guess
that in the limit, it should only take log2(3)~=1.5849625 random bits
per number, and this would be right. The above routine takes an
average of 3 bits for k=3, an average of 5 bits for k=9 and an average
of 6.625 bits for k=27. So to get 3 random numbers with k=3 should
only take an average of 3 bits for the first number, 2 more bits for
the second, and 1.625 bits for the third.
Let's take k=3, and lets feed the random bits {1,0,0,...} into the
routine above:
a = 0, b = 3, mid = 1.5, bit = 1
a = 1.5, b = 3, mid = 2.25, bit = 0
a = 1.5, b = 2.25, mid = 1.875, bit = 0
a = 1.5, b = 1.875
And here the routine stops because the interval (a..b) is contained in
(1..2). It returns the value "1". Suppose we had been calculating a
random number with k=9 using the same random bits, and suppose we were
going to report the answer in base 3. All the values of a, b and mid
would be three times larger, so currently a=4.5 and b=5.625. Since
(a..b) is contained within (3..6) we can already report that the high
order trinary digit (trit?) is "1". To calculate the low order digit,
we can just subtract 3 from a and b, and continue the routine with the
interval (1.5..2.625). Equivalently, (back in the k=3 problem) we
could subtract the "1" we returned from the (1.5..1.875) interval,
getting (0.5..0.875) and then multiply the interval by three, getting
(1.5..2.625) as the starting conditions for calculating the second
random number.
Here's modified code which makes use of left over information in a and
b to calculate a random number between 0 and k-1.
static double a=0, b=1;
double mid;
int bit;
b = k * (b-floor(a));
a = k * (a-floor(a));
while (floor(a) < ceiling(b-1)) {
mid = (a+b) / 2;
bit = randombit();
if (bit == 0) b = mid; else a = mid;
}
return floor(a);
The "static" declaration in the above routine says that a and b retain
their values between subsequent calls to the routine, and the "a=0" and
"b=1" are the values that the variables have before the first call to
the routine.
Implementation details and pitfalls:
Notice how each time through the while loop, I had to use more decimal
places to give the exact values of a, b, and mid? The same thing
happens in binary, so after a few dozen times through the loop, the
results are no longer exact because the computer's floating point
representation doesn't have enough bits.
Also, the number of times through the loop is unbounded. If for k=3,
the random bit sequence is {1,0,1,0,1,0,...} then a and b both close
in on 2, but the the bit sequence has to depart the ...1,0,... pattern
before the algorithm can figure out on which side of the number 2 the
interval lies. It is true that the next random numbers may be very
cheap to calculate (they could require *no* random bits) but if a and
b were very close together, then there were very few bits representing
the difference between them, and the next random numbers could be
inaccurate.
You could make the results exact by implementing the algorithm with
arbitrary precision integer and/or rational arithmetic.
--
Scott Hemphill hemphill at (no spam) alumni.caltech.edu
"This isn't flying. This is falling, with style." -- Buzz Lightyear |
|
|
| Back to top |
|
|
|
| Scott Hemphill... |
| Posted: Thu Oct 22, 2009 5:57 am |
|
|
|
Guest
|
Scott Hemphill <hemphill at (no spam) hemphills.net> writes:
I have just a few followup comments.
[quote]Here's modified code which makes use of left over information in a and
b to calculate a random number between 0 and k-1.
static double a=0, b=1;
double mid;
int bit;
b = k * (b-floor(a));
a = k * (a-floor(a));
while (floor(a) < ceiling(b-1)) {
mid = (a+b) / 2;
bit = randombit();
if (bit == 0) b = mid; else a = mid;
}
return floor(a);
Also, the number of times through the loop is unbounded. If for k=3,
the random bit sequence is {1,0,1,0,1,0,...} then a and b both close
in on 2, but the the bit sequence has to depart the ...1,0,... pattern
before the algorithm can figure out on which side of the number 2 the
interval lies. It is true that the next random numbers may be very
cheap to calculate (they could require *no* random bits) but if a and
b were very close together, then there were very few bits representing
the difference between them, and the next random numbers could be
inaccurate.
[/quote]
An extreme example of this is that the right sequence of random bits
could cause a to be equal to b. The algorithm would never recover
from this condition.
Now I have a comment on the performance of this algorithm. Let K be
the product of all the k's for which random numbers have been
generated. The absolute lower bound on the number of bits required is
log2(K). Since the number of bits must be an integer, you could say
that the lower bound is ceiling(log2(K)). The *expected value* of the
number of bits required is bounded:
ceiling(log2(K)) <= E(number of bits) < log2(K)+2
I tested this algorithm by using the above routine as is (ignoring all
the warnings about loss of accuracy) by simulating the shuffling of a
deck of cards using the Fisher-Yates shuffle. After each complete
shuffle, I reset a to 0 and b to 1. Each shuffle has K=52!. The
value of log2(K) ~= 225.581. So a minimum number of 226 bits is
required for each shuffle, and the expected value is bounded above by
approximately 227.581. I simulated the shuffle 10^9 times (one
American billion) recording a histogram of the number of bits required
for each shuffle. Here are the results:
226 252037639
227 373996086
228 186993057
229 93499471
230 46736407
231 23370424
232 11688446
233 5839317
234 2918490
235 1460270
236 730742
237 365419
238 181785
239 91192
240 45675
241 22956
242 11239
243 5660
244 2797
245 1465
246 729
247 343
248 195
249 91
250 56
251 24
252 11
253 5
254 4
255 5
The average number of bits required for shuffling a deck of cards
was 227.495837354.
Scott
--
Scott Hemphill hemphill at (no spam) alumni.caltech.edu
"This isn't flying. This is falling, with style." -- Buzz Lightyear |
|
|
| Back to top |
|
|
|
| Ray Koopman... |
| Posted: Thu Oct 22, 2009 12:33 pm |
|
|
|
Guest
|
On Oct 21, 7:55 am, Mok-Kong Shen <mok-kong.s... at (no spam) t-online.de> wrote:
[quote]Gordon Sande wrote:
Mok-Kong Shen <mok-kong.s... at (no spam) t-online.de
If one has a good sequence of random bits and desires random numbers
in [0,m-1], one could take k bits with 2^k >= m > 2^(k-1), discarding
them and taking another k bits, in case the number obtained is not in
the desired range. Is there perhaps a better procedure that economizes
the use of the given bits, since the bits discarded are in fact well
random?
If you are just worrying about "complexity" issues then find r so that
r*m is closer to but still smaller than some 2^K. You can determine
r values mod m at once with higher rejection efficiency. It is good
for a complexity result but not very practical if you are waiting online.
Find a value mod r*m and then treat it as an r digit value in base m.
The application I have in mind is the Algorithm P in Knuth's book
to obtain random permutations of n objects. It is assumed that a
good quality random bit sequence is available for generating the
random numbers needed in the algorithm. The question is whether
there is a highly optimal/economic way of practically utilizing the
given bit sequence.
Thanks,
M. K. Shen
[/quote]
This will randomly permute x(0),...,x(n-1). It requires
only a single random number, with k = ceiling(log2(n!))
bits. It presumes the ability to operate on arbitrarily
large integers.
r = a random integer in [0, n!-1];
For j = n-1 to 1 step -1: {
q = r / j! /* integer division */ ;
r = r - q*j! ;
swap x(q) and x(j) } |
|
|
| Back to top |
|
|
|
| Mok-Kong Shen... |
| Posted: Thu Oct 22, 2009 1:10 pm |
|
|
|
Guest
|
Mok-Kong Shen wrote:
[quote]If one has a good sequence of random bits and desires random numbers
in [0,m-1], one could take k bits with 2^k >= m > 2^(k-1), discarding
them and taking another k bits, in case the number obtained is not in
the desired range. Is there perhaps a better procedure that economizes
the use of the given bits, since the bits discarded are in fact well
random?
[/quote]
I like to thank all who have commented and given suggestions. 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 |
|
|
| Back to top |
|
|
|
| Ray Koopman... |
| Posted: Thu Oct 22, 2009 9:10 pm |
|
|
|
Guest
|
On Oct 22, 12:10 pm, Mok-Kong Shen <mok-kong.s... at (no spam) t-online.de> wrote:
[quote][...] 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?
[/quote]
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. |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Fri Dec 11, 2009 7:45 am
|
|