Jak udowodnić poprawność algorytmu losowego?

Mam dwa sposoby tworzenia listy przedmiotów w losowej kolejności i chciałbym ustalić, czy są one równie uczciwe (obiektywne).

Pierwszą metodą, której używam, jest skonstruowanie całej listy elementów, a następnie wykonanie losowania (powiedzmy losowanie Fisher-Yates). Druga metoda jest raczej metodą iteracyjną, która utrzymuje losowość listy przy każdym wstawieniu. W pseudokodzie funkcja wstawiania to:

insert( list, item )
    list.append( item )
    swap( list.random_item, list.last_item )

Interesuje mnie, jak można pokazać uczciwość tego konkretnego przetasowania. Zalety tego algorytmu, jeśli jest używany, są wystarczające, aby nawet jeśli byłoby nieco niesprawiedliwe, byłoby w porządku. Aby zdecydować, potrzebuję sposobu na ocenę jego uczciwości.

Moim pierwszym pomysłem jest to, że muszę obliczyć całkowitą permutację możliwą w ten sposób w porównaniu do całkowitej permutacji możliwej dla zestawu ostatecznej długości. Nie jestem jednak pewien, jak obliczyć permutacje wynikające z tego algorytmu. Nie mogę też mieć pewności, że jest to najlepsze lub najłatwiejsze podejście.

Najpierw stwórzmy dwa, być może oczywiste, ale ważne założenia:

1. _.random_item może wybrać ostatnią pozycję.
2. _.random_itemwybiera każdą pozycję z prawdopodobieństwem .$\frac{1}{n+1}$

Aby udowodnić poprawność algorytmu, potrzebujesz argumentu indukcyjnego podobnego do zastosowanego tutaj :

• W przypadku listy singletonów istnieje tylko jedna możliwość, dlatego jest ona wybierana jednolicie.
• Zakładając, że lista z elementami została wybrana jednolicie (ze wszystkich permutacji), pokaż, że ta z n + 1 elementami uzyskanymi za pomocą twojej techniki jest jednolicie wybrana.$n$$n+1$

^{Odtąd dowód jest błędny. Poniżej znajduje się poprawny dowód; Zostawiam to tutaj, ponieważ zarówno błąd, jak i następujące kroki (które są rozsądne) mogą być pouczające.}

Przydatne jest wyprowadzenie lokalnej (tj. Elementowej) właściwości, która musi zostać zachowana, ponieważ kłótnie o całą permutację są bolesne. Zauważ, że permutacja jest wybierana równomiernie, jeśli każdy element ma równe prawdopodobieństwo bycia w każdej pozycji, tj

$\qquad \displaystyle \mathop{\forall}\limits_{\pi \in \mathrm{Perm}_n} \operatorname{Pr}(L = \pi) = \frac{1}{n!} \quad \Longleftrightarrow \quad \mathop{\forall}\limits_{i=1}^n\ \mathop{\forall}\limits_{j=1}^n \operatorname{Pr}(L_i = j) = \frac{1}{n} \qquad (1)$

gdzie i zakładamy dla uproszczenia, że ​​wstawiamy { 1 , … , n } do listy.$n = |L|$$\{1,\dots,n\}$

Zobaczmy teraz, co robi Twoja technika przy wstawianiu elementu . Musimy rozważyć trzy przypadki (po zamianie):$n+1$

