Teorema de votación de Bertrand

Teorema que da la probabilidad de que un ganador de elecciones supere al perdedor durante todo el recuento.

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?" La respuesta es

${\displaystyle {\frac {p-q}{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 prueba basada en una fórmula general para el número de secuencias favorables utilizando una relación de recursión . Señala que parece probable que un resultado tan simple pueda probarse mediante un método más directo. Tal prueba fue dada por Désiré André ^[6], basándose en la observación de que las secuencias desfavorables pueden dividirse en dos casos igualmente probables, uno de los cuales (el caso en el 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 votación de Bertrand está relacionado con el lema del ciclo . Ofrecen fórmulas similares, pero el lema del ciclo considera los cambios circulares de un orden de recuento de votos determinado en lugar de todas las permutaciones.

Ejemplo

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

• Aaaaaaaa
• AABAB
• Abaab
• BAAAAB
• AABBA
• ABABA
• BAABA
• ABBAA
• BABAA
• BBAAA

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

Para cada columna, el recuento de votos para A siempre es mayor que el 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 de la cuarta votación, 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 de hecho igual a lo que predice el teorema. ${\displaystyle {\frac {3-2}{3+2}}}$

Problemas equivalentes

Órdenes favorables

En lugar de calcular la probabilidad de que un orden aleatorio de recuento de votos tenga la propiedad deseada, se puede calcular el número de órdenes de recuento favorables y luego dividir por el número total de formas en que se podrían haber contado los votos (este es el método que utilizó Bertrand). El número total de formas es el coeficiente binomial ; la prueba de Bertrand muestra que el número de órdenes favorables en los que se pueden contar los votos es (aunque no da este número explícitamente). Y, de hecho, después de la división, esto da . ${\displaystyle {\tbinom {p+q}{p}}}$ ${\displaystyle {\tbinom {p+q-1}{p-1}}-{\tbinom {p+q-1}{p}}}$ ${\displaystyle {\tfrac {p}{p+q}}-{\tfrac {q}{p+q}}={\tfrac {p-q}{p+q}}}$

Paseos aleatorios

Otro problema equivalente es calcular el número de recorridos aleatorios sobre los números enteros que constan de n pasos de longitud unitaria, comenzando en el origen y terminando en el punto m , que nunca se vuelven negativos. Como n y m tienen la misma paridad y , este número es ${\displaystyle n\geq m\geq 0}$

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

Cuando y es par, se obtiene el número de Catalan . Por lo tanto, la probabilidad de que un recorrido aleatorio nunca sea negativo y vuelva al origen en el momento es . Según la fórmula de Stirling, cuando , esta probabilidad es . ${\displaystyle m=0}$ ${\displaystyle n}$ ${\displaystyle {\frac {1}{{\tfrac {n}{2}}+1}}{\binom {n}{\tfrac {n}{2}}}}$ ${\displaystyle n}$ ${\displaystyle 2^{-n}{\frac {1}{{\tfrac {n}{2}}+1}}{\binom {n}{\tfrac {n}{2}}}}$ ${\displaystyle n\to \infty }$ ${\displaystyle \sim {\frac {\sqrt {2}}{n^{3/2}}}}$

[Obsérvese que tienen la misma paridad de la siguiente manera: sea el número de movimientos "positivos", es decir, hacia la derecha, y sea el número de movimientos "negativos", es decir, hacia la izquierda. Como y , tenemos y . Como y son números enteros, tienen la misma paridad] ${\displaystyle m,n}$ ${\displaystyle P}$ ${\displaystyle N}$ ${\displaystyle P+N=n}$ ${\displaystyle P-N=m}$ ${\displaystyle P={\frac {n+m}{2}}}$ ${\displaystyle N={\frac {n-m}{2}}}$ ${\displaystyle P}$ ${\displaystyle N}$ ${\displaystyle m,n}$

Prueba por reflexión

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

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

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

${\displaystyle =1-2\times (}$la probabilidad de secuencias que coinciden 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 {p-q}{p+q}}}$

Prueba por inducción

Otro método de prueba es por inducción matemática :

• Aflojamos la condición a . Claramente, el teorema es correcto cuando , ya 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). ${\displaystyle p>q}$ ${\displaystyle p\geq q}$ ${\displaystyle p=q}$
• Claramente el teorema es verdadero si p  > 0 y q  = 0 cuando la probabilidad es 1, dado que el primer candidato recibe todos los votos; también es verdadero 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 aquí, ya 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 de la votación final) es: ${\displaystyle a=b}$

${\displaystyle {a \over (a+b)}{(a-1)-b \over (a+b-1)}+{b \over (a+b)}{a-(b-1) \over (a+b-1)}={a-b \over a+b}.}$

• Y lo mismo es cierto para todos los p y q con p  >  q  > 0.

Demostración por el lema del ciclo

Una prueba sencilla se basa en el lema del ciclo de Dvoretzky y Motzkin. ^[8] Llamemos dominante a una secuencia de votaciones si A está estrictamente por delante de B durante todo el recuento de los votos. El lema del ciclo afirma que cualquier secuencia de A y B, donde , tiene permutaciones cíclicas precisamente dominantes. Para ver esto, simplemente ordene la secuencia dada de A y B en un círculo y elimine repetidamente los pares adyacentes AB hasta que solo queden A. Cada uno de estos A fue el comienzo de una permutación cíclica dominante antes de que se eliminara algo. Entonces, de las permutaciones cíclicas de cualquier disposición de votos A y votos B, los votos son dominantes. ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle p>q}$ ${\displaystyle p-q}$ ${\displaystyle p+q}$ ${\displaystyle p-q}$ ${\displaystyle p-q}$ ${\displaystyle p+q}$ ${\displaystyle p}$ ${\displaystyle q}$

