En combinatoria , el problema de la boleta de Bertrand es la pregunta: "En una elección en la que 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 el conteo?" La respuesta es
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]
En el artículo original de Bertrand, esboza una demostración basada en una fórmula general para el número de secuencias favorables usando una relación de recursividad . Señala que parece probable que un resultado tan simple pueda probarse mediante un método más directo. Désiré André dio tal prueba , [3] 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; prueba la igualdad mediante una biyección explícita . Una variación de su método se conoce popularmente como método de reflexión de André , aunque André no utilizó ninguna reflexión. [4]
Ejemplo
Suponga que hay 5 votantes, de los cuales 3 votan por el candidato A y 2 votan por el candidato B (entonces p = 3 yq = 2). Hay diez posibilidades para el orden de los votos emitidos:
- AAABB
- AABAB
- ABAAB
- BAAAB
- AABBA
- ABABA
- BAABA
- ABBAA
- BABAA
- BBAAA
Para la orden AABAB , el recuento de votos a medida que avanza la elección es:
Candidato | A | A | B | A | B |
A | 1 | 2 | 2 | 3 | 3 |
B | 0 | 0 | 1 | 1 | 2 |
Para cada columna de la cuenta para A es siempre mayor que el recuento de B por lo que el A es siempre estrictamente por delante de B . Para la orden AABBA, el recuento de votos a medida que avanza la elección es:
Candidato | A | A | B | B | A |
A | 1 | 2 | 2 | 2 | 3 |
B | 0 | 0 | 1 | 2 | 2 |
Para este fin, B está ligado con una después de la cuarta votación, por lo que A no es siempre estrictamente por delante de B . De las 10 órdenes posibles, A siempre está por delante de B solo para AAABB y AABAB . Entonces, la probabilidad de que A siempre esté estrictamente adelante es
y esto es de hecho igual a como predice el teorema.
Problemas equivalentes
En lugar de calcular la probabilidad de que un orden de recuento de votos aleatorio 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 utilizado por Bertrand). El número total de vías es el coeficiente binomial ; La prueba de Bertrand muestra que el número de órdenes favorables en las que contar los votos es(aunque no da este número explícitamente). Y de hecho, después de la división, esto da.
Otro problema equivalente es calcular el número de recorridos aleatorios sobre los enteros que constan de n pasos de longitud unitaria, comenzando en el origen y terminando en el punto m , que nunca se vuelven negativos. Suponiendo n y m tienen la misma paridad y n ≥ m ≥ 0, este número es
Cuando m = 0 y n es par, esto da el número catalán .
Prueba por reflejo
Para que A esté estrictamente por delante de B durante el recuento de votos, no puede haber empates. Separe las secuencias de conteo 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, refleje los votos hasta el punto del primer empate (por lo que cualquier A se convierte en B, y viceversa) para obtener una secuencia que comience con B. Por lo tanto, cada secuencia que comience con A y alcanza 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, por lo que la probabilidad de que A siempre lidere la votación es
- la probabilidad de secuencias que empatan en algún punto
- la probabilidad de secuencias que se unen en algún punto y comiencen con A o B
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 adelante después de que se hayan contado todos los votos (por lo que la probabilidad es 0).
- 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 cierto cuando p = q > 0 como acabamos de ver.
- Suponga 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 casoaquí, puesto que ya hemos dispuesto de él antes.) A continuación, considerando el caso con p = una y q = b , el último votos contados es ya sea para el primer candidato con una probabilidad de un / ( un + b ), o para la segunda con probabilidad b / ( a + b ). Entonces, la probabilidad de que el primero esté por delante durante el conteo hasta el penúltimo voto contado (y también después del voto final) es:
- Y lo que es cierto para todos los p y q con p > q > 0.
Prueba por permutación
Una prueba simple se basa en el hermoso ciclo Lema de Dvoretzky y Motzkin. [5] Llame a una secuencia de votación dominante si A está estrictamente por delante de B durante el recuento de votos. El ciclo lema afirma que cualquier secuencia de Como y B's, donde , tiene precisamente permutaciones cíclicas dominantes. Para ver esto, simplemente organice la secuencia dada de A y B en un círculo y elimine repetidamente los pares AB adyacentes hasta que solo Los A permanecen. Cada una de estas A fue el comienzo de una permutación cíclica dominante antes de que se eliminara algo. Entonces fuera de permutaciones cíclicas de cualquier arreglo de A vota y Los votos B están dominando.
Pruebas de Bertrand y André
Bertrand expresó la solución como
dónde es el número total de votantes y es el número de votantes del primer candidato. Afirma que el resultado se sigue de la fórmula
dónde es el número de secuencias favorables, pero "parece probable que un resultado tan simple pueda mostrarse de una manera más directa". De hecho, pronto Désiré André presentó 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. 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 haytales secuencias con una B seguida de una secuencia arbitraria de ( q -1) B y p A. Cada secuencia desfavorable que comienza con A se puede transformar en una secuencia arbitraria de ( q -1) B yp A al encontrar el primer B que viola la regla (al hacer que el conteo de votos empate) y eliminarlo e intercambiar 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 Entre. 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
y así la probabilidad requerida es
como se esperaba.
Variante: se permiten lazos
El problema original es encontrar 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 encontrar la probabilidad de que el segundo candidato nunca esté por delante (es decir, se permiten empates). En este caso, la respuesta es
El problema de la variante se puede resolver mediante el método de reflexión de manera similar al problema original. El número de posibles secuencias de votación es. Llame a una secuencia "mala" si el segundo candidato alguna vez está por delante, y si el número de secuencias malas se puede enumerar, entonces el número de secuencias "buenas" se puede encontrar por sustracción y se puede calcular la probabilidad.
Represente una secuencia de votación como una ruta de celosía en el plano cartesiano de la siguiente manera:
- Inicie la ruta en (0, 0)
- Cada vez que se reciba un voto por el primer candidato, muévase 1 unidad hacia la derecha.
- Cada vez que se reciba un voto para el segundo candidato, suba 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 la ruta correspondiente nunca pasa por encima de la línea diagonal y = x ; de manera equivalente, una secuencia es "mala" exactamente 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 que toca la línea que lo cruza. P ′ es una ruta de (−1, 1) a ( p , q ). La misma operación aplicada nuevamente restaura la P original . Esto produce una correspondencia uno a uno entre las rutas "malas" y las rutas de (-1, 1) a ( p , q ). El número de estos caminos esy ese es el número de secuencias "malas". Esto deja el número de secuencias 'buenas' como
Puesto que hay en conjunto, la probabilidad de que una secuencia sea buena es .
De hecho, las soluciones al problema original y al problema de la variante se relacionan fácilmente. Para que el candidato A esté estrictamente adelante durante todo el conteo de votos, debe recibir el primer voto y para los votos restantes (ignorando el primero) debe estar estrictamente adelante o empatado durante todo el conteo. Por tanto, la solución al problema original es
según sea necesario.
Por el contrario, el caso de empate puede derivarse del caso de no empate. Tenga en cuenta 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 votos A es, que por manipulación algebraica es , por lo que la fracción de secuencias con p votos para A votos es.
Notas
- ^ Feller, William (1968), Introducción a la teoría de la probabilidad y sus aplicaciones, Volumen I (3ª ed.), Wiley, p. 69.
- ↑ J. Bertrand, Solution d'un problème, Comptes Rendus de l'Académie des Sciences de Paris 105 (1887), 369.
- ↑ D. André, Solution directe du problème resolu par M. Bertrand, Comptes Rendus de l'Académie des Sciences, París 105 (1887) 436–437.
- ↑ Renault, Marc, Lost (and found) en traducción: método actual de André y su aplicación al problema de la papeleta generalizada. Amer. Matemáticas. Mensual 115 (2008), no. 4, 358--363.
- ^ Dvoretzky, Aryeh; Motzkin, Theodore (1947), "Un problema de arreglos", Duke Mathematical Journal , 14 : 305–313, doi : 10.1215 / s0012-7094-47-01423-3
Referencias
- Teoremas de la boleta, viejos 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
- The Ballot Problem (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 de la balota" . MathWorld .