El teorema de la votación de Bertrand

En combinatoria , el problema de la votación de Bertrand es la pregunta: "En una elección donde el candidato A recibe p votos y el candidato B recibe q votos con p  > q , ¿cuál es la probabilidad de que A esté estrictamente por delante de B durante todo el recuento bajo el supuesto de que los votos se cuentan en un orden elegido al azar?" La respuesta es 

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

El resultado fue publicado por primera vez por WA Whitworth en 1878, pero lleva el nombre de Joseph Louis François Bertrand , quien lo redescubrió en 1887. ^{[ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ]}

En el artículo original de Bertrand, esboza una demostración basada en una fórmula general para el número de secuencias favorables utilizando una relación de recurrencia . Observa que parece probable que un resultado tan simple pueda demostrarse mediante un método más directo. Désiré André [ ^{6 ]} proporcionó una demostración de este tipo, ^basada en la observación de que las secuencias desfavorables pueden dividirse en dos casos igualmente probables, uno de los cuales (el caso en que B recibe el primer voto) se calcula fácilmente; demuestra la igualdad mediante una biyección explícita . Una variación de su método se conoce popularmente como el método de reflexión de André , aunque André no utilizó ninguna reflexión. ^{[ 7 ]}

El teorema de la votación de Bertrand está relacionado con el lema del ciclo . Ambos proporcionan fórmulas similares, pero el lema del ciclo considera desplazamientos circulares de un orden de conteo de votos dado, en lugar de todas las permutaciones.

Supongamos que hay 5 votantes, de los cuales 3 votan por el candidato A y 2 votan por el candidato B (por lo tanto, p = 3 y q = 2). Hay diez órdenes igualmente probables en las que se podrían contar los votos:

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

Para el orden AABAB , el recuento de votos a medida que avanza la elección es:

Para cada columna, el recuento de A siempre es mayor que el recuento de B , por lo que A siempre está estrictamente por delante de B. Para el orden AABBA, el recuento de votos a medida que avanza la elección es:

Para este orden, B está empatado con A después del cuarto voto, por lo que A no siempre está estrictamente por delante de B. De los 10 órdenes posibles, A siempre está por delante de B solo para AAABB y AABAB . Por lo tanto, la probabilidad de que A siempre esté estrictamente por delante es

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

y esto es efectivamente igual a${\displaystyle {\frac {3-2}{3+2}}}$tal como predice el teorema.

Para que A esté estrictamente por delante de B durante todo el recuento de votos, no puede haber empates. Separe las secuencias de recuento según el primer voto. Cualquier secuencia que comience con un voto para B debe llegar a un empate en algún punto, porque A finalmente gana. Para cualquier secuencia que comience con A y llegue a un empate, refleje los votos hasta el punto del primer empate (de modo que cualquier A se convierte en un B, y viceversa) para obtener una secuencia que comience con B. Por lo tanto, cada secuencia que comienza con A y llega a un empate está en correspondencia uno a uno con una secuencia que comienza con B, y la probabilidad de que una secuencia comience con B es${\displaystyle q/(p+q)}$, por lo tanto, la probabilidad de que A siempre lidere la votación es

${\displaystyle =1-}$la probabilidad de secuencias que se empaten en algún punto

${\displaystyle =1-}$la probabilidad de secuencias que empatan en algún punto y comienzan con A o B

${\displaystyle =1-2\times (}$la probabilidad de secuencias que empatan en algún punto y comienzan con B${\displaystyle )}$

${\displaystyle =1-2\times (}$la probabilidad de que una secuencia comience con B${\displaystyle )}$

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

Otro método de demostración es mediante inducción matemática :

• Relajamos la condición${\displaystyle p>q}$a${\displaystyle p\geq q}$. Claramente, el teorema es correcto cuando${\displaystyle p=q}$, puesto que en este caso el primer candidato no estará estrictamente por delante después de que se hayan contado todos los votos (por lo que la probabilidad es 0).
• Es evidente que el teorema es cierto si p  >  0 y q  =  0 cuando la probabilidad es 1, dado que el primer candidato recibe todos los votos; también es cierto cuando p  = q > 0, como acabamos de ver.   
• Supongamos que es cierto tanto cuando p  = a − 1 y q = b , como cuando p = a y q = b − 1, con a > b > 0. (No necesitamos considerar el caso               ${\displaystyle a=b}$Aquí, puesto que ya lo hemos resuelto antes.) Entonces, considerando el caso con p  = a y q = b , el último voto contado es para el primer candidato con probabilidad a / ( a + b ), o para el segundo con probabilidad b / ( a + b ). Por lo tanto, la probabilidad de que el primero esté por delante durante todo el recuento hasta el penúltimo voto contado (y también después del voto final) es:       

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

