Bertrands valsats

Inom kombinatorik är Bertrands valsats , uppkallad efter Joseph Bertrand , som publicerade den 1887, ett uttalande som bevisar svaret på frågan "Vad är sannolikheten att i ett val som involverar två kandidater, där den första får p röster och andra får q < p , kommer den första att ligga före den andra under hela tiden för rösträkningen? Svar på denna fråga:

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

I sin publikation skissade Bertrand ett bevis på detta teorem genom induktion och undrade om det kunde bevisas med kombinatoriska metoder. Ett sådant bevis föreslogs av D. Andre[1] .

Exempel

Antag att det finns 5 röster, varav 3 ges till kandidat A och 2 till kandidat B. I detta fall är p =3 och q =2. Eftersom endast resultatet av omröstningen är känt, finns det 10 alternativ för omröstningssekvenser: $\left(C_{5}^{2}\right)$

AAABB
AABAB
ABAAB
BAAAB
AABBA
ABABA
BAABA
ABBAA
BABAA
BBAAA

För AABAB- sekvensen skulle rösträkningen se ut så här:

Kandidat	A	A	B	A	B
A	ett	2	2	3	3
B	0	0	ett	ett	2

Det kan ses att i varje kolumn är antalet röster för A strikt större än antalet röster för B , vilket innebär att denna röstföljd uppfyller villkoret.

För sekvensen AABBA har vi följande:

Kandidat	A	A	B	B	A
A	ett	2	2	2	3
B	0	0	ett	2	2

I detta fall kommer A och B att vara lika efter den fjärde omröstningen, och därför uppfyller denna sekvens inte det givna villkoret. Av de 10 möjliga sekvenserna passar bara AAABB och AABAB . Därför är sannolikheten att A kommer att ligga före B under hela omröstningsperioden

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

i full överensstämmelse med satsens förutsägelse.

Bevis genom induktion

Basen för induktion . Uppenbarligen är satsen sann för p > 0 och q = 0: i detta fall är sannolikheten 1, eftersom den första kandidaten får alla röster. Satsen gäller även för p = q > 0: sannolikheten är 0 på grund av att antalet röster för kandidaterna blir lika åtminstone i slutet av räkningen.
Induktivt antagande . Vi kommer att anta att satsen är sann för p = a − 1 och q = b och när p = a och q = b − 1 under villkoret a > b > 0.
Induktionsövergång . Då i fallet p = a och q = b tillhör den senast räknade rösten den första kandidaten med sannolikhet a /( a + b ) och den andra med sannolikhet b /( a + b ). Vi får att sannolikheten för den första att gå före tvåan fram till sista rösten är lika med

{a \over (a+b)}{(a-1)-b \over (a+b-1)}+{b \over (a+b)}{a-(b-1) \över (a+b-1)}={ab \över a+b}.

. Att antalet röster för den första kandidaten är strikt större än för den andra efter den sista omröstningen säkerställs av villkoret p = a > b = q .

Således är satsen sann för alla p och q så att p > q > 0.

Anteckningar

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

Länkar

Valsedelproblemet, Mark Renault