Elección: probabilidad de que A esté en la delantera desde el primer voto en

Question

Estaba tratando de resolver el siguiente problema:

En una elección, el candidato A recibe n votos y el candidato B recibe m votos, donde n > m. Suponga que en el conteo de los votos todas las posibles combinaciones de los n + m votos son igualmente probables. Sea $P_{n, m}$ la probabilidad de que desde el primer voto en adelante A esté siempre en la delantera. Encuentre

(a - i) $P_{2, 1}$, $P_{3, 1}$, $P_{n, 1}$, $P_{3, 2}$, $P_{4, 2}$, $P_{n, 2}$, $P_{4, 3}$, $P_{5, 3}$, $P_{5, 4}$

(j) Realice una conjetura sobre el valor de $P_{n, m}$.

Resolví todas las partes y mi conjetura fue que $P_{n, m} = \frac{n - m}{n + m}$ lo cual verifiqué un poco con una pequeña aplicación que escribí para comprobar mis soluciones (JavaScript: https://repl.it/EWNM/35).

Mientras trabajaba en los ejercicios (a - i) seguía encontrando la fórmula $P_{n, m} = x * \frac{n!m!}{(n+m)!}$. La parte $\frac{n!m!}{(n + m)!}$ es la probabilidad de que ocurra uno de los resultados. El $x$ sería el número de resultados donde A lidera desde el primer voto. Estaba tratando de encontrar la fórmula para $x$ incluso antes de llegar a la parte (j) pero no pude. Después de averiguar la probabilidad $P_{n, m} = \frac{n - m}{n + m}$, pude resolver para $x$ y obtuve $x = \frac{(n - m)(n + m - 1)!}{n!m!}.

¿Cómo podría haber encontrado $x$ sin saber que $P_{n, m} = \frac{n - m}{n + m}$?

Entonces, en lugar de pensar en probabilidades, ¿cuántas combinaciones diferentes de A y B son posibles donde el número de A en cualquier posición es mayor que el número de B??

¿Existe alguna fórmula general o forma de pensar sobre este tipo de problemas? ¿Cuál sería la solución para A siempre liderando por 2, 3, ..., i?

Gracias, Norbert

Answer 1

Aquí hay un relato más detallado del argumento de reflexión que el que se presenta en el artículo de Wikipedia. Avísame si hay alguna parte de la que aún desees que profundice.

Vamos a considerar todas las posibles secuencias de boletas. La idea de la prueba es dividirlas en tres categorías:

1. Secuencias donde $A$ siempre está adelante
2. Secuencias donde $A$ empieza adelante (es decir, obtiene el primer voto), pero $B$ lo alcanza en algún momento
3. Secuencias donde $B$ empieza adelante

Para concretar, digamos que $n=3$, $m=2$. Entonces las categorías se dividen así:

1. AABAB, AAABB
2. AABBA (B alcanza después de la boleta #4), ABAAB (B alcanza después de la boleta #2), ABABA (B alcanza después de la boleta #2), ABBAA (B alcanza después de la boleta #2)
3. BAAAB, BAABA, BABAA, BBAAA

Observa que la categoría 2 y la categoría 3 son del mismo tamaño. ¡Esto no es una coincidencia! La idea de "reflexión" es emparejar las secuencias de la categoría 2 con las de la categoría 3.

Para hacer esto, primero comentamos que para cualquier secuencia en cualquiera de las categorías, el recuento estará empatado en algún momento. Para las secuencias de la categoría 2, esto es por definición; si $B$ alcanza a $A$, entonces $A$ y $B$ están empatados. Para las secuencias de la categoría 3, es porque $B$ empieza adelante, pero $A$ eventualmente debe ganar. Así que en algún momento antes de ganar, $A$ debe alcanzar a $B$ y ambos estarán empatados.

Para concretar, vamos a enfocarnos en el momento final en que cada una de estas secuencias está empatada. En nuestro conjunto de ejemplos, escribiré un | para indicar este punto. Así que las dos categorías son:

2. AABB|A, AB|AAB, ABAB|A, ABBA|A
3. BA|AAB, BAAB|A, BABA|A, BBAA|A

A continuación, vamos a ver qué sucede si invertimos todos los votos antes de un |. Por ejemplo, AABB|A se convertiría en BBAA|A. Observa que:

• Siempre podemos hacer esto y obtener otra secuencia de boleta válida, porque el | denota un punto donde el recuento está empatado, invertir todos los votos no cambia el total final.
• Esto lleva las secuencias de la categoría 2 (que comienzan con una A) a secuencias de la categoría 3 (que comienzan con una B), y viceversa.
• Si lo haces dos veces, vuelves a la secuencia con la que empezaste.

Esto significa que proporciona una forma de emparejar las secuencias de la categoría 2 con las de la categoría 3, tal como queríamos. En nuestro ejemplo específico, este emparejamiento es:

• AABB|A <=> BBAA|A
• AB|AAB <=> BA|AAB
• ABAB|A <=> BABA|A
• ABBA|A <=> BAAB|A

Ahora, casi hemos terminado. Solo necesitamos una observación más: la categoría 3 simplemente consiste en secuencias que comienzan con una B. Dado que $m$ de $n+m$ boletas son de tipo $B$, eso significa que la probabilidad de terminar en la categoría 3 es $\frac{m}{n+m}$. ¡Pero la categoría 2 es del mismo tamaño que la categoría 3! Dado que todas las secuencias de boletas tienen la misma probabilidad, eso significa que la probabilidad de terminar en la categoría 2 también es $\frac{m}{n+m}$. Entonces la probabilidad de terminar en la categoría 1 es $$ 1-2\frac{m}{n+m}=\frac{n+m-2m}{n+m}=\frac{n-m}{n+m} $$ tal como habías conjeturado.