Bertrands valsats

Inom kombinatorik är Bertrands valsedelproblem frågan: "I ett val där kandidat A får p röster och kandidat B får q röster med p > q , vad är sannolikheten att A kommer att ligga strikt före B under hela räkningen?" Svaret är

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

Resultatet publicerades först av WA Whitworth 1878, men är uppkallat efter Joseph Louis François Bertrand som återupptäckte det 1887.

I Bertrands originalpapper skisserar han ett bevis baserat på en allmän formel för antalet gynnsamma sekvenser med hjälp av en rekursionsrelation . Han anmärker att det förefaller troligt att ett så enkelt resultat skulle kunna bevisas med en mer direkt metod. Ett sådant bevis gavs av Désiré André , baserat på observationen att de ogynnsamma sekvenserna kan delas upp i två lika sannolika fall, varav ett (fallet då B får den första rösten) är lätt att beräkna; han bevisar jämlikheten genom en explicit bijektion . En variant av hans metod är populärt känd som Andrés reflektionsmetod , även om André inte använde några reflektioner. Bertrands omröstningssats är ekvivalent med cykellemmat .

Exempel

Antag att det finns 5 väljare, varav 3 röstar på kandidat A och 2 röstar på kandidat B (så p = 3 och q = 2). Det finns tio möjligheter för ordningsföljden för de avgivna rösterna:

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

För ordningen AABAB är röstsiffran när valet fortskrider:

Kandidat	A	A	B	A	B
A	1	2	2	3	3
B	0	0	1	1	2

För varje kolumn är talet för A alltid större än talet för B , så A är alltid strikt före B . För ordningen AABBA är röstsiffran när valet fortskrider:

Kandidat	A	A	B	B	A
A	1	2	2	2	3
B	0	0	1	2	2

För denna ordning är B lika med A efter den fjärde rösten, så A ligger inte alltid strikt före B . Av de 10 möjliga beställningarna A alltid före B endast för AAABB och AABAB . Så sannolikheten att A alltid kommer att ligga strikt före är

${\frac {2}{10}}={\frac {1}{5}},$

och detta är verkligen lika med ${\frac {3-2}{3+2}}$ som satsen förutsäger.

Motsvarande problem

Istället för att beräkna sannolikheten för att en slumpmässig rösträkningsordning har den önskade egenskapen, kan man istället beräkna antalet fördelaktiga räkneorder och sedan dividera med det totala antalet sätt som rösterna kunde ha räknats på. (Detta är metoden som används av Bertrand.) Det totala antalet sätt är den binomala koefficienten ${\tbinom {p+q}{p}}$ ; Bertrands bevis visar att antalet gynnsamma ordningsföljder för att räkna rösterna är ${\tbinom {p+q-1}{p -1}}-{\tbinom {p+q-1}{p}}$ (även om han inte anger detta nummer explicit). Och efter division ger detta ${\tfrac {p}{p+q}}-{\tfrac {q}{p+q}} ={\tfrac {pq}{p+q}}$ .

Ett annat ekvivalent problem är att beräkna antalet slumpmässiga vandringar på de heltal som består av n steg av enhetslängd, som börjar vid origo och slutar vid punkten m , som aldrig blir negativa. Om vi ​​antar att n och m har samma paritet och $n\geq m\geq 0$ är detta tal

${\binom {n}{\tfrac {n+m}{2}}}-{\binom {n}{{\tfrac {n+m}{2}}+1}}={\frac {m+1}{{\tfrac {n+m}{2}}+1}}{\binom {n}{\tfrac {n+m}{2}}}.$

När $m=0$ och $n$ är jämnt ger detta det katalanska talet ${\frac {1}{{\tfrac {n }{2}}+1}}{\binom {n}{\tfrac {n}{2}}}$ .

[Observera att om $m=0$ måste $n$ vara jämnt. Annars kan den slumpmässiga promenaden inte sluta vid $0$ . Detta kan ses på följande sätt: låt $P$ vara antalet "positiva" drag, dvs till höger, och låt $N$ vara antalet "negativa" drag, dvs. vänster. Eftersom $P+N=n$ och $PN=m$ , har vi $P={\frac {n+m} {2}}$ och $N={\frac {nm}{2}}$ . Eftersom $P$ och $N$ är heltal, om $m=0$ måste ${\frac {n}{2}}$ vara ett heltal. Med andra ord måste ${\displaystyle n} vara jämnt.]$

Bevis genom eftertanke

För att A ska ligga strikt före B under hela rösträkningen kan det inte bli oavgjort. Separera räknesekvenserna enligt första rösten. Varje sekvens som börjar med en röst på B måste nå oavgjort någon gång, eftersom A så småningom vinner. För varje sekvens som börjar med A och når oavgjort, reflektera rösterna fram till punkten för den första lika (så att alla A blir ett B och vice versa) för att få en sekvens som börjar med B. Därav varje sekvens som börjar med A och når oavgjort är en-till-en-överensstämmelse med en sekvens som börjar med B, och sannolikheten att en sekvens börjar med B är $q/(p+q)$ , så sannolikheten att A alltid leder omröstningen är

