Twierdzenie o głosowaniu Bertranda

W kombinatoryce problem kart do głosowania Bertranda polega na pytaniu: „W wyborach , w których kandydat A otrzymuje p głosów, a kandydat B otrzymuje q głosów z p > q , jakie jest prawdopodobieństwo , że A będzie wyraźnie przed B przez cały czas liczenia?” Odpowiedź to

Wynik został po raz pierwszy opublikowany przez WA Whitwortha w 1878 roku, ale został nazwany na cześć Josepha Louisa François Bertranda , który odkrył go ponownie w 1887 roku.

W oryginalnej pracy Bertranda szkicuje dowód oparty na ogólnym wzorze na liczbę korzystnych sekwencji z wykorzystaniem relacji rekurencji . Zauważa, że ​​wydaje się prawdopodobne, że tak prosty wynik można było udowodnić bardziej bezpośrednią metodą. Dowód taki dał Désiré André , opierając się na spostrzeżeniu, że niekorzystne ciągi można podzielić na dwa równie prawdopodobne przypadki, z których jeden (przypadek, w którym B otrzymuje pierwszy głos) jest łatwy do obliczenia; dowodzi równości przez jawną bijekcję . Odmiana jego metody jest powszechnie znana jako metoda odbicia André , chociaż André nie stosował żadnych odbić. Twierdzenie o głosowaniu Bertranda jest równoważne z lematem o cyklu .

Przykład

Załóżmy, że jest 5 wyborców, z których 3 głosuje na kandydata A , a 2 na kandydata B (więc p = 3 i q = 2). Istnieje dziesięć możliwości kolejności oddanych głosów:

  • AAABB
  • AABAB
  • ABAB
  • BAAAB
  • AABBA
  • ABABA
  • BAABA
  • ABBAA
  • BABAA
  • BBAAA

W przypadku kolejności AABAB suma głosów w miarę postępu wyborów jest następująca:

Kandydat A A B A B
A 1 2 2 3 3
B 0 0 1 1 2

Dla każdej kolumny suma dla A jest zawsze większa niż suma dla B , więc A jest zawsze ściśle przed B . W przypadku porządku AABBA suma głosów w miarę postępu wyborów jest następująca:

Kandydat A A B B A
A 1 2 2 2 3
B 0 0 1 2 2

W przypadku tej kolejności B jest remisowy z A po czwartym głosowaniu, więc A nie zawsze wyprzedza B . Spośród 10 możliwych zleceń A jest zawsze przed B tylko dla AAABB i AABAB . Zatem prawdopodobieństwo, że A będzie zawsze dokładnie wyprzedzać, wynosi

równe, twierdzenie

Równoważne problemy

Zamiast obliczać prawdopodobieństwo, że losowa kolejność liczenia głosów ma pożądaną właściwość, można zamiast tego obliczyć liczbę korzystnych kolejności liczenia, a następnie podzielić przez całkowitą liczbę sposobów, na jakie można było policzyć głosy. (Jest to metoda stosowana przez Bertranda.) Całkowita liczba sposobów to współczynnik dwumianu ; Dowód Bertranda pokazuje, że liczba korzystnych zamówień, w których należy policzyć głosy, wynosi (choć nie podaje tej liczby wprost). I rzeczywiście po podzieleniu daje to .

Innym równoważnym problemem jest obliczenie liczby spacerów losowych po liczbach całkowitych składających się z n kroków o jednostkowej długości, zaczynających się w początku i kończących w punkcie m , które nigdy nie stają się ujemne. Zakładając, że n i m mają tę samą parzystość i , liczba ta wynosi

m i jest parzysta, daje to liczbę katalońską .

, że jeśli , to musi być parzysta W przeciwnym razie błądzenie losowe nie może się zakończyć na . Można to zobaczyć w następujący sposób: niech liczbą „pozytywnych” ruchów, tj. w prawo, i niech „ujemnych” ruchów, tj lewy. Ponieważ i , mamy i . Ponieważ i liczbami całkowitymi, jeśli to musi być liczbą całkowitą Innymi słowy, musi być parzysta.]

Dowód przez odbicie

