Korelacja między dwiema taliami kart?

Napisałem program do symulacji występowi karty Losowo.

Każda karta jest ponumerowana, kolor odpowiada, od CLUBS, DIAMONDS, HEARTS, SPADESrangi od dwóch do dziesięciu, a następnie Jacka, Królowej, Króla i Asa. Zatem Two of Clubs ma liczbę 1, Three of Clubs 2 ... As trefl wynosi 13 ... As pik wynosi 52.

Jedną z metod ustalenia, jak potasowane są karty, jest porównanie ich z nietasowaną kartą i sprawdzenie, czy kolejność kart jest skorelowana.

Oznacza to, że mogę mieć te karty z niepasowaną kartą do porównania:

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

Korelacja metodą Pearsona wynosiłaby: 0,6

Przy dużym zestawie kart (wszystkie 52) mogą pojawić się wzorce. Moja hipoteza jest taka, że ​​po większym tasowaniu uzyskasz mniejszą korelację.

Istnieje jednak wiele sposobów pomiaru korelacji.

Próbowałem swoich sił w korelacji Pearsona, ale nie jestem pewien, czy jest to właściwa korelacja do zastosowania w tej sytuacji.

Czy to odpowiednia miara korelacji? Czy istnieje bardziej odpowiedni środek?

Punkty bonusowe Czasami widzę takie dane w moich wynikach:

Oczywiście istnieje pewna korelacja, ale nie wiem, jak mierzysz osobne „linie trendu”?

Możesz zmierzyć względny poziom korelacji (a ściślej rosnący poziom losowości) za pomocą entropii Shannona różnicy wartości nominalnej między wszystkimi parami sąsiednich kart.

Oto jak to obliczyć dla losowo tasowanej talii 52 kart. Zaczynasz od zapętlenia całej talii i zbudowania swego rodzaju histogramu. Dla każdej pozycji karty$i=1,2,...,52$, oblicz różnicę wartości nominalnej $\Delta F_{i} = F_{i+1} - F_{i}$. Aby uczynić to bardziej konkretnym, powiedzmy, że karta w$(i+1)$pozycja jest królem pik, a karta w $i$czwarta pozycja to cztery kluby. Potem będzie$F_{i+1} = 51$ i $F_{i} = 3$ i $\Delta F_{i} = 51-3 = 48$. Kiedy dojdziesz do$i=52$, to szczególny przypadek; ponownie zapętlasz się z powrotem na początek talii i bierzesz$\Delta F_{52} = F_{1} - F_{52}$. Jeśli skończą się liczby ujemne dla dowolnego z$\Delta F$dodaj 52, aby sprowadzić różnicę wartości nominalnej z powrotem do zakresu 1-52.

Otrzymasz zestaw różnic wartości nominalnej dla 52 par sąsiednich kart, z których każda mieści się w dozwolonym zakresie od 1-52; policz ich względną częstotliwość za pomocą histogramu (tj. jednowymiarowej tablicy) z 52 elementami. Histogram rejestruje rodzaj „obserwowanego rozkładu prawdopodobieństwa” dla talii; możesz znormalizować ten rozkład, dzieląc liczby w każdym przedziale przez 52. W ten sposób powstanie szereg zmiennych$p_{1}, p_{2}, ... p_{52}$ gdzie każda z nich może przyjąć dyskretny zakres możliwych wartości: {0, 1/52, 2/52, 3/52 itd.} w zależności od tego, ile różnic par wartości twarzy trafiło losowo do określonego przedziału histogramu.

Po utworzeniu histogramu możesz obliczyć entropię Shannona dla określonej iteracji losowania jako