$=1-$ sannolikheten för sekvenser som vid något tillfälle stämmer

$=1-$ sannolikheten för sekvenser som hänger ihop någon gång och börjar med A eller B

$=1-2\times ($ sannolikheten för sekvenser som binder ihop någon gång och börjar med B $)$

$=1-2\times ($ sannolikheten att en sekvens börjar med B $)$

$=1-2{\frac {q}{p+q}}={\frac { pq}{p+q}}$

Bevis genom induktion

En annan metod för bevis är genom matematisk induktion :

• Vi lossar villkoret $p>q$ till $p\geq q$ . Uppenbarligen är satsen korrekt när $p=q$ , eftersom den första kandidaten i det här fallet inte kommer strikt före efter att alla röster har räknats (så sannolikheten är 0).
• Uppenbarligen är satsen sann om p > 0 och q = 0 när sannolikheten är 1, givet att den första kandidaten får alla röster; det är också sant när p = q > 0 som vi nyss har sett.
• Antag att det är sant både när p = a − 1 och q = b , och när p = a och q = b − 1, med a > b > 0. (Vi behöver inte ta hänsyn till fallet ${\ displaystyle a=b}$ här, eftersom vi redan har disponerat det tidigare.) När man sedan betraktar fallet med p = a och q = b , är den sista rösten som räknas antingen för den första kandidaten med sannolikhet a /( a + b ), eller för den andra med sannolikhet b /( a + b ). Så sannolikheten för att den första går före under hela räkningen till den näst sista rösten som räknas (och även efter den sista rösten) är:

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

• Och så är det sant för alla p och q med p > q > 0.

Bevis via Cykellemma

Ett enkelt bevis är baserat på Dvoretzkys och Motzkins vackra cykellemma. Kalla en valsedel som dominerar om A är strikt före B under hela rösträkningen. Cykellemma hävdar att varje sekvens av $p$ A:n och $q$ B:n, där $p>q$ , har exakt $pq$ dominerande cykliska permutationer. För att se detta, arrangera bara den givna sekvensen av $p+q$ A och B i en cirkel och upprepade gånger ta bort intilliggande par AB tills endast $pq$ A:s återstår. Var och en av dessa A var början på en dominerande cyklisk permutation innan någonting togs bort. Så $pq$ av de $p+q$ cykliska permutationerna av valfritt arrangemang av $p$ A-röster och $q$ B-röster dominerar.

Bevis av martingaler

Låt $n=p+q$ . Definiera den "bakåträkning" stokastiska processen

$$X_{k}={\frac {S_{nk}}{nk}};\quad k=0,1,...,n-1$$

där $S_{nk}$ är ledningen för kandidat A över B, efter att $nk$ röster har kommit in.

Påstående: $X_{k}$ är en martingalprocess.

Med tanke på $X_{k}$ vet vi att ${\displaystyle S_{nk}=(nk)X_{k}} ,$ alltså av de första $nk$ röster, ${\frac {X_{k}+1}{2}}(nk)$ var för kandidat A, och ${\frac {-X_{k}+1}{2}}(nk)$ var för kandidat B.

Så, med sannolikhet ${\frac {X_{k}+1}{2}}$ , vi har $S_{nk-1}=S_{nk}-1$ och $X_{k+1}={\frac {nk}{nk-1}}X_{k}-{\frac {1}{nk-1}}$ . Likadant för den andra. Beräkna sedan för att hitta $E[X_{k+1}|X_{k}]=X_{k}$ .

Definiera stopptiden $T$ som antingen minsta $k$ så att ${\displaystyle X_{k}=0} ,$ eller $n-1$ om det inte finns någon sådan $k$ . Då är sannolikheten att kandidat A leder hela tiden bara ${\displaystyle E[X_{T}]} ,$ vilket enligt den valfria stoppsatsen är $E[X_{T}]=E[X_{0}]={\frac {pq}{p+q}}$

Bertrands och Andrés bevis

Bertrand uttryckte lösningen som

${\frac {2m-\mu }{\mu }}$

där $\mu =p+q$ är det totala antalet väljare och $m=p$ är antalet väljare för den första kandidaten. Han konstaterar att resultatet följer av formeln

$P_{m+1,\mu +1}=P_{m,\mu }+P_{m+1, \mu },$