• Y así es para todo p y q con p  > q > 0.   

Una prueba sencilla se basa en el lema del ciclo de Dvoretzky y Motzkin. ^{[ 8 ]} Se dice que una secuencia de votos es dominante si A está estrictamente por delante de B durante todo el recuento de votos. El lema del ciclo afirma que cualquier secuencia de${\displaystyle p}$A y${\displaystyle q}$B's, donde${\displaystyle p>q}$, tiene precisamente${\displaystyle pq}$permutaciones cíclicas dominantes. Para ver esto, simplemente ordene la secuencia dada de${\displaystyle p+q}$A y B en un círculo y eliminar repetidamente pares adyacentes AB hasta que solo${\displaystyle pq}$Las A permanecen. Cada una de estas A era el inicio de una permutación cíclica dominante antes de que se eliminara nada. Así que${\displaystyle pq}$fuera de la${\displaystyle p+q}$permutaciones cíclicas de cualquier arreglo de${\displaystyle p}$Un voto y${\displaystyle q}$Los votos del tipo B son dominantes.

Dejar${\displaystyle n=p+q}$Defina el proceso estocástico de "conteo hacia atrás".

$${\displaystyle X_{k}={\frac {S_{nk}}{nk}};\quad k=0,1,...,n-1}$$ dónde${\displaystyle S_{nk}}$es la ventaja del candidato A sobre B, después${\displaystyle nk}$Ya han llegado los votos.

Afirmar:${\displaystyle X_{k}}$es un proceso de martingala .

Dado${\displaystyle X_{k}}$, sabemos que${\ Displaystyle S_ {nk} = (nk) X_ {k}}$, así que del primero${\displaystyle nk}$votos,${\displaystyle {\frac {X_{k}+1}{2}}(nk)}$eran para el candidato A, y${\displaystyle {\frac {-X_{k}+1}{2}}(nk)}$eran para el candidato B.

Entonces, con probabilidad${\displaystyle {\frac {X_{k}+1}{2}}}$, tenemos${\displaystyle S_{nk-1}=S_{nk}-1}$, y${\displaystyle X_{k+1}={\frac {nk}{nk-1}}X_{k}-{\frac {1}{nk-1}}}$. De forma similar para el otro. Luego calcula para encontrar${\displaystyle E[X_{k+1}|X_{k}]=X_{k}}$.

Defina el tiempo de parada${\displaystyle T}$como mínimo${\displaystyle k}$de tal manera que${\displaystyle X_{k}=0}$, o${\displaystyle n-1}$si no existe tal cosa${\displaystyle k}$Entonces, la probabilidad de que el candidato A lidere todo el tiempo es simplemente${\displaystyle E[X_{T}]}$, que por el teorema de parada opcional es${\displaystyle E[X_{T}]=E[X_{0}]}$. Utilizando el líder final como${\displaystyle S_{n}}$y la definición de${\displaystyle X_{k}}$a las 0,${\displaystyle E[X_{0}]={\frac {p-q}{p+q}}}$.

Bertrand expresó la solución como

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

dónde${\displaystyle \mu =p+q}$es el número total de votantes y${\displaystyle m=p}$es el número de votantes para el primer candidato. Afirma que el resultado se deriva de la fórmula

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

dónde${\displaystyle P_{m,\mu }}$es el número de secuencias favorables, pero "parece probable que un resultado tan simple pueda demostrarse de una manera más directa". De hecho, Désiré André pronto produjo una demostración más directa. Su enfoque a menudo es etiquetado erróneamente como "el principio de reflexión" por autores modernos, pero en realidad utiliza una permutación. Demuestra que las secuencias "desfavorables" (aquellas que alcanzan un empate intermedio) consisten en un número igual de secuencias que comienzan con A que las que comienzan con B. Toda secuencia que comienza con B es desfavorable, y hay${\displaystyle {\tbinom {p+q-1}{q-1}}}$tales secuencias con una B seguida de una secuencia arbitraria de ( q - 1) B y p A. Cada secuencia desfavorable que comienza con A puede transformarse en una secuencia arbitraria de ( q - 1) B y p A encontrando la primera B que viola la regla (al causar un empate en el recuento de votos) y eliminándola, e intercambiando el orden de las partes restantes. Para revertir el proceso, tome cualquier secuencia de ( q - 1) B y p A y busque desde el final para encontrar dónde el número de A excede por primera vez el número de B, y luego intercambie el orden de las partes y coloque una B en medio. Por ejemplo, la secuencia desfavorable AAB B ABAA corresponde de forma única a la secuencia arbitraria ABAA AAB . De esto, se deduce que el número de secuencias favorables de p A y q B es

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

