¿Cómo modelizar la probabilidad de este intercambio de regalos?

Question

Hay un intercambio de regalos con $N$ personas utilizando las siguientes reglas:

1. Todo el mundo empieza con un regalo envuelto elegido al azar.
2. Por turnos, los participantes tiran un dado de 6 caras para determinar qué acción realizar. Sacar un 1 o un 2 significa que esa persona abre el regalo que tiene delante y queda fuera de la rotación. Sacar un 3, 4, 5 o 6 provoca otros eventos que cambian los regalos envueltos (es decir, esa persona aún no puede abrir su regalo).
3. El juego termina cuando se abren todos los regalos.

Quería saber cuántos turnos debería durar este intercambio de regalos hasta su finalización, pero no he conseguido averiguar cómo modelarlo. Intento reestructurarlo como "¿Cuál es la probabilidad de que termine en $X$ vueltas?", pero seguía sin llegar lejos. ¿Alguna idea?

Sé que la probabilidad de abrir un regalo en cualquier turno es $\frac{2}{6} = \frac{1}{3}$ . Así podría calcular la probabilidad de que el intercambio de regalos termine lo antes posible ( $N$ vueltas para $N$ personas), que sería $\left(\frac{1}{3}\right)^N$ . ¿Cómo puedo ampliar esto para calcular la probabilidad de que el intercambio termine en $X$ turnos, donde cada turno tiene un $\frac{2}{3}$ posibilidad de "no abrir regalos"?

Answer 1

Quería saber cuántos turnos debe durar este intercambio de regalos hasta completarse...

Se pregunta por el número de veces que se espera lanzar el dado. A primera vista, este recuento parece ser una suma de variables aleatorias geométricas. $$C=\sum_{i=1}^n G_i$$ donde $G_i$ es la variable aleatoria geométrica que cuenta el número de veces que hay que lanzar el dado, para el $i$ -enésima persona a eliminar (abrir el regalo) $$G_i\sim G(\frac{1}{3}).$$ Lo que le interesa es el número de intentos necesarios. $$E(C)=E(\sum_{i=1}^n G_i)=\sum_{i=1}^n E(G_i)=nE(G)=n\cdot\frac{1}{p}$$ donde $p$ es la probabilidad de éxito en cada intento, $\frac{1}{3}$ en tu caso. Para completar, el número esperado de ensayos/vueltas para una variable aleatoria geométrica es $\frac{1}{p}$ .

Así, para un grupo de a $100$ personas, se necesitaría $$100\cdot\frac{1}{\frac{1}{3}}=300$$ turnos para que todos ellos sean eliminados (abran sus regalos).

Modelización del intercambio de regalos - Distribución binomial negativa

Podrías haber preguntado

¿Cuál es la probabilidad de que el $n$ -ésima eliminación (apertura del regalo) va precedida exactamente de $N$ fallos (y $n-1$ eliminaciones)?

y modelar el mismo procedimiento. Entonces, la probabilidad de un juego en el que participen $n$ personas para terminar en el $N$ turno es

$$P(N,n)=\binom{N+n-1}{N}(1-p)^Np^n$$

que es el distribución binomial negativa .

Nota sobre la expectativa de la binomial negativa

Tenga en cuenta que el valor esperado que se cita en la wiki $$\tilde{E}(C)=n\frac{1-p}{p}$$ cuenta el número previsto de fallos. El número sobre el que preguntó y que hemos calculado anteriormente cuenta todos los ensayos. Para obtenerlo a partir de la fórmula citada para el número de fracasos, le añadimos el número de éxitos

$$\tilde{E}(C)+n=n\frac{1-p}{p}+n=n\frac{1}{p}=E(C)$$

Simulación

Probemos la solución con una simulación del juego en numpy.

import numpy as np
def foo(n):
  k=n
  count=0
  while k>0:
   count+=k
   throws=np.random.randint(1,7,k)
   k-=np.sum((throws==1)|(throws==2))
  return count
np.mean([foo(100) for _ in range(10000)])

299.997

La simulación coincide con el resultado.

Espero haber entendido bien su procedimiento. Para mí, una tirada del dado se consideraba un intento/turno.

Answer 2

Ten en cuenta que, en teoría, no hay límite a la duración de la partida: si tienes suficiente mala suerte, en teoría no hay límite a cuántas rondas seguidas puedes obtener un resultado "sin regalos" en el dado. Dicho esto, el número previsto de rondas antes de que se abran todos los N regalos es 3N (como se muestra a continuación), y existe una buena fórmula para calcular la probabilidad de que el juego haya terminado después de $k$ rondas, para cualquier $k$ . Aunque esta probabilidad nunca es exactamente del 100%, se aproxima al 100% a medida que $k$ se hace grande.

El número esperado de rondas es 3N

