Does shuffle() produce uniform result ?

Dan Bishop danb_83 at yahoo.com
Sat Aug 25 15:48:33 CEST 2007


On Aug 24, 2:38 am, tooru honda <tooru_ho... at fast-mail.org> wrote:
> Hi,
>
> I have read the source code of the built-in random module, random.py.
> After also reading Wiki article on Knuth Shuffle algorithm, I wonder if
> the shuffle method implemented in random.py produces results with modulo
> bias.
>
> The reasoning is as follows: Because the method random() only produces
> finitely many possible results, we get modulo bias when the number of
> possible results is not divisible by the size of the shuffled list.
>
> 1. Does shuffle() produce uniform result ?

Experimental evidence with a 5-card decks and 1,200,000 simulation
gives me

[9782, 9784, 9784, 9786, 9817, 9822, 9825, 9841, 9859, 9864, 9866,
9872, 9886, 9888, 9893, 9893, 9893, 9893, 9896, 9896, 9901, 9905,
9909, 9909, 9912, 9917, 9919, 9920, 9920, 9925, 9932, 9933, 9934,
9938, 9938, 9943, 9944, 9946, 9947, 9951, 9952, 9955, 9956, 9959,
9960, 9961, 9962, 9963, 9964, 9966, 9968, 9968, 9968, 9969, 9969,
9975, 9977, 9978, 9978, 9979, 9985, 9987, 9990, 9996, 9998, 9998,
10002, 10009, 10012, 10015, 10017, 10018, 10020, 10026, 10027, 10028,
10032, 10035, 10042, 10047, 10048, 10049, 10049, 10055, 10056, 10060,
10062, 10064, 10066, 10069, 10070, 10076, 10087, 10089, 10092, 10095,
10097, 10098, 10100, 10101, 10116, 10117, 10128, 10129, 10131, 10137,
10138, 10140, 10146, 10155, 10158, 10162, 10162, 10163, 10177, 10190,
10190, 10232, 10260, 10292]

frequencies of each of the 120 possible orderings.  The chi-squared
test statistic (for H0: all 120 orderings are equally likely) is
132.9472 with 119 degrees of freedom.  The p-value is 0.1804, which is
greater than typically-used significance levels, so there is
insufficient evidence to reject H0.




More information about the Python-list mailing list