y por lo tanto la probabilidad requerida es

${\displaystyle {\frac {p-q}{p+q}}}$

Como era de esperar.

El problema original consiste en hallar la probabilidad de que el primer candidato siempre esté estrictamente por delante en el recuento de votos. En su lugar, se puede considerar el problema de hallar la probabilidad de que el segundo candidato nunca esté por delante (es decir, se permiten empates). En este caso, la respuesta es

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

El problema variante se puede resolver mediante el método de reflexión de forma similar al problema original. El número de secuencias de votación posibles es${\displaystyle {\tbinom {p+q}{q}}}$Una secuencia se considera "mala" si el segundo candidato siempre va por delante, y si se puede enumerar el número de secuencias malas, entonces se puede encontrar el número de secuencias "buenas" por resta y se puede calcular la probabilidad.

Represente una secuencia de votación como una trayectoria reticular noreste en el plano cartesiano de la siguiente manera:

• Comience el camino en (0,  0)
• Cada vez que se reciba un voto para el primer candidato, muévase 1 unidad a la derecha.
• Cada vez que se reciba un voto para el segundo candidato, avance 1 unidad.

Cada una de estas rutas corresponde a una secuencia única de votos y termina en ( p , q ). Una secuencia es "buena" precisamente cuando la ruta correspondiente nunca supera la diagonal y  = x ; de forma equivalente, una secuencia es "mala" precisamente cuando la ruta correspondiente toca la línea y = x + 1.     

Para cada camino "malo" P , defina un nuevo camino P ′ reflejando la parte de P hasta el primer punto donde toca la línea que lo atraviesa. P ′ es un camino desde (−1,  1) hasta ( p , q ). La misma operación aplicada nuevamente restaura el P original . Esto produce una correspondencia biunívoca entre los caminos "malos" y los caminos desde (−1, 1) hasta ( p , q ). El número de estos caminos es   ${\displaystyle {\tbinom {p+q}{q-1}}}$y ese es el número de secuencias 'malas'. Esto deja el número de secuencias 'buenas' como

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

Dado que hay${\displaystyle {\tbinom {p+q}{q}}}$En conjunto, la probabilidad de que una secuencia sea buena es${\displaystyle {\tfrac {p+1-q}{p+1}}}$.

De hecho, las soluciones al problema original y al problema variante están fácilmente relacionadas. Para que el candidato A esté estrictamente por delante durante todo el recuento de votos, debe recibir el primer voto y para los votos restantes (ignorando el primero) debe estar estrictamente por delante o empatado durante todo el recuento. Por lo tanto, la solución al problema original es

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

según sea necesario.

Por el contrario, el caso de empate se puede derivar del caso de no empate. Nótese que el número de secuencias de no empate con p+1 votos para A es igual al número de secuencias de empate con p votos para A. El número de votos de no empate con p + 1 votos para A es${\displaystyle {\tfrac {p+1-q}{p+1+q}}{\tbinom {p+1+q}{q}}}$, que mediante manipulación algebraica es ${\displaystyle {\tfrac {p+1-q}{p+1}}{\tbinom {p+q}{q}}}$, por lo que la fracción de secuencias con p votos para A votos es${\displaystyle {\tfrac {p+1-q}{p+1}}}$.

• Teoremas de votación, antiguos y nuevos , L. Addario-Berry, BA Reed , 2007, en Horizontes de combinatoria , Editores Ervin Győri, G. Katona, Gyula OH Katona, László Lovász , Springer, 2008, ISBN 978-3-540-77199-9

• El problema de las papeletas electorales (incluye escaneos de los artículos originales en francés y traducciones al inglés)
• Bernard Bru, Les leçons de calcul des probabilités de Joseph Bertrand , historia del problema (en francés)
• Weisstein, Eric W. "Problema electoral" . MundoMatemático .