Bertrandin vaalilause

Kombinatoriikassa Bertrandin vaalilause , joka on nimetty Joseph Bertrandin mukaan, joka julkaisi sen vuonna 1887, on lausunto, joka todistaa vastauksen kysymykseen "Millä todennäköisyydellä vaaleissa , joissa on kaksi ehdokasta, joista ensimmäinen saa p ääntä ja toinen saa q < p , onko ensimmäinen edellä toista koko ääntenlaskennan ajan? Vastaus tähän kysymykseen:

{\frac {pq}{p+q}}

Julkaisussaan Bertrand luonnosteli tämän lauseen todisteen induktiolla ja pohti, voitaisiinko se todistaa kombinatorisilla menetelmillä. Tällaista todistetta ehdotti D. Andre[1] .

Esimerkki

Oletetaan, että on 5 ääntä, joista 3 annetaan ehdokkaalle A ja 2 ehdokkaalle B. Tässä tapauksessa p = 3 ja q = 2. Koska vain äänestyksen tulos on tiedossa, äänestyssarjoille on 10 vaihtoehtoa: $\left(C_{5}^{2}\right)$

AAABB
AABAB
ABAAB
BAAAB
AABBA
ABABA
BAABA
ABBAA
BABAA
BBAAA

AABAB- sarjan äänimäärä näyttäisi tältä:

ehdokas	A	A	B	A	B
A	yksi	2	2	3	3
B	0	0	yksi	yksi	2

Voidaan nähdä, että kussakin sarakkeessa A :n äänimäärä on ehdottomasti suurempi kuin B :n äänimäärä , mikä tarkoittaa, että tämä äänisarja täyttää ehdon.

Sekvenssille AABBA meillä on seuraavat:

ehdokas	A	A	B	B	A
A	yksi	2	2	2	3
B	0	0	yksi	2	2

Tässä tapauksessa A ja B ovat samat neljännen äänestyksen jälkeen, joten tämä järjestys ei täytä annettua ehtoa. Kymmenestä mahdollisesta sekvenssistä vain AAABB ja AABAB sopivat . Siksi todennäköisyys, että A on B :n edellä koko äänestysajan, on

{\frac {2}{10}}={\frac {1}{5}}={\frac {3-2}{3+2}}

täysin lauseen ennusteen mukaisesti.

Todistus induktiolla

Induktion pohja . Ilmeisesti lause pitää paikkansa, kun p > 0 ja q = 0: tässä tapauksessa todennäköisyys on 1, koska ensimmäinen ehdokas saa kaikki äänet. Lause pätee myös p = q > 0: todennäköisyys on 0 johtuen siitä, että ehdokkaiden äänimäärät ovat yhtä suuret ainakin laskennan lopussa.
Induktiivinen oletus . Oletetaan, että lause on tosi, kun p = a − 1 ja q = b ja kun p = a ja q = b − 1 ehdolla a > b > 0.
Induktio siirtymä . Tällöin p = a ja q = b tapauksessa viimeksi laskettu ääni kuuluu ensimmäiselle todennäköisyydellä a /( a + b ) ja toiselle todennäköisyydellä b /( a + b ). Saamme, että todennäköisyys ensimmäiselle olla toisen edellä viimeiseen äänestykseen asti on yhtä suuri

{\näyttötyyli {a \over (a+b)}{(a-1)-b \over (a+b-1)}+{b \over (a+b)}{a-(b-1) \over (a+b-1)}={ab \over a+b}.}

. Ehdolla p = a > b = q varmistetaan se, että ensimmäisen ehdokkaan äänimäärä on tiukasti suurempi kuin toisella viimeisen äänestyksen jälkeen .

Näin ollen lause pätee kaikille p :lle ja q :lle siten, että p > q > 0.

Muistiinpanot

↑ D. André, Solution directe du problème résolu par M. Bertrand, Comptes Rendus de l'Académie des Sciences, Paris 105 (1887) 436-437.

Linkit

Äänestysongelma, Mark Renault