där $P_{m,\mu }$ är antalet gynnsamma sekvenser, men "det verkar troligt att ett så enkelt resultat skulle kunna visas på ett mer direkt sätt". Ett mer direkt bevis producerades snart av Désiré André. Hans tillvägagångssätt kallas ofta felaktigt för "reflektionsprincipen" av moderna författare men använder i själva verket en permutation. Han visar att de "ogynnsamma" sekvenserna (de som når ett mellanläge) består av lika många sekvenser som börjar med A som de som börjar med B. Varje sekvens som börjar med B är ogynnsam, och det finns ${\tbinom {p+q-1}{q-1}}$ sådana sekvenser med ett B följt av en godtycklig sekvens av ( q -1) B och p A. Varje ogynnsam sekvens som börjar med A kan omvandlas till en godtycklig sekvens av ( q -1) B:n och p A:n genom att hitta det första B som bryter mot regeln (genom att få rösträkningen att bli lika) och radera den och byta ordningsföljd av de återstående delarna. För att vända processen, ta valfri sekvens av ( q -1) B och p A och sök från slutet för att hitta var antalet A först överstiger antalet B och växla sedan ordningen på delarna och placera ett B i mellan. Till exempel motsvarar den ogynnsamma sekvensen AABB ABAA unikt den godtyckliga sekvensen ABAA AAB . Av detta följer att antalet gynnsamma sekvenser av p A och q B är

${\binom {p+q}{q}}-2{\ binom {p+q-1}{q-1}}={\binom {p+q}{q}}{\frac {pq}{p+q}}$

och därmed den erforderliga sannolikheten är

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

som förväntat.

Variant: slipsar tillåtna

Det ursprungliga problemet är att hitta sannolikheten för att den första kandidaten alltid ligger strikt före i rösträkningen. Man kan istället överväga problemet med att hitta sannolikheten att den andra kandidaten aldrig är före (det vill säga med slipsar är tillåtna). I det här fallet är svaret

${\frac {p+1-q}{p+1}}.$

Variantproblemet kan lösas med reflektionsmetoden på liknande sätt som det ursprungliga problemet. Antalet möjliga röstsekvenser är ${\tbinom {p+q}{q}}$ . Kalla en sekvens för "dålig" om den andra kandidaten någonsin är före, och om antalet dåliga sekvenser kan räknas kan antalet "bra" sekvenser hittas genom subtraktion och sannolikheten kan beräknas.

Representera en röstningssekvens som en gitterbana på det kartesiska planet enligt följande:

• Starta banan vid (0, 0)
• Varje gång en röst på den första kandidaten tas emot, flytta höger 1 enhet.
• Varje gång en röst på den andra kandidaten tas emot flyttas upp 1 enhet.

Varje sådan väg motsvarar en unik sekvens av röster och kommer att sluta på ( p , q ). En sekvens är 'bra' exakt när motsvarande väg aldrig går över diagonallinjen y = x ; på motsvarande sätt är en sekvens "dålig" exakt när motsvarande bana vidrör linjen y = x + 1.

"Dålig" väg (blå) och dess reflekterade väg (röd)

För varje "dålig" bana P definierar du en ny bana P ′ genom att reflektera delen av P fram till den första punkten den vidrör linjen över den. P ′ är en väg från (−1, 1) till ( p , q ). Samma operation återställer det ursprungliga P . Detta ger en en-till-en-överensstämmelse mellan de "dåliga" banorna och banorna från (−1, 1) till ( p , q ). Antalet av dessa vägar är ${\tbinom {p+q}{q-1}}$ och så det är antalet "dåliga" sekvenser. Detta lämnar antalet "bra" sekvenser som

${\binom {p+q}{q}}-{\binom {p+q}{q-1}}={\binom {p+q}{q}}{\frac {p+1 -q}{p+1}}.$

Eftersom det finns ${\tbinom {p+q}{q}}$ totalt, är sannolikheten för att en sekvens är bra ${\tfrac { p+1-q}{p+1}}$ .

Faktum är att lösningarna på det ursprungliga problemet och variantproblemet är lätt relaterade. För att kandidat A ska vara strikt före under hela rösträkningen måste de få den första rösten och för de återstående rösterna (om man ignorerar den första) måste de antingen ligga strikt före eller oavgjort under hela räkningen. Därför är lösningen på det ursprungliga problemet

${\frac {p}{p+q}}{\frac {p-1+1-q} {p-1+1}}={\frac {pq}{p+q}}$

såsom krävs.

Omvänt kan slipsväskan härledas från fallet utan slips. Observera att antalet oavgjorda sekvenser med p+1 röster för A är lika med antalet oavgjorda sekvenser med p röster för A. Antalet oavgjorda röster med p + 1 röster för A-röster är ${\tfrac {p+1-q}{p+1+q}}{\tbinom {p+1+q}{q}}$ , som genom algebraisk manipulation är ${\tfrac {p+1-q}{p+1}}{\tbinom {p+q}{q} }$ , så bråkdelen av sekvenser med p röster för A-röster är ${\tfrac {p+1-q}{p+1}}$ .

Anteckningar

•   Valsedlar, gamla och nya , L. Addario-Berry, BA Reed , 2007, i Horizons of combinatorics , Redaktörer Ervin Győri, G. Katona, Gyula OH Katona, László Lovász , Springer, 2008, ISBN 978-77-1990 -9

externa länkar

• Valsedelproblemet (inkluderar skanningar av de franska originalartiklarna och engelska översättningar)
• Bernard Bru, Les leçons de calcul des probabilités de Joseph Bertrand , problemets historia (på franska)
• Weisstein, Eric W. "Röstningsproblem" . MathWorld .