Re: Use of random bits

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:
On 2009-10-21 16:00:56 -0300, Art Kendall <Art@xxxxxxxxxxxxx> 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@xxxxxxxxxxx> said:

Gordon Sande wrote:
Mok-Kong Shen <mok-kong.shen@xxxxxxxxxxx>

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.


Quantcast