Jest to kontynuacja pytania Stackoverflow o losowe tasowanie tablicy .

Istnieją ustalone algorytmy (takie jak Knuff-Fisher-Yates Shuffle ), których należy używać do tasowania tablicy, zamiast polegać na „naiwnych” implementacjach ad-hoc.

Jestem teraz zainteresowany udowodnieniem (lub obaleniem), że mój naiwny algorytm jest uszkodzony (jak w: nie generuje wszystkich możliwych permutacji z jednakowym prawdopodobieństwem).

Oto algorytm:

Zapętl kilka razy (powinna wystarczyć długość tablicy), a przy każdej iteracji uzyskaj dwa losowe indeksy tablicy i zamień tam dwa elementy.

Oczywiście wymaga to więcej liczb losowych niż KFY (dwa razy więcej), ale czy oprócz tego działa poprawnie? A jaka byłaby odpowiednia liczba iteracji (czy „długość tablicy” jest wystarczająca)?

Jest zepsuty, chociaż jeśli wykonasz wystarczającą liczbę przetasowań, może to być doskonałe przybliżenie (jak wskazały poprzednie odpowiedzi).

Aby zrozumieć, co się dzieje, zastanów się, jak często twój algorytm będzie generował przetasowania tablicy elementów, w której ustalony jest pierwszy element, . Gdy permutacje są generowane z jednakowym prawdopodobieństwem, powinno to nastąpić czasu. Niech będzie względną częstotliwością tego zdarzenia po tasowaniu algorytmu. Bądźmy również hojni i załóżmy, że tak naprawdę losowo wybierasz różne pary indeksów losowo dla swoich tasowań, aby każda para została wybrana z prawdopodobieństwem =k ≥ 2 1 / k p n n 1 / ($k$$k \ge 2$$1/k$$p_n$$n$ 2/(k(k-1)$1/{k \choose 2}$$2/\left( k (k-1) \right)$. (Oznacza to, że nie marnuje się „trywialnych” przetasowań. Z drugiej strony całkowicie psuje algorytm tablicy dwuelementowej, ponieważ na przemian ustawiasz dwa elementy i zamieniasz je, więc jeśli zatrzymasz się po z góry określonej liczbie kroki, nie ma żadnej losowości wyniku!)

Ta częstotliwość spełnia prostą rekurencję, ponieważ pierwszy element znajduje się w swoim pierwotnym miejscu po tasowaniu na dwa rozłączne sposoby. Jednym z nich jest to, że zostało to naprawione po przetasowaniach, a następne losowanie nie przenosi pierwszego elementu. Drugi polega na tym, że został przesunięty po tasowaniu, ale tasowanie przesuwa go z powrotem. Szansa na brak przesunięcia pierwszego elementu wynosi = , natomiast szansa na cofnięcie pierwszego elementu do tyłu wynosi = . Skąd:n n n + 1 s t ( k - $n+1$$n$$n$$n+1^{st}$ (k-2)/k1/ (${k-1 \choose 2}/{k \choose 2}$$(k-2)/k$ 2/(k(k-1)$1/{k \choose 2}$$2/\left( k (k-1) \right)$

Rozwiązaniem jest

Odejmując , widzimy, że częstotliwość jest niepoprawna przez . Dla dużych i dobrym przybliżeniem jest . To pokazuje, że błąd na tej konkretnej częstotliwości spadnie wykładniczo wraz z liczbą zamian w stosunku do rozmiaru tablicy ( ), co oznacza, że ​​będzie trudny do wykrycia przy dużych tablicach, jeśli dokonałeś względnie dużej liczby zamian - ale błąd zawsze występuje.( k - $1/k$ knk-$\left( \frac{k-3}{k-1} \right) ^n \frac{k-1}{k}$$k$$n$n/$\frac{k-1}{k} \exp(-\frac{2n}{k-1})$$n/k$

Trudno jest zapewnić kompleksową analizę błędów na wszystkich częstotliwościach. Jest jednak prawdopodobne, że będą się tak zachowywać, co pokazuje, że potrzeba co najmniej (liczby swapów), aby był wystarczająco duży, aby błąd był akceptowalnie mały. Przybliżone rozwiązanie to$n$

gdzie powinien być bardzo mały w porównaniu do . Oznacza to, że powinno być kilka razy dla nawet przybliżonych przybliżeń ( tj. Gdzie jest rzędu razy lub tak.)1 / k n k $\epsilon$$1/k$$n$$k$$\epsilon$1 /$0.01$$1/k$

Wszystko to nasuwa pytanie: dlaczego miałbyś wybrać algorytm, który nie jest całkiem (ale tylko w przybliżeniu) poprawny, stosuje dokładnie takie same techniki jak inny algorytm, który jest możliwy do udowodnienia, a jednak wymaga więcej obliczeń?

Edytować

Komentarz Thilo jest trafny (i miałem nadzieję, że nikt nie zwróci na to uwagi, więc mógłbym oszczędzić tej dodatkowej pracy!). Pozwól mi wyjaśnić logikę.

• Jeśli za każdym razem generujesz rzeczywiste swapy, jesteś kompletnie spieprzony. Problem, który wskazałem dla przypadku obejmuje wszystkie tablice. Tylko połowę wszystkich możliwych permutacji można uzyskać, stosując parzystą liczbę zamian; drugą połowę uzyskuje się przez zastosowanie nieparzystej liczby zamian. Dlatego w tej sytuacji nigdy nie można wygenerować nigdzie w pobliżu jednolitego rozkładu permutacji (ale istnieje tak wiele możliwych, że badanie symulacyjne dla każdego znacznego nie będzie w stanie wykryć problemu). To naprawdę źle.$k=2$$k$

• Dlatego mądrze jest generować swapy losowo, generując dwie pozycje niezależnie losowo. Oznacza to, że istnieje szansa każdym razem, gdy element zostanie zamieniony; to znaczy nie robić nic. Ten proces skutecznie spowalnia nieco algorytm: po krokach spodziewamy się tylko prawdziwych zamian.n k - $1/k$$n$$\frac{k-1}{k} N \lt N$

• Zauważ, że rozmiar błędu zmniejsza się monotonicznie wraz z liczbą wyraźnych zamian. Dlatego też przeprowadzenie mniejszej liczby swapów również średnio zwiększa błąd. Ale jest to cena, którą powinieneś zapłacić, aby rozwiązać problem opisany w pierwszym punkcie. W związku z tym moje oszacowanie błędu jest konserwatywnie niskie, w przybliżeniu o współczynnik .$(k-1)/k$

Chciałem również wskazać interesujący pozorny wyjątek: dokładne przyjrzenie się formule błędu sugeruje, że nie ma błędu w przypadku . To nie jest pomyłka: jest poprawna. Jednak tutaj zbadałem tylko jedną statystykę związaną z jednolitym rozkładem permutacji. Fakt, że algorytm może odtworzyć tę jedną statystykę, gdy (czyli uzyskanie odpowiedniej częstotliwości permutacji, które ustalają dowolną pozycję), nie gwarantuje, że permutacje rzeczywiście zostały rozmieszczone równomiernie. Rzeczywiście, po rzeczywistych zamianach, jedynymi możliwymi kombinacjami, które można wygenerować, są ,k = 3 2 n ( 123 ) ( 321 ) 2 n + 1 ( 12 $k=3$$k=3$$2n$$(123)$$(321)$i tożsamość. Tylko ta ostatnia naprawia dowolną pozycję, a więc dokładnie jedna trzecia permutacji naprawia pozycję. Ale brakuje połowy permutacji! W innym przypadku, po rzeczywistych zamianach , jedynymi możliwymi kombinacjami są , i . Ponownie dokładnie jedna z nich naprawi dowolną pozycję, więc ponownie uzyskujemy prawidłową częstotliwość permutacji ustalających tę pozycję, ale ponownie uzyskujemy tylko połowę możliwych permutacji.$2n+1$$(12)$$(23)$$(13)$

Ten mały przykład pomaga ujawnić główne wątki argumentu: będąc „hojnymi” zachowawczo nie doceniamy poziomu błędu dla jednej konkretnej statystyki. Ponieważ ten poziom błędu jest niezerowy dla wszystkich , widzimy, że algorytm jest uszkodzony. Ponadto, analizując zanik wskaźnika błędów dla tej statystyki, ustalamy dolną granicę liczby iteracji algorytmu potrzebnych do uzyskania jakiejkolwiek nadziei na przybliżenie jednolitego rozkładu permutacji.$k \ge 4$

Myślę, że twój prosty algorytm poprawnie przetasuje karty, gdy liczba tasuje się w nieskończoność.

Załóżmy, że masz trzy karty: {A, B, C}. Załóż, że Twoje karty zaczynają się w następującej kolejności: A, B, C. Następnie po jednym losowaniu masz następujące kombinacje:

{A,B,C}, {A,B,C}, {A,B,C} #You get this if choose the same RN twice.
{A,C,B}, {A,C,B}
{C,B,A}, {C,B,A}
{B,A,C}, {B,A,C}

Dlatego prawdopodobieństwo, że karta A będzie w pozycji {1,2,3}, wynosi {5/9, 2/9, 2/9}.

Jeśli przetasujemy karty po raz drugi, wówczas:

Pr(A in position 1 after 2 shuffles) = 5/9*Pr(A in position 1 after 1 shuffle) 
                                     + 2/9*Pr(A in position 2 after 1 shuffle) 
                                     + 2/9*Pr(A in position 3 after 1 shuffle) 

Daje to 0,407.

Korzystając z tego samego pomysłu, możemy utworzyć relację powtarzalności, tj .:

Pr(A in position 1 after n shuffles) = 5/9*Pr(A in position 1 after (n-1) shuffles) 
                                     + 2/9*Pr(A in position 2 after (n-1) shuffles) 
                                     + 2/9*Pr(A in position 3 after (n-1) shuffles).

Kodowanie tego w R (patrz kod poniżej), daje prawdopodobieństwo, że karta A znajdzie się w pozycji {1,2,3} jako {0.33334, 0.33333, 0.33333} po dziesięciu tasowaniach.

Kod R.

## m is the probability matrix of card position
## Row is position
## Col is card A, B, C
m = matrix(0, nrow=3, ncol=3)
m[1,1] = 1; m[2,2] = 1; m[3,3] = 1

## Transition matrix
m_trans = matrix(2/9, nrow=3, ncol=3)
m_trans[1,1] = 5/9; m_trans[2,2] = 5/9; m_trans[3,3] = 5/9

for(i in 1:10){
  old_m = m
  m[1,1] = sum(m_trans[,1]*old_m[,1])
  m[2,1] = sum(m_trans[,2]*old_m[,1])
  m[3,1] = sum(m_trans[,3]*old_m[,1])

  m[1,2] = sum(m_trans[,1]*old_m[,2])
  m[2,2] = sum(m_trans[,2]*old_m[,2])
  m[3,2] = sum(m_trans[,3]*old_m[,2])

  m[1,3] = sum(m_trans[,1]*old_m[,3])
  m[2,3] = sum(m_trans[,2]*old_m[,3])
  m[3,3] = sum(m_trans[,3]*old_m[,3])
}  
m

$1/n!$$t$$A/n^{2t}$$A$$1/n! = A/n^{2t}$$n^{2t}/n! = A$$n \ge 3$$n$$n^{2t}/n!$$n!$$n=52$$1/52!$$3, 5, 7, ..., 47$$1/52^{2t}$$A/52^{2t}$$1/52!$

Ile potrzebujesz, aby dobrze oszacować przypadkową permutację? Generowanie losowej permutacji przez losowe transpozycje przeanalizowali Diaconis i Shahshahani, stosując teorię reprezentacji grupy symetrycznej w

Diaconis, P., Shahshahani, M. (1981): „Generowanie losowej permutacji z losowymi transpozycjami”. Z. Wahrsch. Verw. Geb. 57, 159–179.

$\frac 12 n \log n$$(1-\epsilon) \frac12 n \log n$$(1+\epsilon) \frac 12 n \log n$$L^2$$7$

Pamiętaj, że nie jestem statystykiem, ale postawię moje 2 centy.

Zrobiłem mały test w R (ostrożnie, jest bardzo wolny na wysoki numTrials, kod można prawdopodobnie zoptymalizować):

numElements <- 1000
numTrials <- 5000

swapVec <- function()
    {
    vec.swp <- vec

    for (i in 1:numElements)
        {
        i <- sample(1:numElements)
        j <- sample(1:numElements)

        tmp <- vec.swp[i]
        vec.swp[i] <- vec.swp[j]
        vec.swp[j] <- tmp
        }

    return (vec.swp)
    }

# Create a normally distributed array of numElements length
vec <- rnorm(numElements)

# Do several "swapping trials" so we can make some stats on them
swaps <- vec
prog <- txtProgressBar(0, numTrials, style=3)

for (t in 1:numTrials)
    {
    swaps <- rbind(swaps, swapVec())
    setTxtProgressBar(prog, t)
    }

To wygeneruje macierz swapsz numTrials+1wierszami (po jednym na próbę + oryginał) i numElementskolumnami (po jednym na każdy element wektorowy). Jeśli metoda jest poprawna, rozkład każdej kolumny (tj. Wartości dla każdego elementu w ramach prób) nie powinien różnić się od rozkładu oryginalnych danych.

Ponieważ nasze oryginalne dane były normalnie dystrybuowane, spodziewalibyśmy się, że wszystkie kolumny nie odbiegają od tego.

Jeśli uciekniemy

par(mfrow= c(2,2))
# Our original data
hist(swaps[1,], 100, col="black", freq=FALSE, main="Original")
# Three "randomly" chosen columns
hist(swaps[,1], 100, col="black", freq=FALSE, main="Trial # 1") 
hist(swaps[,257], 100, col="black", freq=FALSE, main="Trial # 257")
hist(swaps[,844], 100, col="black", freq=FALSE, main="Trial # 844")

Otrzymujemy:

co wygląda bardzo obiecująco. Teraz, jeśli chcemy statystycznie potwierdzić, że rozkłady nie odbiegają od oryginału, myślę, że moglibyśmy zastosować test Kołmogorowa-Smirnowa (proszę, czy jakiś statystyk może potwierdzić, że to prawda?) I zrobić, na przykład

ks.test(swaps[1, ], swaps[, 234])

Co daje nam p = 0,9926

Jeśli sprawdzimy wszystkie kolumny:

ks.results <- apply(swaps, 2, function(col){ks.test(swaps[1,], col)})
p.values <- unlist(lapply(ks.results, function(x){x$p.value})

I biegniemy

hist(p.values, 100, col="black")

otrzymujemy:

Tak więc, dla większości elementów tablicy, twoja metoda zamiany dała dobry wynik, jak widać również patrząc na kwartyle.

1> quantile(p.values)
       0%       25%       50%       75%      100% 
0.6819832 0.9963731 0.9999188 0.9999996 1.0000000

Pamiętaj, że oczywiście przy mniejszej liczbie prób sytuacja nie jest tak dobra:

50 prób

1> quantile(p.values)
          0%          25%          50%          75%         100% 
0.0003399635 0.2920976389 0.5583204486 0.8103852744 0.9999165730

100 prób

          0%         25%         50%         75%        100% 
 0.001434198 0.327553996 0.596603804 0.828037097 0.999999591 

500 prób

         0%         25%         50%         75%        100% 
0.007834701 0.504698404 0.764231550 0.934223503 0.999995887 

Oto jak interpretuję twój algorytm w pseudo kodzie:

void shuffle(array, length, num_passes)
  for (pass = 0; pass < num_passes; ++pass) 
    for (n = 0; n < length; ++)
      i = random_in(0, length-1)
      j = random_in(0, lenght-1)
      swap(array[i], array[j]

$2 \times length \times num\_passes$$[0, length-1]$$length$

$length ^ {2 \times length \times num\_passes}$

$length !$$length ! < length ^ {2 \times length \times num\_passes}$

$length ! \bigm| length ^ {2 \times length \times num\_passes}$

$p$$p < length$$p \nmid length$$length > 2$$p \bigm| length!$$length ^ {2 \times length \times num\_passes}$$length ! \nmid length ^ {2 \times length \times num\_passes}$$length > 2$

$length$$p < length$$length-1$$length-1$$length$

$length$$length-1$$length !$$length! \bigm| length!$. Nietrudno wykazać, że każdy ślad powoduje inną permutację, a stamtąd łatwo zauważyć, że Fisher-Yates generuje każdą permutację z jednakowym prawdopodobieństwem.