Prueba por martingalas

Definamos el proceso estocástico de "conteo inverso" ${\displaystyle n=p+q}$

$${\displaystyle X_{k}={\frac {S_{n-k}}{n-k}};\quad k=0,1,...,n-1}$$¿Dónde está la ventaja del candidato A sobre el B, después de haber contado los votos? ${\displaystyle S_{n-k}}$ ${\displaystyle n-k}$

Reclamación: es un proceso martingala . ${\displaystyle X_{k}}$

Dado , sabemos que , por lo que de los primeros votos, fueron para el candidato A, y fueron para el candidato B. ${\displaystyle X_{k}}$ ${\displaystyle S_{n-k}=(n-k)X_{k}}$ ${\displaystyle n-k}$ ${\displaystyle {\frac {X_{k}+1}{2}}(n-k)}$ ${\displaystyle {\frac {-X_{k}+1}{2}}(n-k)}$

Entonces, con probabilidad , tenemos , y . Lo mismo ocurre con el otro. Luego, calcula para encontrar . ${\displaystyle {\frac {X_{k}+1}{2}}}$ ${\displaystyle S_{n-k-1}=S_{n-k}-1}$ ${\displaystyle X_{k+1}={\frac {n-k}{n-k-1}}X_{k}-{\frac {1}{n-k-1}}}$ ${\displaystyle E[X_{k+1}|X_{k}]=X_{k}}$

Defina el tiempo de parada como el mínimo tal que , o si no hay tal . Entonces la probabilidad de que el candidato A esté al frente todo el tiempo es simplemente , que por el teorema de parada opcional es ${\displaystyle T}$ ${\displaystyle k}$ ${\displaystyle X_{k}=0}$ ${\displaystyle n-1}$ ${\displaystyle k}$ ${\displaystyle E[X_{T}]}$ ${\displaystyle E[X_{T}]=E[X_{0}]={\frac {p-q}{p+q}}}$

Pruebas de Bertrand y André

Bertrand expresó la solución como

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

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

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

