Co jest złego w tym „naiwnym” algorytmie tasowania?

23

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

Thilo
źródło
4
Po prostu nie rozumiem, dlaczego ludzie myślą, że ta zamiana jest „prostsza” lub „bardziej naiwna” niż FY ... Kiedy rozwiązałem ten problem po raz pierwszy, właśnie wdrożyłem FY (nie wiedząc, że ma nawet nazwę) tylko dlatego, że wydawał mi się to najprostszym sposobem.
1
@mbq: osobiście uważam je za równie łatwe, chociaż zgadzam się, że FY wydaje mi się bardziej „naturalna”.
nico
3
Kiedy badałem algorytmy tasowania po napisaniu własnego (praktyka, którą porzuciłem odtąd), byłem cały „cholera, już to zrobiono i ma nazwę !!”
JM nie jest statystykiem

Odpowiedzi:

12

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 / ( kkk2)1/kpnn 2/(k(k-1))1/(k2))2)/(k(k-1)). (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 - 1n+1nnn+1st (k-2)/k1/ ( k(k-12))/(k2))(k-2))/k 2/(k(k-1))1/(k2))2/(k(k1))

p0=1
ponieważ pierwszy element zaczyna się na swoim właściwym miejscu;

pn+1=k2kpn+2k(k1)(1pn).

Rozwiązaniem jest

pn=1/k+(k3k1)nk1k.

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 - 31/k knk-1(k3k1)nk1kknn/kk1kexp(2nk1)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 ton

n>12(1(k1)log(ϵ))

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 ϵϵ1/knkϵ1 / k0.011/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.kk=2k

  • 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 - 11/knk1kN<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 .(k1)/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=3k=32n(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.k4

Whuber
źródło
1
„Bądźmy również hojni i załóżmy, że tak naprawdę losowo wybierasz różne pary indeksów dla losowego losowania”. Nie rozumiem, dlaczego można przyjąć takie założenie i jak jest ono hojne. Wydaje się, że odrzuca możliwe permutacje, co powoduje jeszcze mniej losowy rozkład.
Thilo,
1
@Thilo: Dziękuję. Twój komentarz zasługuje na rozszerzoną odpowiedź, więc umieściłem go w samej odpowiedzi. Zaznaczę tutaj, że bycie „hojnym” tak naprawdę nie odrzuca żadnych permutacji: po prostu eliminuje kroki w algorytmie, które w przeciwnym razie nic by nie zrobiły.
whuber
2
Problem ten można w pełni przeanalizować jako łańcuch Markowa na wykresie Cayleya grupy permutacji. Obliczenia numeryczne dla k = 1 do 7 (macierz 5040 na 5040!) Potwierdzają, że największe wartości własne wielkości (po 1 i -1) wynoszą dokładnie . Oznacza to, że po rozwiązaniu problemu naprzemiennego znaku permutacji (odpowiadającego wartości własnej -1), błędy we wszystkich prawdopodobieństwach zanikają w tempie lub szybciej. Podejrzewam, że nadal obowiązuje to dla wszystkich większych . (k3)/(k1)=12/(k1)(12/(k1))nk
whuber
1
Możesz zrobić znacznie lepiej niż ponieważ prawdopodobieństwa są niezmienne w klasach koniugacji, a istnieje tylko partycji więc zamiast tego możesz analizować macierz . 5040×504015715×15
Douglas Zare
8

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
csgillespie
źródło
1
+1. To pokazuje, że prawdopodobieństwo, że dana karta znajdzie się na danej pozycji, jest zbliżone do oczekiwanego współczynnika wraz ze wzrostem liczby przetasowań. To samo dotyczy również algorytmu, który po prostu obraca tablicę jeden raz o losową liczbę: wszystkie karty mają jednakowe prawdopodobieństwo, że znajdą się na wszystkich pozycjach, ale losowość w ogóle nie występuje (tablica pozostaje posortowana).
Thilo,
@Thilo: Przepraszam, nie śledzę twojego komentarza. „Algorytm obraca się o losową liczbę”, ale nadal nie ma „losowości”? Czy możesz wyjaśnić dalej?
csgillespie
Jeśli „losowo” macierz N-elementów, obracając ją między pozycjami 0 i N-1 (losowo), wówczas każda karta ma dokładnie takie samo prawdopodobieństwo, że skończy w dowolnej z N pozycji, ale 2 zawsze znajduje się między 1 i 3.
Thilo
1
@Thio: Ach, rozumiem o co ci chodzi. Cóż, możesz obliczyć prawdopodobieństwo (stosując dokładnie ten sam pomysł jak powyżej), dla Pr (A w pozycji 2) i Pr (A w pozycji 3) - dito dla kart B i C. Zobaczysz, że wszystkie prawdopodobieństwa mają tendencję do 1/3 Uwaga: moja odpowiedź podaje tylko konkretny przypadek, podczas gdy @whuber ładna odpowiedź podaje ogólny przypadek.
csgillespie
4

1/n!tA/n2tA1/n!=A/n2tn2t/n!=An3nn2t/n!n!n=521/52!3,5,7,...,471/522tA/522t1/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.

12nlogn(1ϵ)12nlogn(1+ϵ)12nlognL27

Douglas Zare
źródło
2

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:

Histogramy prób losowych

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:

Histogram wartości p testu Kołmogorowa-Smirnowa

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 
Nico
źródło
0

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×length×num_passes[0,length1]length

length2×length×num_passes

lminsolth!lminsolth!<lminsolth2)×lminsolth×num_pzassmis

lminsolth!|lminsolth2)×lminsolth×num_pzassmis

pp<lminsolthplminsolthlminsolth>2)p|lminsolth!lminsolth2)×lminsolth×num_pzassmislength!length2×length×num_passeslength>2

lengthp<lengthlength1length1length

lengthlength1length!length!|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.

tzs
źródło