Korrelation zwischen zwei Kartenspielen?

Ich habe ein Programm geschrieben, um ein Überhandkarten -Shuffle zu simulieren .

Jede Karte ist nummeriert, mit einer Farbe von CLUBS, DIAMONDS, HEARTS, SPADESund einem Rang von zwei bis zehn, dann Jack, Queen, King und Ace. Somit hat die Zwei der Vereine eine Nummer von 1, die Drei der Vereine eine 2 .... Das Ass der Vereine ist 13 ... Das Pik-Ass ist 52.

Eine der Methoden, um festzustellen, wie gemischt die Karten sind, besteht darin, sie mit einer nicht gemischten Karte zu vergleichen und festzustellen, ob die Reihenfolge der Karten korreliert.

Das heißt, ich könnte diese Karten mit der nicht gemischten Karte zum Vergleich haben:

Unshuffled          Shuffled            Unshuffled number   Shuffled number
Two of Clubs        Three of Clubs      1                   2
Three of Clubs      Two of Clubs        2                   1
Four of Clubs       Five of Clubs       3                   4
Five of Clubs       Four of Clubs       4                   3

Die Korrelation nach der Pearson-Methode wäre: 0,6

Bei einem großen Kartensatz (alle 52) können Muster entstehen. Meine Hypothese ist, dass Sie nach mehr Mischen weniger Korrelation erhalten.

Es gibt jedoch viele Möglichkeiten, die Korrelation zu messen.

Ich habe mich an Pearsons Korrelation versucht, bin mir aber nicht sicher, ob dies die richtige Korrelation für diese Situation ist.

Ist dies ein geeignetes Korrelationsmaß? Gibt es eine geeignetere Maßnahme?

Bonuspunkte Manchmal sehe ich diese Art von Daten in meinen Ergebnissen:

Natürlich gibt es eine gewisse Korrelation, aber ich weiß nicht, wie Sie die einzelnen "Trendlinien" messen?

Sie können den relativen Korrelationsgrad (oder genauer den zunehmenden Grad der Zufälligkeit) anhand der Shannon-Entropie der Differenz des Nennwerts zwischen allen Paaren benachbarter Karten messen .

$i=1,2,...,52$$\Delta F_{i} = F_{i+1} - F_{i}$$(i+1)$$i$$F_{i+1} = 51$$F_{i} = 3$$\Delta F_{i} = 51-3 = 48$$i=52$$\Delta F_{52} = F_{1} - F_{52}$$\Delta F$

$p_{1}, p_{2}, ... p_{52}$

Sobald Sie das Histogramm haben, können Sie die Shannon-Entropie für eine bestimmte Shuffle-Iteration als berechnen.

$$E = \sum_{k=1}^{52} -p_{k} ln(p_{k})$$ Ich habe eine kleine Simulation in R geschrieben, um das Ergebnis zu demonstrieren. Das erste Diagramm zeigt, wie sich die Entropie im Verlauf von 20 Shuffle-Iterationen entwickelt. Ein Wert von 0 ist einem perfekt geordneten Deck zugeordnet. Größere Werte bedeuten ein Deck, das zunehmend ungeordneter oder dekorrelierter ist. Das zweite Diagramm zeigt eine Reihe von 20 Facetten, von denen jede ein Diagramm enthält, das dem ursprünglich in der Frage enthaltenen ähnelt und die Reihenfolge der gemischten Karten im Vergleich zur ursprünglichen Kartenreihenfolge zeigt. Die 20 Facetten im zweiten Plot sind die gleichen wie die 20 Iterationen im ersten Plot, und sie sind auch gleich farbcodiert, so dass Sie ein visuelles Gefühl dafür bekommen, welcher Grad der Shannon-Entropie dem Ausmaß der Zufälligkeit entspricht die Sortierreihenfolge. Der Simulationscode, der die Diagramme generiert hat, wird am Ende angehängt.

library(ggplot2)

