¿Cuál es la probabilidad de perder en el partido del equipo IMO de Taiwán?

Question

El recuento de Evan Chen sobre el viaje del equipo taiwanés de la OMI registró un juego que los miembros del equipo jugaron en su tiempo libre, que es el siguiente:

Hay $n$ miembros del equipo (en el caso actual $n=6$ pero aquí simplemente tomamos $n\geq2$ )Cada miembro del equipo apunta a otro miembro del equipo (que debe ser diferente de él mismo) y así obtenemos un grafo (dirigido) con $n$ vértices y $n$ bordes. Tiene una arista más que un árbol y, por tanto, debe contener un ciclo. Cualquier miembro que sea un vértice de cualquier ciclo en este gráfico pierde el juego. (Así que es posible que todos pierdan pero es imposible que nadie pierda).

Suponiendo que todo el mundo elige a la persona que señala al azar, ¿cuál es la probabilidad de que un jugador pierda la partida?

Referencia: El recuento de Evan Chen

Answer 1

Lo es: $$p_{1}+\cdots+p_{n-1}$$ donde: $$p_{k}:=\frac{n-2}{n-1}\frac{n-3}{n-1}\cdots\frac{n-k}{n-1}\frac{1}{n-1}$$ es la probabilidad de perder junto con $k$ compañeros que están en el mismo ciclo (perdedor).

---

adición:

Empecemos por denotar al jugador que comienza con $P_0$ y el jugador que señala con $P_1$ . Denota inductivamente el jugador señalado por $P_{n-1}$ con $P_n$ . Entonces $P_0$ perderá con exactitud $k$ en el mismo ciclo si $P_0,\dots,P_{k-1}$ son distintos y $P_k=P_0$ .

Si, por ejemplo $P_0$ pierde junto con $3$ compañeros $P_1$ debe apuntar a $P_2\neq P_0$ (probabilidad $\frac{n-2}{n-1}$ ), $P_2$ debe apuntar a $P_3\notin\{P_0,P_1\}$ (probabilidad $\frac{n-3}{n-1}$ ) y finalmente $P_3$ debe apuntar a $P_0$ (probabilidad $\frac1{n-1}$ ).

Esto lleva a $p_3=\frac{n-2}{n-1}\frac{n-3}{n-1}\frac{1}{n-1}$ .

Answer 2

De forma equivalente a las otras respuestas hasta ahora, es $\displaystyle\sum_{k=2}^n\frac{(k-1)!\binom{n-1}{k-1}}{(n-1)^k}$ o para que la suma salga bien (añadiendo el primer término que falta y desplazando el índice $k$ por uno): $$ -\frac{1}{n-1}+\displaystyle\sum_{k=0}^{n-1}\frac{k!\binom{n-1}{k}}{(n-1)^{k+1}} $$

Me gustaría señalar que esto se puede simplificar mediante el uso de funciones generadoras. Empezamos con la función generadora simple $$ (1+x)^{n-1}=\displaystyle\sum_{k=0}^{n-1}\binom{n-1}{k}x^k. $$ Tenga en cuenta que para $y$ positivo, $\displaystyle\int_0^{\infty}x^ke^{-x/y}dx=y^{k+1}\displaystyle\int_{0}^{\infty}z^ke^{-z}dz=k!y^{k+1}$ (utilizando la sustitución $x=yz$ ).

Esta es una herramienta conveniente que nos permite obtener la $k!$ en nuestra función generadora. En particular, encontramos que

$$ \displaystyle\int_0^{\infty}(1+x)^{n-1}e^{-x/y}dx=\displaystyle\sum_{k=0}^{n-1}\binom{n-1}{k}\displaystyle\int_0^{\infty}x^ke^{-x/y}dx=\displaystyle\sum_{k=0}^{n-1}k!\binom{n-1}{k}y^{k+1}. $$

Ahora la idea es clara, ya que tenemos esa subsunción $y=\frac{1}{n-1}$ , $$ \displaystyle\sum_{k=0}^{n-1}\frac{k!\binom{n-1}{k}}{(n-1)^{k+1}}=\displaystyle\int_0^{\infty}(1+x)^{n-1}e^{-(n-1)x}dx=\displaystyle\int_0^{\infty}((1+x)e^{-x})^{n-1}dx, $$ por lo que tenemos que la probabilidad con $n$ personas es $$ P_n=-\frac{1}{n-1}+\displaystyle\int_0^{\infty}((1+x)e^{-x})^{n-1}dx. $$ Esta formulación integral es agradable porque nos permite evaluar esto asintóticamente, ya que la integral es $$ \displaystyle\int_0^{\infty}e^{(n-1)(\ln(1+x)-x)}dx\approx\displaystyle\int_0^{\infty}e^{(n-1)(-x^2/2)}dx $$ para grandes $n$ que es una integral gaussiana y se evalúa como $\sqrt{\frac{\pi}{2(n-1)}}$ . El $\frac{1}{n-1}$ puede ser ignorado y obtenemos un resultado asintótico de $\sqrt{\frac{\pi}{2(n-1)}}$ .

Answer 3

Juguemos a este juego con $n$ personas. Llamaré a un gráfico que viene de una jugada de este juego un redondo . Como cada persona tiene $n-1$ opciones de a quién señalar, hay $(n-1)^{n}$ posibles rondas.

Calculemos el número de rondas en las que Persona $1$ pierde.

Por supuesto, en cada ronda, cada vértice tiene exactamente un grado de salida $1$ . De ello se deduce que si Persona $1$ pierde en una ronda determinada, entonces el ciclo en el que están es un ciclo dirigido y, además, están en exactamente un ciclo dirigido.

Si la persona $1$ pierde porque están en una dirección $k$ -ciclo para algunos $k\geq 2$ entonces hay ${n-1\choose k-1}$ opciones de las personas que pueden participar en un $k$ -con el ciclo, y $(k-1)!$ diferentes ciclos dirigidos que involucran sólo a estas personas. Así que hay $(k-1)!{n-1\choose k-1}(n-1)^{n-k}$ tales rondas.

Obsérvese que aquí no estamos contando de más en ninguna parte, ya que no puede darse el caso de que la Persona $1$ está en más de un ciclo.

Por lo tanto, la probabilidad de que la persona $1$ perder es $$\frac{\sum_{k=2}^n(k-1)!{n-1\choose k-1}(n-1)^{n-k}}{(n-1)^n}$$

Para $n=6$ esto equivale a una probabilidad de algo más de la mitad ( $0.50208$ ).