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”.
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.
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
- Ballot twierdzenia, stare i nowe , L. Addario-Berry, BA Reed , 2007, w Horyzonty kombinatoryki , redaktorzy Ervin Győri, G. Katona, Gyula OH Katona, László Lovász , Springer, 2008, ISBN 978-3-540-77199 -9
Linki zewnętrzne
- The Ballot Problem (zawiera skany oryginalnych artykułów francuskich i tłumaczenia na język angielski)
- Bernard Bru, Les leçons de calcul des probabilités de Joseph Bertrand , historia problemu (po francusku)
- Weisstein, Eric W. „Problem głosowania” . MathWorld .