# Number of cards
ncard <- 52 
# Number of shuffles to plot
nshuffle <- 20
# Parameter between 0 and 1 to control randomness of the shuffle
# Setting this closer to 1 makes the initial correlations fade away
# more slowly, setting it closer to 0 makes them fade away faster
mixprob <- 0.985 
# Make data frame to keep track of progress
shuffleorder <- NULL
startorder <- NULL
iteration <- NULL
shuffletracker <- data.frame(shuffleorder, startorder, iteration)

# Initialize cards in sequential order
startorder <- seq(1,ncard)
shuffleorder <- startorder

entropy <- rep(0, nshuffle)
# Loop over each new shuffle
for (ii in 1:nshuffle) {
    # Append previous results to data frame
    iteration <- rep(ii, ncard)
    shuffletracker <- rbind(shuffletracker, data.frame(shuffleorder,
                            startorder, iteration))
    # Calculate pairwise value difference histogram
    freq <- rep(0, ncard)
    for (ij in 1:ncard) {
        if (ij == 1) {
            idx <- shuffleorder[1] - shuffleorder[ncard]
        } else {
            idx <- shuffleorder[ij] - shuffleorder[ij-1]
        }
        # Impose periodic boundary condition
        if (idx < 1) {
            idx <- idx + ncard
        }
        freq[idx] <- freq[idx] + 1
    }
    # Sum over frequency histogram to compute entropy
    for (ij in 1:ncard) {
        if (freq[ij] == 0) {
            x <- 0
        } else {
            p <- freq[ij] / ncard
            x <- -p * log(p, base=exp(1))
        }
        entropy[ii] <- entropy[ii] + x
    }
    # Shuffle the cards to prepare for the next iteration
    lefthand <- shuffleorder[floor((ncard/2)+1):ncard]
    righthand <- shuffleorder[1:floor(ncard/2)]
    ij <- 0
    ik <- 0
    while ((ij+ik) < ncard) {
        if ((runif(1) < mixprob) & (ij < length(lefthand))) {
            ij <- ij + 1
            shuffleorder[ij+ik] <- lefthand[ij]
        }
        if ((runif(1) < mixprob) & (ik < length(righthand))) {
            ik <- ik + 1
            shuffleorder[ij+ik] <- righthand[ik]
        }
    }
}
# Plot entropy vs. shuffle iteration
iteration <- seq(1, nshuffle)
output <- data.frame(iteration, entropy)
print(qplot(iteration, entropy, data=output, xlab="Shuffle Iteration", 
            ylab="Information Entropy", geom=c("point", "line"),
            color=iteration) + scale_color_gradient(low="#ffb000",
            high="red"))

# Plot gradually de-correlating sort order
dev.new()
print(qplot(startorder, shuffleorder, data=shuffletracker, color=iteration,
            xlab="Start Order", ylab="Shuffle Order") + facet_wrap(~ iteration,
            ncol=4) + scale_color_gradient(low="#ffb000", high="red"))

Ich weiß, dass dieser Beitrag fast 4 Jahre alt ist, aber ich bin ein Hobby-Kryptoanalytiker und habe Spielkarten-Chiffren studiert . Infolgedessen bin ich immer wieder auf diesen Beitrag zurückgekommen, um das Mischen von Decks als Entropiequelle für die zufällige Eingabe des Decks zu erklären. Schließlich beschloss ich, die Antwort durch Stachyra zu überprüfen, indem ich das Deck von Hand mischte und die Deckentropie nach jedem Mischen schätzte.

TL; DR, um die Deckentropie zu maximieren:

• Für nur Riffle Shuffling benötigen Sie 11-12 Shuffles.
• Um zuerst das Deck zu schneiden und dann das Riffle zu mischen, benötigen Sie nur 6-7 Cut-and-Shuffles.

Zunächst einmal ist alles richtig, was Stachyra zur Berechnung der Shannon-Entropie erwähnt hat. Es kann folgendermaßen eingekocht werden:

