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)?
źródło
Odpowiedzi:
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 / ( kk k ≥ 2 1 / k pn n 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 + 1 n n n + 1s t (k-2)/k1/ ( k( k-12)) / ( k2)) ( k - 2 ) / k 2/(k(k-1))1 / ( k2)) 2/(k(k−1))
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 - 31/k knk-1(k−3k−1)nk−1k k n n/kk−1kexp(−2nk−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 ton
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/k n k ϵ 1 / k0.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.kk=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 - 11/k n k−1kN<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≥4
źródło
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:
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:
Daje to 0,407.
Korzystając z tego samego pomysłu, możemy utworzyć relację powtarzalności, tj .:
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.
źródło
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.
źródło
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ć):To wygeneruje macierz
swaps
znumTrials+1
wierszami (po jednym na próbę + oryginał) inumElements
kolumnami (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
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
Co daje nam p = 0,9926
Jeśli sprawdzimy wszystkie kolumny:
I biegniemy
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.
Pamiętaj, że oczywiście przy mniejszej liczbie prób sytuacja nie jest tak dobra:
50 prób
100 prób
500 prób
źródło
Oto jak interpretuję twój algorytm w pseudo kodzie:
źródło