$$E = \sum_{k=1}^{52} -p_{k} ln(p_{k})$$ Napisałem małą symulację w języku R, aby zademonstrować wynik. Pierwszy wykres pokazuje, jak ewoluuje entropia w ciągu 20 iteracji losowych. Wartość 0 jest powiązana z idealnie uporządkowaną talią; większe wartości oznaczają talię, która jest coraz bardziej nieuporządkowana lub powiązana z dekoracją. Drugi wykres pokazuje serię 20 aspektów, z których każdy zawiera wykres podobny do tego, który pierwotnie był dołączony do pytania, pokazując losową kolejność kart względem początkowej kolejności kart. 20 aspektów na 2. wykresie jest takich samych jak 20 iteracji na pierwszym wykresie, a także są również oznaczone tym samym kolorem, dzięki czemu można wizualnie wyczuć, jaki poziom entropii Shannona odpowiada ilości losowości w kolejność sortowania. Kod symulacji, który wygenerował wykresy, jest dołączany na końcu.

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"))

Wiem, że ten post ma prawie 4 lata, ale jestem hobbystycznym kryptoanalitykiem i studiuję szyfrów do gry . W rezultacie wielokrotnie powracałem do tego postu, aby wyjaśnić tasowanie talii jako źródło entropii do losowego wpisywania talii. W końcu postanowiłem zweryfikować odpowiedź przez stachyrę, ręcznie tasując talię i oceniając entropię talii po każdym tasowaniu.

TL; DR, aby zmaksymalizować entropię pokładu:

• Aby przetasować tylko riffle, potrzebujesz 11-12 przetasowań.
• Aby najpierw wyciąć talię, a następnie przetasować riffle, potrzebujesz tylko 6-7 cięć i tasowania.

Po pierwsze, wszystko, co wspominała Stachyra do obliczania entropii Shannona, jest poprawne. Można go sprowadzić w ten sposób:

1. Przydziel numerycznie unikalną wartość każdej z 52 kart w talii.
2. Potasuj talię.
3. Dla n = 0 do n = 51, zanotuj każdą wartość (n - (n + 1) mod 52) mod 52
4. Policz liczbę wystąpień 0, 1, 2, ..., 49, 50, 51
5. Znormalizuj te rekordy, dzieląc każdy przez 52
6. Dla i = 1 do i = 52, oblicz -p_i * log (p_i) / log (2)
7. Zsumuj wartości

Stachyra przyjmuje jedno subtelne założenie, że wprowadzenie losowego losu w programie komputerowym przyniesie trochę bagażu. Dzięki papierowym kartom do gry, gdy się przyzwyczają, olej z rąk przenosi się na karty. Z biegiem czasu, z powodu nagromadzenia ropy, karty zaczną się sklejać, a to skończy się tasowaniem. Im bardziej intensywnie używana talia, tym bardziej prawdopodobne, że dwie lub więcej sąsiadujących ze sobą kart sklei się i tym częściej będzie się to zdarzało.

Co więcej, przypuszczalnie dwa kluby i walet kier trzymają się razem. Mogą skończyć się razem podczas tasowania, nigdy się nie rozdzielając. Można to naśladować w programie komputerowym, ale nie jest tak w przypadku procedury R. Stachyry.

Ponadto Stachyra ma zmienną manipulacyjną „mixprob”. Bez pełnego zrozumienia tej zmiennej jest to trochę czarna skrzynka. Możesz go nieprawidłowo ustawić, wpływając na wyniki. Chciałem więc upewnić się, że jego intuicja jest poprawna. Więc zweryfikowałem to ręcznie.

Przetasowałem talię 20 razy ręcznie, w dwóch różnych przypadkach (40 losowych tasowań). W pierwszej kolejności po prostu przetasowałem, trzymając prawe i lewe cięcia prawie równe. W drugim przypadku celowo odciąłem talię od jej środka (1/3, 2/5, 1/4 itd.), Zanim wykonałem równomierne cięcie dla przetasowania riffle. Moje drugie przeczucie było takie, że przecinając pokład przed tasowaniem i trzymając się z dala od środka, mogłem wprowadzić dyfuzję do pokładu szybciej niż tasowanie karabinu podstawowego.

Oto wyniki. Po pierwsze, tasowanie karabinu prostego:

A oto cięcie talii w połączeniu z tasowaniem karabinów:

Wydaje się, że entropia zostaje zmaksymalizowana w około 1/2 czasu roszczenia przez Stachyrę. Co więcej, moja intuicja była słuszna, że ​​celowe odcięcie talii od środka najpierw, zanim tasowanie karabinów wprowadziło więcej dyfuzji do talii. Jednak po około 5 losach nie miało to już większego znaczenia. Widać, że po około 6-7 przetasowaniach entropia jest zmaksymalizowana w porównaniu z 10-12, gdy roszczenie uczyniło moją stachyrę. Czy to możliwe, że 7 tasowań jest wystarczających, czy też jestem oślepiony?

Możesz zobaczyć moje dane w Arkuszach Google . Możliwe, że źle zapisałem jedną lub dwie karty do gry, więc nie mogę zagwarantować 100% dokładności danych.

Ważne jest, aby twoje ustalenia również były niezależnie weryfikowane. Brad Mann z Wydziału Matematyki na Uniwersytecie Harvarda zbadał, ile razy potrzeba potasować talię kart, zanim przewidywalność dowolnej karty w talii jest całkowicie nieprzewidywalna (entropia Shannona jest zmaksymalizowana). Jego wyniki można znaleźć w tym 33-stronicowym pliku PDF .

Co ciekawe, jego odkrycia polegają na tym, że w rzeczywistości samodzielnie weryfikuje artykuł Persi Diaconisa z 1990 roku napisany przez New York Timesa , który twierdzi, że 7 tasowań wystarcza do dokładnego wymieszania talii kart do gry za pomocą tasowania riffle.

Brad Mann omija kilka różnych modeli matematycznych, w tym łańcuchy Markowa, i dochodzi do następującego wniosku:

Jest to w przybliżeniu 11,7 dla n = 52, co oznacza, że ​​zgodnie z tym punktem widzenia oczekujemy, że do losowania prawdziwej talii kart potrzeba średnio 11 lub 12 przetasowań. Pamiętaj, że jest to znacznie więcej niż 7.

Brad Mann właśnie niezależnie zweryfikował wynik stachyry, a nie mój. Spojrzałem więc bliżej na moje dane i odkryłem, dlaczego 7 przetasowań nie jest wystarczających. Po pierwsze, teoretyczna maksymalna entropia Shannona w bitach dla dowolnej karty w talii to log (52) / log (2) ~ = 5,7 bitów. Ale moje dane nigdy tak naprawdę nie łamią się znacznie powyżej 5 bitów. Co ciekawe, stworzyłem tablicę 52 elementów w Pythonie, przetasowałem tę tablicę:

>>> 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]

Obliczenie entropii na kartę daje około 4,8 bitów. Wykonanie tego kilkanaście razy pokazuje podobne wyniki w zakresie od 5,2 do 4,6 bitów, przy średniej od 4,8 do 4,9. Więc spojrzenie na surową wartość entropii moich danych nie wystarczy, w przeciwnym razie mógłbym to nazwać dobrą przy 5 losowych losach.

Kiedy przyglądam się bliżej moim danym, zauważyłem liczbę „zerowych segmentów”. Są to segmenty, w których nie ma danych dotyczących różnic między powierzchniami kart dla tego numeru. Na przykład, odejmując wartość dwóch sąsiednich kart, nie ma wyniku „15” po obliczeniu wszystkich 52 delt.

Widzę, że ostatecznie ustala się około 17-18 „zerowych wiader” około 11-12 przetasowań. Rzeczywiście, moja tasowana talia za pomocą Pythona wynosi średnio 17–18 „zero wiader”, z wysokim 21 i niskim 14. Dlaczego 17-18 jest ustalonym wynikiem, nie potrafię wyjaśnić… jeszcze. Wygląda jednak na to, że chcę zarówno ~ 4,8 bitów entropii ORAZ 17 „zerowych koszy”.

Z moim tasowaniem karabinu podstawowego to 11-12 przetasowań. W moim przypadku „cut and shuffle” to 6-7. Jeśli chodzi o gry, polecam cut-and-shuffles. Gwarantuje to nie tylko, że górne i dolne karty mieszają się w talii przy każdym tasowaniu, ale jest też po prostu szybsze niż 11-12 tasowań. Nie wiem o tobie, ale kiedy gram w gry karciane z rodziną i przyjaciółmi, nie są oni wystarczająco cierpliwi, aby wykonać 12 losowych riffów.