1. Weisen Sie jeder der 52 Karten im Deck numerisch einen eindeutigen Wert zu.
2. Mische das Deck.
3. Notieren Sie für n = 0 bis n = 51 jeden Wert von (n - (n + 1) mod 52) mod 52
4. Zählen Sie die Anzahl der Vorkommen von 0, 1, 2, ..., 49, 50, 51
5. Normalisieren Sie diese Datensätze, indem Sie sie jeweils durch 52 teilen
6. Berechnen Sie für i = 1 bis i = 52 -p_i * log (p_i) / log (2)
7. Summiere die Werte

Wenn Stachyra eine subtile Annahme macht, ist die Implementierung eines menschlichen Shuffle in einem Computerprogramm mit etwas Gepäck verbunden. Bei papierbasierten Spielkarten wird Öl aus Ihren Händen auf die Karten übertragen, sobald sie verwendet werden. Im Laufe der Zeit werden die Karten aufgrund von Ölansammlungen zusammenkleben und dies wird in Ihrem Shuffle enden. Je stärker das Deck genutzt wird, desto wahrscheinlicher werden zwei oder mehr benachbarte Karten zusammenkleben und desto häufiger wird es passieren.

Weiter angenommen, die beiden Clubs und Jack of Hearts halten zusammen. Sie können für die Dauer Ihres Mischens zusammenkleben und sich nie trennen. Dies könnte in einem Computerprogramm nachgeahmt werden, aber dies ist bei der R-Routine von stachyra nicht der Fall.

Stachyra hat auch eine Manipulationsvariable "mixprob". Ohne diese Variable vollständig zu verstehen, handelt es sich um eine Art Black Box. Sie können es falsch einstellen, was sich auf die Ergebnisse auswirkt. Also wollte ich sicherstellen, dass seine Intuition korrekt war. Also habe ich es von Hand überprüft.

Ich habe das Deck 20 Mal von Hand gemischt, in zwei verschiedenen Fällen (insgesamt 40 Mischen). In erster Linie habe ich nur das Riffeln gemischt und dabei die rechten und linken Schnitte nahezu gleichmäßig gehalten. Im zweiten Fall schneide ich das Deck absichtlich von der Mitte des Decks weg (1/3, 2/5, 1/4 usw.), bevor ich einen gleichmäßigen Schnitt für das Riffle Shuffle mache. Mein Bauchgefühl in der zweiten Instanz war, dass ich durch Schneiden des Decks vor dem Mischen und Halten von der Mitte weg eine Diffusion schneller in das Deck einbringen konnte als das Mischen von Standard-Riffeln.

Hier sind die Ergebnisse. Erstens, gerade Riffel mischen:

Und hier wird das Deck in Kombination mit dem Mischen von Riffs geschnitten:

Es scheint, dass die Entropie in etwa der Hälfte der Zeit der Behauptung durch Stachyra maximiert ist. Außerdem war meine Intuition richtig, dass das Decks absichtlich absichtlich von der Mitte weggeschnitten wurde, bevor das Mischen der Riffs mehr Diffusion in das Deck einbrachte. Nach ungefähr 5 Schlurfen war es jedoch nicht mehr wirklich wichtig. Sie können sehen, dass nach ungefähr 6-7 Mischen die Entropie maximiert ist, gegenüber den 10-12, als die Behauptung mein Stachyra machte. Könnte es möglich sein, dass 7 Shuffles ausreichen, oder werde ich geblendet?

Sie können meine Daten bei Google Sheets sehen . Es ist möglich, dass ich eine oder zwei Spielkarten falsch aufgenommen habe, daher kann ich keine 100% ige Genauigkeit der Daten garantieren.

Es ist wichtig, dass Ihre Ergebnisse auch unabhängig überprüft werden. Brad Mann vom Institut für Mathematik der Harvard University untersuchte, wie oft es dauern würde, ein Kartenspiel zu mischen, bevor die Vorhersagbarkeit einer Karte im Kartenspiel völlig unvorhersehbar ist (die Shannon-Entropie ist maximiert). Seine Ergebnisse finden Sie in diesem 33-seitigen PDF .

