这种简单的改组算法是否会返回一张随机混乱的扑克牌？

Question

您有52张卡片的列表,其中该列表中的卡片位置不会移动.您有第二张卡位置列表.首先,位置列表与第一个列表相同.

1. 迭代第一个列表.

2. 对于第一个列表中的每张卡,生成一个从1到52的数字.将卡在第二个列表中的位置与卡在该位置交换.

存在偏见吗？为什么？

更新:从来没有人相信纯数学或逻辑,我决定自己实现这一点.以下是第5张卡(位置方式)从1到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%

如你所见,非常随机.我想要一位数学家来证明为什么第五张卡比其他任何东西都更有可能,但我猜这与早期卡片(如7)有更多交换机会这一事实有关 - 其​​中正是算法所能阻止的,它只允许卡片交换一次.

Answer 1

这是破坏Fisher-Yates shuffle算法的常用方法.看看你从这个破碎的随机混乱中获得了什么分布？有关此实现的属性的热烈讨论.

这与Fisher-Yates有什么不同？

对于Fisher-Yates,在kth卡上你必须在k和之间选择一个随机数52.你选择之间的随机数1和52每个时间.

你描述的方法类似于你从这个破碎的随机shuffle得到什么分布中讨论的方法？,但可能不完全一样.你的实施类似于井上研究"从顶部到随机"的混乱(参见Diaconis,Fill和Pitman的随机混乱的分析),最终将给出一个完全洗牌的套牌,尽管不是"一次通过".Top to Random shuffle描述如下:

选择一个随机数p从1到 52,并与卡在位置换顶牌p.继续,直到顶部卡片是最初位置的卡片52,然后随机放置,卡片是随机顺序.

这种停止条件被称为"停止时间",需要很长时间才能达到.Fisher-Yates shuffle要快得多.