Does this simple shuffling algorithm return a rand

问题:

You have a list of 52 cards where the position of the cards in that list does not move. You have a second list of card positions. At first, the position list is the same as the first list.

1. Iterate through the first list.

2. For each card in the first list, generate a number from 1 to 52. Swap its position in the second list with the card in that position.

Does a bias exist? Why?

Update: Never one to believe pure math or logic, I decided to implement this myself. Here are the percent chance of the 5th card (position-wise) to be each number from 1 to 52:

1. 1.9346%
2. 1.9011%
3. 1.8513%
4. 1.8634%
5. 1.8561%
6. 1.8382%
7. 2.5086%
8. 2.4528%
9. 2.4552%
10. 2.3772%
11. 2.3658%
12. 2.3264%
13. 2.3375%
14. 2.287%
15. 2.2627%
16. 2.2151%
17. 2.1846%
18. 2.1776%
19. 2.1441%
20. 2.1103%
21. 2.084%
22. 2.0505%
23. 2.0441%
24. 2.0201%
25. 1.972%
26. 1.9568%
27. 1.9477%
28. 1.9429%
29. 1.9094%
30. 1.8714%
31. 1.8463%
32. 1.8253%
33. 1.8308%
34. 1.8005%
35. 1.7633%
36. 1.7634%
37. 1.769%
38. 1.7269%
39. 1.705%
40. 1.6858%
41. 1.6657%
42. 1.6491%
43. 1.6403%
44. 1.6189%
45. 1.6204%
46. 1.5953%
47. 1.5872%
48. 1.5632%
49. 1.5402%
50. 1.5347%
51. 1.5191%
52. 1.5011%

As you can see, quite un-random. I'd love a mathematician to prove why the 5th card is more likely to be a 7 than anything else, but I'm guessing it has to do with the fact that early cards, like 7, have more opportunities to swap -- which is exactly what the right algorithm prevents, it only lets cards swap once.

回答1:

This is a common way to botch the Fisher-Yates shuffle algorithm. See What distribution do you get from this broken random shuffle? for a lively discussion on properties of this implementation.

---

How is this different from Fisher-Yates?

For Fisher-Yates, at the kth card you must choose a random number between k and 52. You are choosing a random number between 1 and 52 each time.

---

The method you describe is similar to that discussed in What distribution do you get from this broken random shuffle?, but may not be exactly the same. Your implementation is similar to the well studies "Top to Random" shuffle (see Analysis of Top To Random Shuffles by Diaconis, Fill and Pitman) that will eventually give a fully shuffled deck, though not in "one pass". The Top to Random shuffle is described as following:

Choose a random number p from 1 to 52, and swap the top card with the card at position p. Continue until the top card is the card originally in position 52, and after this is randomly placed the deck is in random order.

This stop condition is known as a "Stopping Time", and takes quite a while to attain. The Fisher-Yates shuffle is far faster.

回答2:

Yes, there exists a bias, and it is easy to compute.

You ask the random number generator 52 times for a number between 1 and 52. This, in the end, amounts to 52^52 possible answers.

But there are only 52! possible shuffled decks, so with the above algorithm, the shuffling cannot be evenly distributed.

You need to make sure that you ask the random number generator for ld(52!) bits of randomness, not ld(52^52).