Interessant an seinen Ergebnissen ist, dass er tatsächlich einen Artikel der New York Times von 1990 von Persi Diaconis unabhängig überprüft , der behauptet, dass 7 Shuffles ausreichen, um ein Kartenspiel über das Riffle Shuffle gründlich zu mischen.

Brad Mann geht beim Mischen einige verschiedene mathematische Modelle durch, einschließlich Markov-Ketten, und kommt zu folgendem Ergebnis:

Dies ist ungefähr 11,7 für n = 52, was bedeutet, dass wir unter diesem Gesichtspunkt erwarten, dass durchschnittlich 11 oder 12 Mischvorgänge erforderlich sind, um ein echtes Kartenspiel zufällig zu ordnen. Beachten Sie, dass dies wesentlich größer als 7 ist.

Brad Mann überprüfte nur unabhängig das Ergebnis von Stachyra und nicht meins. Also habe ich mir meine Daten genauer angesehen und festgestellt, warum 7 Shuffles nicht ausreichen. Zunächst einmal beträgt die theoretische maximale Shannon-Entropie in Bit für jede Karte im Deck log (52) / log (2) ~ = 5,7 Bit. Aber meine Daten brechen nie wirklich viel über 5 Bits. Seltsamerweise habe ich in Python ein Array mit 52 Elementen erstellt und dieses Array gemischt:

>>> import random
>>> r = random.SystemRandom()
>>> d = [x for x in xrange(1,52)]
>>> r.shuffle(d)
>>> print d
[20, 51, 42, 44, 16, 5, 18, 27, 8, 24, 23, 13, 6, 22, 19, 45, 40, 30, 10, 15, 25, 37, 52, 34, 12, 46, 48, 3, 26, 4, 1, 38, 32, 14, 43, 7, 31, 50, 47, 41, 29, 36, 39, 49, 28, 21, 2, 33, 35, 9, 17, 11]

Die Berechnung der Entropie pro Karte ergibt etwa 4,8 Bit. Wenn Sie dies etwa ein Dutzend Mal tun, werden ähnliche Ergebnisse zwischen 5,2 Bit und 4,6 Bit angezeigt, wobei der Durchschnitt 4,8 bis 4,9 beträgt. Es reicht also nicht aus, den Rohentropiewert meiner Daten zu betrachten, sonst könnte ich es bei 5 Shuffles als gut bezeichnen.

Bei näherer Betrachtung meiner Daten bemerkte ich die Anzahl der "Null-Buckets". Dies sind Eimer, in denen für diese Nummer keine Daten für Deltas zwischen Kartenflächen vorhanden sind. Wenn beispielsweise der Wert zweier benachbarter Karten subtrahiert wird, gibt es kein "15" -Ergebnis, nachdem alle 52 Deltas berechnet wurden.

Ich sehe, dass es sich irgendwann um 17-18 "Zero Buckets" um 11-12 Shuffles einstellt. Sicher genug, mein gemischtes Deck über Python hat einen Durchschnitt von 17 bis 18 "Null-Eimern", mit einem Hoch von 21 und einem Tief von 14. Warum 17 bis 18 das festgelegte Ergebnis ist, kann ich noch nicht erklären. Aber es scheint, dass ich sowohl ~ 4,8 Bit Entropie als auch 17 "Null-Eimer" will.

Mit meinem Stock Riffle Shuffling sind das 11-12 Shuffles. Bei meinem Cut-and-Shuffle sind das 6-7. Wenn es um Spiele geht, würde ich Cut-and-Shuffles empfehlen. Dies garantiert nicht nur, dass die oberen und unteren Karten bei jedem Shuffle in das Deck gemischt werden, es ist auch einfach schneller als 11-12 Shuffles. Ich weiß nichts über dich, aber wenn ich mit meiner Familie und meinen Freunden Kartenspiele spiele, sind sie nicht geduldig genug, um 12 Riffel-Shuffles durchzuführen.