donde 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 prueba más directa. Su enfoque a menudo es etiquetado erróneamente como "el principio de reflexión" por los autores modernos, pero de hecho utiliza una permutación. Muestra 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 existen 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 (haciendo que los recuentos de votos empaten) y eliminándola, e intercambiando el orden de las partes restantes. Para invertir 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 primero al número de B, y luego intercambie el orden de las partes y coloque una B en el medio. Por ejemplo, la secuencia desfavorable AAB B ABAA corresponde únicamente 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 P_{m,\mu }}$ ${\displaystyle {\tbinom {p+q-1}{q-1}}}$

${\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 se esperaba.

Variante: se permiten corbatas

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

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

El problema de la variante se puede resolver mediante el método de reflexión de una manera similar al problema original. El número de secuencias de votos posibles es . Llamemos a una secuencia "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" mediante la resta y se puede calcular la probabilidad. ${\displaystyle {\tbinom {p+q}{q}}}$

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

• Iniciar la ruta en (0, 0)
• Cada vez que se recibe un voto para el primer candidato, se mueve 1 unidad a la derecha.
• Cada vez que se recibe un voto para el segundo candidato se sube 1 unidad.

Cada uno de estos caminos corresponde a una secuencia única de votos y terminará en ( p , q ). Una secuencia es "buena" exactamente cuando el camino correspondiente nunca pasa por encima de la línea diagonal y  =  x ; equivalentemente, una secuencia es "mala" exactamente cuando el camino correspondiente toca la línea y  =  x  + 1.

Camino 'malo' (azul) y su camino reflejado (rojo)

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

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

Como hay todos ellos en total, la probabilidad de que una secuencia sea buena es . ${\displaystyle {\tbinom {p+q}{q}}}$ ${\displaystyle {\tfrac {p+1-q}{p+1}}}$

De hecho, las soluciones del problema original y del problema de la variante se relacionan fácilmente. 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 del 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 sin empate con p+1 votos para A es igual al número de secuencias empatadas con p votos para A. El número de votos sin empate con p + 1 votos para A votos es , que por manipulación algebraica es , por lo que la fracción de secuencias con p votos para A votos es . ${\displaystyle {\tfrac {p+1-q}{p+1+q}}{\tbinom {p+1+q}{q}}}$ ${\displaystyle {\tfrac {p+1-q}{p+1}}{\tbinom {p+q}{q}}}$ ${\displaystyle {\tfrac {p+1-q}{p+1}}}$

Notas

1. Barton, DE; Mallows, CL (1965). "Algunos aspectos de la secuencia aleatoria". Ann. Math. Statist . 36 : 236–260. doi : 10.1214/aoms/1177700286 .
2. Feller, William (1968), Introducción a la teoría de la probabilidad y sus aplicaciones, Volumen I (3.ª ed.), Wiley, pág. 69.
3. Whitworth, WA (1878). «Disposiciones de m cosas de un tipo y n cosas de otro tipo bajo ciertas condiciones de prioridad». Messenger of Math . 8 : 105–114 . Consultado el 25 de mayo de 2024 .
4. Whitworth, WA (1886). "Capítulo V". Elección y azar (cuarta edición). Cambridge: Deighton, Bell and Co.
5. J. Bertrand, Solution d'un problème, Comptes Rendus de l'Académie des Sciences de Paris 105 (1887), 369.
6. D. André, Solution directe du problème résolu par M. Bertrand, Comptes Rendus de l'Académie des Sciences, París 105 (1887) 436–437.
7. Renault, Marc (2008). "Perdido (y encontrado) en la traducción: el método actual de André y su aplicación al problema generalizado de las papeletas". Amer. Math. Monthly . 115 (4): 358–363. doi :10.1080/00029890.2008.11920537. JSTOR  27642480.
8. Dvoretzky, Aryeh; Motzkin, Theodore (1947), "Un problema de arreglos", Duke Mathematical Journal , 14 (2): 305–313, doi :10.1215/s0012-7094-47-01423-3

Referencias

• 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 

Enlaces externos

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