Ergibt dieser einfache Mischalgorithmus ein zufällig gemischtes Spielkartendeck?

Question

Sie haben eine Liste mit 52 Karten, bei der sich die Position der Karten in dieser Liste nicht ändert. Sie haben eine zweite Liste mit Kartenpositionen. Zunächst ist die Positionsliste dieselbe wie die erste Liste.

1. Iterieren Sie durch die erste Liste.

2. Erstelle für jede Karte in der ersten Liste eine Zahl von 1 bis 52. Tausche ihre Position in der zweiten Liste mit der Karte an dieser Position.

Gibt es eine Voreingenommenheit? Warum?

Update: Da ich nie an reine Mathematik oder Logik geglaubt habe, habe ich beschlossen, dies selbst umzusetzen. Hier ist die prozentuale Chance, dass die 5. Karte (von der Position her) jede Zahl von 1 bis 52 ist:

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%

Wie Sie sehen können, ist das nicht ganz zufällig. Ich würde es lieben, wenn ein Mathematiker beweisen könnte, warum die 5. Karte mit größerer Wahrscheinlichkeit eine 7 ist als irgendetwas anderes, aber ich vermute, dass es damit zu tun hat, dass frühe Karten, wie die 7, mehr Möglichkeiten haben, zu tauschen - was genau das ist, was der richtige Algorithmus verhindert, er lässt Karten nur einmal tauschen.

Answer 1

Dies ist eine gängige Methode, um die Fisher-Yates-Shuffle-Algorithmus . Siehe Welche Verteilung ergibt sich aus dieser fehlerhaften Zufallsmischung? für eine lebhafte Diskussion über die Eigenschaften dieser Implementierung.

---

Was ist der Unterschied zu Fisher-Yates?

Für Fisher-Yates, bei der k Karte müssen Sie eine Zufallszahl wählen zwischen k y 52 . Sie wählen eine Zufallszahl zwischen 1 y 52 jedes Mal.

---

Die von Ihnen beschriebene Methode ähnelt der Methode, die in Welche Verteilung ergibt sich aus dieser fehlerhaften Zufallsmischung? , aber möglicherweise nicht genau dasselbe. Ihre Implementierung ähnelt der gut studierten "Top to Random"-Mischung (siehe Analyse von Top To Random Shuffles von Diaconis, Fill und Pitman), das schließlich ein vollständig gemischtes Deck ergibt, wenn auch nicht in "einem Durchgang". Die Top to Random-Mischung wird wie folgt beschrieben:

Wählen Sie eine Zufallszahl p de 1 zu 52 und tauschen Sie die oberste Karte mit der Karte an Position p . Fahren Sie fort, bis die oberste Karte die Karte ist, die ursprünglich in Position 52 und danach ist zufällig platziert wird, ist das Deck in zufälliger Reihenfolge.

Diese Anhaltebedingung wird als "Anhaltezeit" bezeichnet, und es dauert eine ganze Weile, bis sie erreicht ist. Die Fisher-Yates-Mischung ist viel schneller.

Answer 2

Ja, es gibt eine Verzerrung, und sie ist leicht zu berechnen.

Sie fragen den Zufallszahlengenerator 52 Mal nach einer Zahl zwischen 1 und 52. Das ergibt letztlich 52^52 mögliche Antworten.

Es gibt jedoch nur 52! mögliche gemischte Decks, so dass mit dem obigen Algorithmus das Mischen nicht gleichmäßig verteilt werden kann.

Sie müssen darauf achten, dass Sie den Zufallszahlengenerator nach ld(52!) Bits der Zufälligkeit, nicht ld(52^52) .