Bertrandova volební věta

V kombinatorice je Bertrandova volební věta , pojmenovaná po Josephu Bertrandovi , který ji publikoval v roce 1887, prohlášení dokazující odpověď na otázku „Jaká je pravděpodobnost, že ve volbách zahrnujících dva kandidáty, ve kterých první získá p hlasů a druhý dostane q < p , bude první po celou dobu sčítání hlasů před druhým? Odpověď na tuto otázku:

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

Bertrand ve své publikaci načrtl důkaz tohoto teorému indukcí a přemýšlel, zda by to bylo možné dokázat kombinatorickými metodami. Takový důkaz navrhl D. Andre[1] .

Příklad

Předpokládejme, že je 5 hlasů, z nichž 3 jsou přiděleny kandidátovi A a 2 kandidátovi B. V tomto případě p = 3 a q = 2. Protože je znám pouze výsledek hlasování, existuje 10 možností pro pořadí hlasování: $\left(C_{5}^{2}\right)$

AAABB
AABAB
ABAAB
BAAAB
AABBA
ABABA
BAABA
ABBAA
BABAA
BBAAA

Pro sekvenci AABAB by počet hlasů vypadal takto:

Kandidát	A	A	B	A	B
A	jeden	2	2	3	3
B	0	0	jeden	jeden	2

Je vidět, že v každém sloupci je počet hlasů pro A striktně větší než počet hlasů pro B , což znamená, že tato posloupnost hlasů podmínku splňuje.

Pro sekvenci AABBA máme následující:

Kandidát	A	A	B	B	A
A	jeden	2	2	2	3
B	0	0	jeden	2	2

V tomto případě se A a B po čtvrtém hlasování vyrovnají, a proto tato posloupnost nesplňuje danou podmínku. Z 10 možných sekvencí se hodí pouze AAABB a AABAB . Pravděpodobnost, že A bude po celou dobu hlasování před B , je tedy

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

plně v souladu s předpovědí věty.

Důkaz indukcí

Základ indukce . Je zřejmé, že věta platí pro p > 0 a q = 0: v tomto případě je pravděpodobnost 1, protože první kandidát získá všechny hlasy. Věta platí i pro p = q > 0: pravděpodobnost je 0 vzhledem k tomu, že počet hlasů kandidátů se bude minimálně na konci sčítání rovnat.
Indukční předpoklad . Budeme předpokládat, že věta platí pro p = a − 1 a q = b a když p = a a q = b − 1 za podmínky a > b > 0.
Indukční přechod . Pak v případě p = a a q = b patří poslední sečtený hlas prvnímu kandidátovi s pravděpodobností a /( a + b ) a druhému s pravděpodobností b /( a + b ). Dostaneme, že pravděpodobnost, že první bude před druhým až do posledního hlasu, je rovna

{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}.

. Skutečnost, že počet hlasů pro prvního kandidáta je po posledním hlasování striktně větší než pro druhého, je zajištěna podmínkou p = a > b = q .

Věta tedy platí pro všechna p a q tak, že p > q > 0.

Poznámky

↑ 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.

Odkazy

Problém s hlasováním, Mark Renault