Tasowanie może wyglądać losowo, a mimo to faworyzować część układów
Nie wystarczy wielokrotnie zamieniać każdej karty z „losową kartą”, aby otrzymać uczciwe tasowanie. Łatwo napisać pętlę, która daje różnym permutacjom różne prawdopodobieństwa, choć wynik na oko wygląda chaotycznie. Fisher–Yates unika tego problemu: na kolejnych pozycjach wybiera równomiernie jeden z elementów, które nie zostały jeszcze ustalone, i zamienia go na bieżącą pozycję. W efekcie każda z N! permutacji ma tę samą szansę, zakładając poprawne losowanie indeksów. Dla N=3 można też szybko udowodnić błąd popularnej naiwnej metody: 3³=27 równoprawdopodobnych ciągów wyborów nie da się podzielić równo między 3!=6 permutacji.
Chaos wizualny nie jest dowodem równomierności
Programista chce potasować tablicę. Naturalny pomysł: przejdź po każdym indeksie i zamień jego element z elementem na losowej pozycji z całej tablicy. Po kilku takich zamianach wynik wygląda przypadkowo. Problem w tym, że „wygląda przypadkowo” nie oznacza, że każda permutacja jest równie prawdopodobna.
Dla trzech elementów naiwna pętla wykonująca trzy niezależne wybory spośród trzech pozycji ma 3³=27 możliwych sekwencji decyzji, jeśli każda jest równie prawdopodobna. Tymczasem istnieje 3!=6 końcowych permutacji. Ponieważ 27 nie dzieli się przez 6, nie da się przypisać każdej permutacji tej samej liczby sekwencji wyborów. Już sama arytmetyka dowodzi, że taki wariant nie może być idealnie równomierny.
Fisher–Yates ustala jedną pozycję naraz
W nowoczesnej wersji algorytmu Fishera–Yatesa przechodzimy np. od końca tablicy. Dla pozycji i losujemy j równomiernie z zakresu 0..i i zamieniamy elementy i oraz j. Po tej operacji pozycja i jest ustalona i już do niej nie wracamy. Następnie wykonujemy to samo dla i-1.
NIST opisuje równoważną wersję jako zamienianie każdego elementu z losowym elementem należącym do jeszcze nieustalonego zakresu. Algorytm działa w czasie liniowym. Kluczowe jest zwężanie obszaru losowania: pierwszy wybór ma N możliwości, następny N-1, potem N-2 i tak dalej. Liczba możliwych ścieżek wynosi dokładnie N!, tak jak liczba permutacji.
Każda permutacja ma jedną odpowiadającą jej historię wyborów
Równomierność można zobaczyć konstrukcyjnie. Na ostatniej pozycji każdy z N elementów ma szansę 1/N. Po jej ustaleniu na przedostatniej każdy z pozostałych N-1 elementów ma szansę 1/(N-1), potem 1/(N-2) i tak dalej. Konkretna końcowa permutacja odpowiada jednej konkretnej sekwencji wyborów i ma prawdopodobieństwo 1/N · 1/(N-1) · ... · 1/2 = 1/N!.
Richard Durstenfeld opublikował w 1964 roku komputerową wersję efektywnego algorytmu losowej permutacji; NIST odwołuje się także do wcześniejszej metody Fishera i Yatesa. W informatyce nazwa Fisher–Yates zwykle obejmuje właśnie rodzinę tych równomiernych tasowań.
Algorytm może być poprawny, a losowanie nadal zepsute
Dowód Fishera–Yatesa zakłada, że wybrany indeks jest naprawdę równomierny w wymaganym zakresie. Jeśli program generuje indeks przez błędne `random_value % m`, a liczba możliwych wartości generatora nie jest wielokrotnością m, może pojawić się tzw. modulo bias. Również generator o zbyt małym stanie nie będzie w stanie osiągnąć wszystkich permutacji bardzo dużej tablicy.
Dlatego „użyłem Fisher–Yatesa” nie kończy audytu losowości. Trzeba jeszcze sprawdzić generator i sposób mapowania jego wyjścia na zakres. To dobra lekcja z programowania probabilistycznego: poprawność rozkładu jest własnością całego łańcucha decyzji, a nie tylko wyglądu pseudokodu.
Jedna drobna zmiana zakresu losowania zmienia cały rozkład
Najłatwiej zepsuć tasowanie przez pomylenie dwóch bardzo podobnych pętli. W Fisherze–Yatesie dla pozycji i losujemy tylko z jeszcze nieustalonego zakresu 0…i. Jeśli zamiast tego za każdym razem losujemy ze wszystkich N pozycji, liczba możliwych historii wyborów wynosi N^N, a nie N!. Dla N=3 mamy 27 równoprawdopodobnych historii i 6 permutacji, więc nie mogą one dostać identycznej liczby historii. Kod nadal wykonuje zamiany, wygląda chaotycznie i może przechodzić powierzchowne testy. Równomierność jest jednak własnością matematycznego rozkładu, a nie wizualnego nieporządku. Dlatego testowanie algorytmów losowych wymaga sprawdzania prawdopodobieństw, nie tylko kilku przykładowych wyników.
Małe przypadki potrafią bezlitośnie ujawnić błąd probabilistyczny
Algorytmy losowe warto testować inaczej niż zwykłe funkcje deterministyczne. Dla trzech lub czterech elementów można enumerować wszystkie możliwe sekwencje wyborów i policzyć, z jaką częstością prowadzą do każdej permutacji. W naiwnej wersji od razu widać nierówny rozkład; w poprawnym Fisherze–Yatesie każda permutacja ma tę samą liczbę odpowiadających jej ścieżek losowania. Taki test nie zastępuje dowodu dla dowolnego N, ale jest świetnym narzędziem diagnostycznym. Błąd probabilistyczny może nie ujawnić się w pojedynczym uruchomieniu — wynik zawsze „wygląda jak tasowanie”. Dopiero rozkład wielu wyników pokazuje, czy niektóre układy są systematycznie uprzywilejowane. W tym sensie poprawność algorytmu losowego obejmuje nie tylko zbiór możliwych odpowiedzi, lecz także ich prawdopodobieństwa.