Podemos relacionar los resultados de este juego con los resultados de un juego relacionado en el que lanzamos una moneda que tiene una probabilidad $\frac{1}{3}$ de HEADS y una probabilidad $\frac{2}{3}$ de COLAS. En concreto, HEADS significa "abre un regalo" y TAILS significa "no abras un regalo".

Existen $N$ regalos en total y el juego termina cuando están todos abiertos. Por lo tanto, el número esperado de rondas antes de que el juego termine es el número esperado de lanzamientos de moneda antes de que $N$ éxitos. El número esperado de lanzamientos de moneda antes de $N$ éxitos es $N/p$ donde $p$ es la probabilidad de éxito. Aquí, "éxito" significa "abrir un regalo", así que:

Expectativa = $\frac{N}{p} = \frac{N}{1/3} = 3N$ rondas para abrir todos los N regalos.

Es decir, se espera que el juego termine después de $3N$ rondas, donde $N$ es el número de regalos que hay que abrir. (Esto tiene sentido: imagínese si la probabilidad de abrir un regalo fuera del 100%, o si fuera de 1/2, y así sucesivamente).

---

Una fórmula para la probabilidad de terminar después de k rondas

Del mismo modo, la probabilidad de que el juego haya terminado después de $M$ turnos es la probabilidad de dar la vuelta $M$ monedas y conseguir como mínimo $N$ cabezas. (La razón por la que está bien conseguir más de $N$ cabezas es porque podemos imaginar que el juego terminó después de $N$ caras y seguíamos tirando monedas de todos modos aunque ya no tuviera ningún efecto).

La probabilidad de voltear $M$ monedas y conseguir al menos $N$ cabezas es:

$$P(M,N) \equiv \sum_{h=N}^M {M \choose h} \left(\frac{1}{3}\right)^h \left(\frac{2}{3}\right)^{M-h} = \left(\frac{2}{3}\right)^M\sum_{h=N}^M {M \choose h} 2^{-h}$$

Esto equivale a la probabilidad de que el juego termine tras $M$ rondas o menos. Desgraciadamente, es una fórmula bastante complicada con muchos términos. En la próxima sección, mostraré cómo podemos utilizar la matemática matricial para obtener una forma más compacta de calcular estas y otras probabilidades.

---

Una fórmula mejorada utilizando matemáticas matriciales

Supongamos que llevamos la cuenta del número $g$ de regalos que hemos abierto hasta ahora. Al principio, $g=0$ y sabemos que el juego termina cuando $g=N$ . En cada ronda $g$ se incrementa (probabilidad 1/3) o permanece igual (probabilidad 2/3).

Como podemos modelizar este problema como varios "estados del mundo" con una probabilidad de transición entre ellos, podemos utilizar una rama de la matemática matricial (en concreto, los procesos de Markov) para calcular eficazmente las probabilidades de los distintos resultados.

Para ello, hacemos una $(N+1)\times (N+1)$ matriz de transición $T$ . La entrada $T_{i,j}$ es la probabilidad de comenzar en el estado $g=i$ e ir al estado $g=j$ después de una ronda. En nuestro caso, tenemos:

$$T_{i,j} = \begin{cases}\frac{1}{3}&\text{if }i=j-1\\\frac{2}{3} &\text{if }i=j<N\\1&\text{if }i=j=N\\0&\text{otherwise}\end{cases}$$

(También hemos incluido la regla de que siempre que $g=N$ permanece en $g=N$ porque el número de regalos abiertos ya no puede aumentar).

Así, por ejemplo, si hay $N=4$ regalos, la matriz de transición es de 5×5 y tiene el siguiente aspecto:

$$T = \begin{bmatrix}\frac{2}{3}&&&&\\\frac{1}{3}&\frac{2}{3}&&&\\&\frac{1}{3}&\frac{2}{3}&&\\&&\frac{1}{3}&\frac{2}{3}&\\&&&\frac{1}{3}&1\end{bmatrix}$$

Ahora resulta que los poderes $T, T^2, T^3, \ldots, T^k$ de la matriz de transición $T$ calcular probabilidades importantes. Específicamente:

La primera columna de $T^k$ enumera las probabilidades de que varios números de regalos estén abiertos después de exactamente $k$ rondas. En particular, la entrada inferior izquierda de $T^k$ es la probabilidad de que todos $N$ regalos están abiertos-así que el juego ha terminado-por el $k$ ª ronda.

Esto proporciona una forma compacta de calcular la probabilidad de que el juego haya terminado por el $k$ ª ronda, para cualquier $k$ .

Answer 3

Para terminar exactamente $X$ vueltas que hay que seleccionar $X-N$ veces de la primera $X-1$ para no tener ningún regalo abierto, entonces abre uno en el turno $X$ . La oportunidad es entonces ${X-1 \choose X-N}(\frac 23)^{X-N}(\frac 13)^N$