1. Jeden z elementów na liście, nie zamieniony, tj. i j ∈ { 1 , … , n $i \in \{1,\dots,n\}$$j \in \{1,\dots,n\}$
2. Jeden z elementów na liście, zamieniony, tj. i j ∈ { 1 , … , n $i = n+1$$j \in \{1,\dots,n\}$
3. Nowy element, tj. i j = n + $i \in \{1,\dots,n+1\}$$j = n+1$

Dla każdego przypadku obliczamy prawdopodobieństwo, że element będzie w pozycji i ; wszystkie muszą być $j$$i$ (co jest wystarczające z powodu(1)). Niechpn=$\frac{1}{n+1}$$(1)$ oznacza prawdopodobieństwo, że jeden z pierwszychnelementów znajdzie się w dowolnej pozycji na starej liście (hipoteza indukcyjna), aps=$p_n = \frac{1}{n}$$n$ prawdopodobieństwo, że dowolna pozycja zostanie wybrana przez(założenia 1, 2). Zwróć uwagę, że coice listy zelementamini wybranie pozycji zamiany sązdarzeniami niezależnymi, więc prawdopodobieństwo czynników wspólnych zdarzeń, np.$p_s = \frac{1}{n+1}$random_item$n$

$\qquad \displaystyle \operatorname{Pr}(L_i=j, i \text{ swapped}) = \operatorname{Pr}(L_i=j)\cdot \operatorname{Pr}(i \text{ swapped}) = p_np_s$

dla . Teraz do obliczeń.$i,j \in \{1,\dots,n\}$

1. Bierzemy pod uwagę tylko stare elementów. Taki element J znajduje się w pozycji i tylko wtedy, gdy to było przed ostatnim wkładania oraz i nie wchodzi w położeniu wymiany, to jest $n$$j$$i$$i$

   .$\quad \displaystyle \operatorname{Pr}(L_i = j) = p_n(1-p_s) = \frac{1}{n}\cdot\frac{n}{n+1} = \frac{1}{n+1}$

2. Uważamy tutaj, że jeden ze starych elementów jest zamieniany na ostatnią pozycję. Element mógł znajdować się na dowolnej ze starych pozycji, więc sumujemy wszystkie prawdopodobieństwa, że j było na pozycji i, a i wybrano jako pozycję wymiany, to znaczy$j$$j$$i$$i$

   .$\quad \displaystyle \operatorname{Pr}(L_{n+1} = j) = \sum_{i=1}^n p_np_s = \sum_{i=1}^n \frac{1}{n}\cdot\frac{1}{n+1} = \frac{1}{n+1}$

3. Nowy element kończy się w pozycji wtedy i tylko wtedy, gdy i jest wybrane jako pozycja wymiany, to znaczy$i$$i$

   .$\quad \displaystyle \operatorname{Pr}(L_i = j) = p_s = \frac{1}{n+1}$

Wszystko okazało się dobrze, twoja strategia wstawiania rzeczywiście zachowuje jednolitość. Dzięki sile indukcji dowodzi to, że algorytm tworzy jednolicie rozmieszczone permutacje.

^{Słowo ostrzeżenia: dowód ten psuje się, jeśli wstawione elementy nie są połączone parami inaczej. rozróżnialne, ponieważ wtedy pierwsze równanie nie jest już ważne. Ale twój algorytm jest nadal aktualny; każda permutacja z duplikatami jest generowana przez tę samą liczbę losowych wykonań. Możesz to udowodnić, zaznaczając duplikaty (tzn. Czyniąc je rozróżnialnymi), wykonaj powyższy dowód i usuń oznaczenia (praktycznie); ostatni krok zwija zestawy równych rozmiarów permutacji do tego samego.}

Jak słusznie zauważył Steven w komentarzach, powyższy dowód jest zasadniczo wadliwy, ponieważ nie ma zastosowania; możesz konstruować rozkłady na zbiorze permutacji, które spełniają prawą, ale nie lewą stronę¹.$(1)$

random_item$L^{(k)}$$\{1,\dots,k\}$

$\pi' \in \mathrm{Perm}_{n+1}$$\{1,\dots,n+1\}$

$\qquad \displaystyle \pi' = (\pi(1), \pi(2), \dots, \pi(i-1), n+1, \pi(i+1), \dots, \pi(n), \pi(i))$

$\pi \in \mathrm{Perm}_n$$i \in \{1,\dots,n+1\}$$\operatorname{Pr}(L^{(n)} = \pi) = \frac{1}{n!}$random_item$i$$\frac{1}{n+1}$$\pi$$i$

$\qquad \displaystyle \operatorname{Pr}(L^{(n+1)} = \pi') = \operatorname{Pr}(L^{(n)} = \pi) \cdot \operatorname{Pr}(i \text{ swapped}) = \frac{1}{(n+1)!}$

które musieliśmy pokazać. Dzięki sile indukcji dowodzi to, że algorytm tworzy jednolicie rozmieszczone permutacje.

1. $\{(1, 2, 3, 4), (2, 3, 4, 1), (3, 4, 1, 2), (4, 1, 2, 3)\}$$\frac{1}{4}$$0$