Aby A był ściśle przed B podczas całego liczenia głosów, nie może być remisów. Rozdziel sekwencje liczenia według pierwszego głosowania. Każda sekwencja, która zaczyna się od głosowania na B, musi w pewnym momencie doprowadzić do remisu, ponieważ A ostatecznie wygrywa. Dla każdej sekwencji, która zaczyna się od A i kończy się remisem, odzwierciedlaj głosy aż do punktu pierwszego remisu (a więc każde A staje się B i odwrotnie), aby uzyskać sekwencję rozpoczynającą się od B. Stąd każda sekwencja rozpoczynająca się od A i osiąga remis jest w relacji jeden do jednego z sekwencją zaczynającą się od B, a prawdopodobieństwo, że sekwencja zaczyna się od B wynosi , więc prawdopodobieństwo, że A zawsze prowadzi w głosowaniu, wynosi

prawdopodobieństwo sekwencji, które wiążą się w pewnym momencie
prawdopodobieństwo sekwencji, które wiążą się w pewnym momencie i zaczynają się od A lub B
prawdopodobieństwo sekwencji, które wiążą się w pewnym momencie i zaczynają się od b
prawdopodobieństwo, że sekwencja zaczyna się od B

Dowód przez indukcję

Inną metodą dowodu jest indukcja matematyczna :

  • Poluzowujemy warunek do . Oczywiście twierdzenie jest poprawne, gdy , ponieważ w tym przypadku pierwszy kandydat nie będzie wyraźnie po zliczeniu wszystkich głosów (więc prawdopodobieństwo wynosi
  • Oczywiście twierdzenie jest prawdziwe, jeśli p > 0 i q = 0, gdy prawdopodobieństwo wynosi 1, biorąc pod uwagę, że pierwszy kandydat otrzymuje wszystkie głosy; jest to również prawdziwe, gdy p = q > 0, jak właśnie widzieliśmy.
  • Załóżmy, że jest to prawdziwe zarówno wtedy, gdy p = a − 1 i q = b , jak i gdy p = a i q = b − 1, gdzie a > b > 0. (Nie musimy rozważać przypadku tutaj, ponieważ już wcześniej się go pozbyliśmy.) Następnie, biorąc pod uwagę przypadek z p = a i q = b , ostatni liczony głos dotyczy pierwszego kandydata z prawdopodobieństwem a / ( a + b ), lub dla drugiego z prawdopodobieństwem b /( a + b ). Tak więc prawdopodobieństwo, że pierwszy będzie prowadził przez całe liczenie do przedostatniego liczonego głosu (a także po głosowaniu końcowym) wynosi:
  • A więc jest to prawdziwe dla wszystkich p i q gdzie p > q > 0.

Dowód za pomocą lematu o cyklu

Prosty dowód oparty jest na pięknym Lemacie o Cyklu Dvoretzky'ego i Motzkina. Wywołaj dominującą sekwencję kart do głosowania , jeśli A wyraźnie wyprzedza B podczas liczenia głosów. Cycle Lemma twierdzi B , ma cykliczne ułóż podaną sekwencję w okręgu i wielokrotnie usuwaj sąsiednie pary AB, Każde z tych A było początkiem dominującej permutacji cyklicznej, zanim cokolwiek zostało usunięte. Tak z dowolnego _ _

Dowód przez martyngały

Niech . Zdefiniuj proces stochastyczny „liczenia wstecz”.

gdzie przewaga kandydata A .

Twierdzenie: jest procesem martyngałowym.

Biorąc pod uwagę , wiemy, że pierwszego głosy, były dla kandydata A i dla kandydata B.

prawdopodobieństwem , mamy i . Podobnie dla drugiego. Następnie oblicz, aby znaleźć .

Zdefiniuj czas zatrzymania jako minimum takie, że jeśli ma taki . Wtedy prawdopodobieństwo, że kandydat A prowadzi przez cały czas, opcjonalnego twierdzenia o zatrzymaniu =

Dowody Bertranda i André

Bertrand wyraził rozwiązanie jako

gdzie , a to liczba wyborców na pierwszego kandydata. Stwierdza, że ​​wynik wynika ze wzoru

gdzie jest liczbą korzystnych sekwencji, ale „wydaje się prawdopodobne, że tak prosty wynik można by pokazać w Rzeczywiście, wkrótce Désiré André przedstawił bardziej bezpośredni dowód. Jego podejście jest często błędnie określane przez współczesnych autorów jako „zasada odbicia”, ale w rzeczywistości wykorzystuje permutację. Pokazuje, że sekwencje „niekorzystne” (te, które osiągają remis pośredni) składają się z takiej samej liczby sekwencji rozpoczynających się na literę A, jak i na literę B. Każda sekwencja rozpoczynająca się na literę B jest niekorzystna i istnieje takie sekwencje z B, po którym q B p A. Każda niekorzystna sekwencja, która zaczyna się od A, może zostać przekształcona w dowolną sekwencję ( q -1) B i p A, znajdując pierwsze B, które narusza regułę (powodując zrównanie liczby głosów) i usuwając je oraz zamieniając kolejność pozostałych części. Aby odwrócić proces, weź dowolną sekwencję ( q -1) B i p A i wyszukaj od końca, aby znaleźć miejsce, w którym liczba A najpierw przekracza liczbę B, a następnie zamień kolejność części i umieść B w między. Na przykład niekorzystna sekwencja AAB B ABAA jednoznacznie odpowiada dowolnej sekwencji ABAA AAB . Z tego wynika, że ​​liczba korzystnych sekwencji p A i q B wynosi

a zatem wymagane prawdopodobieństwo wynosi

zgodnie z oczekiwaniami.

Wariant: remisy dozwolone

Pierwotny problem polega na znalezieniu prawdopodobieństwa, że ​​pierwszy kandydat ma zawsze przewagę w liczeniu głosów. Zamiast tego można rozważyć problem znalezienia prawdopodobieństwa, że ​​​​drugi kandydat nigdy nie jest na czele (to znaczy z remisami są dozwolone). W tym przypadku odpowiedź brzmi

Problem wariantowy można rozwiązać metodą odbicia w sposób podobny do problemu pierwotnego. Liczba możliwych sekwencji głosowania wynosi . Nazwij sekwencję „złą”, jeśli drugi kandydat jest zawsze z przodu, a jeśli można wyliczyć liczbę złych sekwencji, liczbę „dobrych” sekwencji można znaleźć przez odjęcie i obliczenie prawdopodobieństwa.

Przedstaw sekwencję głosowania jako ścieżkę kratową na płaszczyźnie kartezjańskiej w następujący sposób:

  • Rozpocznij ścieżkę w (0, 0)
  • Za każdym razem, gdy otrzymany zostanie głos na pierwszego kandydata, przesuń się o 1 jednostkę w prawo.
  • Za każdym razem, gdy otrzymany zostanie głos na drugiego kandydata, przesuń się o 1 jednostkę w górę.

Każda taka ścieżka odpowiada unikalnej sekwencji głosów i kończy się na ( p , q ). Sekwencja jest „dobra” dokładnie wtedy, gdy odpowiadająca jej ścieżka nigdy nie wychodzi poza ukośną linię y = x ; równoważnie sekwencja jest „zła” dokładnie wtedy, gdy odpowiadająca jej ścieżka dotyka linii y = x + 1.

„Zła” ścieżka (niebieska) i jej odbita ścieżka (czerwona)

Dla każdej „złej” ścieżki P zdefiniuj nową ścieżkę P ′, odzwierciedlając część P aż do pierwszego punktu, w którym styka się ona z linią przecinającą ją. P ′ jest ścieżką od (−1, 1) do ( p , q ). Ta sama operacja zastosowana ponownie przywraca oryginalne P . Daje to zgodność jeden do jednego między „złymi” ścieżkami a ścieżkami od (−1, 1) do ( p , q ). Liczba tych ścieżek wynosi a więc jest to liczba „złych” sekwencji. Pozostawia to liczbę „dobrych” sekwencji jako

Ponieważ są razem że sekwencja jest dobra, wynosi .

W rzeczywistości rozwiązania pierwotnego problemu i problemu wariantowego są łatwo powiązane. Aby kandydat A miał całkowitą przewagę podczas całego liczenia głosów, musi otrzymać pierwszy głos, a dla pozostałych głosów (pomijając pierwszy) musi być albo wyraźnie lepszy, albo remisujący przez cały czas liczenia. Stąd rozwiązanie pierwotnego problemu jest

jako wymagane.

I odwrotnie, przypadek remisu można wyprowadzić z przypadku braku remisu. Zauważ, że liczba nieremisujących sekwencji z p+1 głosami na A jest równa liczbie remisowych sekwencji z p głosami na A. Liczba nieremisujących głosów z p + 1 głosami na A wynosi { , więc ułamek sekwencji z głosami p na głosy A wynosi .

Notatki

Linki zewnętrzne