Jak udowodnić poprawność algorytmu losowego?

24

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.

edA-qa mort-ora-y
źródło
Możesz wykonać próbkę statystyczną na dużej liczbie przebiegów algorytmu i porównać ją z oczekiwaną wartością lub wykonać na niej jakiś test losowości.
Dave Clarke
Chcesz przetestować dystrybucję. Czy jest równomiernie rozłożony, czy przekrzywiony. Podejrzewam jednak, że trzeba by go uruchamiać wiele razy.
Dave Clarke
Nie jestem pewien, jak bym to zrobił. Nie chodzi o losowość treści, ale o losowość kolejności. Które podejście może mierzyć rozkład zamówienia?
edA-qa mort-ora-y
Ach, głupie ja, mógłbym użyć stałego zestawu danych wejściowych i użyć końcowej pozycji każdego elementu, aby uzyskać rozkład. Mimo to wolałbym bardziej logiczny dowód niż symulację.
edA-qa mort-ora-y
@ edA-qamort-ora-y: Twoje życzenie jest dla mnie rozkazem. ;)
Raphael

Odpowiedzi:

22

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 .1n+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.nn+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

πPermnPr(L=π)=1n!i=1n j=1nPr(Li=j)=1n(1)

gdzie i zakładamy dla uproszczenia, że ​​wstawiamy { 1 , , n } do listy.n=|L|{1,,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{1,,n}j{1,,n}
  2. Jeden z elementów na liście, zamieniony, tj. i j { 1 , , n }i=n+1j{1,,n}
  3. Nowy element, tj. i j = n + 1i{1,,n+1}j=n+1

Dla każdego przypadku obliczamy prawdopodobieństwo, że element będzie w pozycji i ; wszystkie muszą być 1ji (co jest wystarczające z powodu(1)). Niechpn=11n+1(1) oznacza prawdopodobieństwo, że jeden z pierwszychnelementów znajdzie się w dowolnej pozycji na starej liście (hipoteza indukcyjna), aps=1pn=1nn 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.ps=1n+1random_itemn

Pr(Li=j,i swapped)=Pr(Li=j)Pr(i swapped)=pnps

dla . Teraz do obliczeń.i,j{1,,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 njii

    .Pr(Li=j)=pn(1ps)=1nnn+1=1n+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 znaczyjjii

    .Pr(Ln+1=j)=i=1npnps=i=1n1n1n+1=1n+1

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

    .Pr(Li=j)=ps=1n+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_itemL(k){1,,k}

πPermn+1{1,,n+1}

π=(π(1),π(2),,π(i1),n+1,π(i+1),,π(n),π(i))

πPermni{1,,n+1}Pr(L(n)=π)=1n!random_itemi1n+1πi

Pr(L(n+1)=π)=Pr(L(n)=π)Pr(i swapped)=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)}140
Raphael
źródło
4
„Zauważ, że permutacja jest wybierana jednolicie, jeśli każdy element ma równe prawdopodobieństwo bycia w każdej pozycji” - to nieprawda. Na przykład zestaw czterech permutacji na czterech elementach {(1, 2, 3, 4), (2, 3, 4, 1), (3, 4, 1, 2), (4, 1, 2, 3 )} spełnia twoje ograniczenia, ale oczywiście nie jest zbiorem wszystkich permutacji. Niestety musisz użyć globalnych właściwości swojej permutacji, ponieważ żadne warunki lokalne nie są wystarczające, aby określić jednorodność.
Steven Stadnicki