Tiradas esperadas para lanzar cada número de un dado un número impar de veces

Question

Nuestra familia ha aprendido recientemente a jugar a un sencillo juego llamado "Oh Dear". Cada jugador tiene seis cartas (As, 2, 3, 4, 5, 6) boca arriba, y se turnan para tirar los dados. Sea cual sea el número que saque el dado, se da la vuelta a la carta correspondiente. El ganador es el jugador que pone todas sus cartas boca abajo primero, pero si sale el número de una carta que ha sido puesta boca abajo, entonces esa carta se vuelve a poner boca arriba (y se dice "¡Oh querido!").

Quiero calcular la duración prevista de una partida (en tiradas de dados). Me interesa, en primer lugar, calcular esto en el caso de un jugador que juega solo, y luego también la cuestión de cómo cambia la respuesta con múltiples jugadores. Esto equivale a calcular el número esperado de veces que un jugador debe tirar los dados para haber sacado cada número del dado un número impar de veces. (Asumo un dado justo de seis caras, pero de nuevo estaría interesado en una solución más general también).

Es sencillo calcular las probabilidades de ganar lo antes posible desde cualquier posición, pero no estoy seguro de cómo calcular el número esperado de tiradas antes de que un jugador gane...

Answer 1

Puede pensar en su problema como un Cadena de Markov es decir, un conjunto de estados con ciertos probabilidades de transición entre estados. Empiezas en un estado (todas las cartas boca arriba) y terminas en un estado de absorción (todas las cartas boca abajo). Su pregunta se refiere al número esperado de pasos hasta alcanzar ese estado de absorción, ya sea para una sola cadena, o para el número mínimo esperado de pasos a través de $n$ cadenas de Markov independientes que se ejecutan simultáneamente.

Y en realidad hay dos formas ligeramente diferentes de ver esto. La primera, como comenta whuber es considerar las seis tarjetas como seis bits diferentes $\{0,1\}$ y considerar el estado como un vector de seis en $\{0,1\}^6$ es decir, el hipercubo discreto de seis dimensiones. Comenzamos en el vértice $(0,0,0,0,0,0)$ y el estado de absorción es $(1,1,1,1,1,1)$ . Un paso puede llevarnos a un vértice adyacente, en el que se invierte exactamente un bit con respecto al estado original. Es decir, las transiciones nos llevan de un vértice a cualquier vértice vecino con Distancia Hamming exactamente uno, y cada uno de esos vecinos tiene la misma probabilidad de ser el siguiente estado.

Hay algo de literatura sobre paseos aleatorios y cadenas de Markov en cubos discretos con distancias de Hamming, pero nada que haya podido localizar a corto plazo. Tenemos un hilo muy bonito sobre Paseo aleatorio por las aristas de un cubo que podría ser interesante.

---

La segunda forma de verlo es utilizar el hecho de que todas las cartas son intercambiables (suponiendo un dado justo). Entonces podemos utilizar sólo siete estados diferentes, correspondientes al número de cartas boca abajo. Empezamos en el estado $i=0$ y el estado de absorción es $i=6$ . Las probabilidades de transición dependen del estado en el que nos encontremos:

• Desde $i=0$ (todas las cartas boca arriba), tiraremos una carta hacia abajo y terminaremos con una carta boca abajo con certeza: tenemos la probabilidad de transición $p_{01}=1$ (y $p_{0j}=0$ para $j\neq 1$ ).
• Desde $i=1$ podemos llegar a $j=0$ con probabilidad $p_{10}=\frac{1}{6}$ y $j=2$ con probabilidad $p_{12}=\frac{5}{6}$ .

En general, obtenemos lo siguiente matriz de transición :

$$ T=\begin{pmatrix} 0 & \frac{6}{6} & 0 & 0 & 0 & 0 & 0 \\ \frac{1}{6} & 0 & \frac{5}{6} & 0 & 0 & 0 & 0 \\ 0 & \frac{2}{6} & 0 & \frac{4}{6} & 0 & 0 & 0 \\ 0 & 0 & \frac{3}{6} & 0 & \frac{3}{6} & 0 & 0 \\ 0 & 0 & 0 & \frac{4}{6} & 0 & \frac{2}{6} & 0 \\ 0 & 0 & 0 & 0 & \frac{5}{6} & 0 & \frac{1}{6} \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix} $$

Comenzamos con la certeza en el estado $i=0$ . Podemos codificar las probabilidades de cada estado en un punto determinado con un vector $v\in[0,1]^7$ y nuestro estado inicial corresponde a $v_0=(1,0,0,0,0,0,0)$ .

He aquí un hecho fundamental sobre las cadenas de Markov (que es fácil de ver y de demostrar por inducción): las probabilidades para el estado después de $k$ las transiciones vienen dadas por $v_k=(T')^kv_0$ . (Es decir $T$ transpuesto. También se puede trabajar con vectores de fila $v$ entonces no es necesario transponer, sino que " $v_0T^k$ "Hay que acostumbrarse un poco).

Por lo tanto, la probabilidad de que hayamos terminado en el estado de absorción $i=6$ después de $k$ pasos es precisamente la última entrada de ese vector, o $v_k[6]=((T')^kv_0)[6]$ . Por supuesto, podríamos haber estado ya en el estado de absorción después de $k-1$ pasos. Así que la probabilidad de que nuestra cadena de Markov termine en el estado de absorción por primera vez después de $k$ pasos es

$$ p_k := ((T')^kv_0)[6]-((T')^{k-1}v_0)[6]. $$

Podemos calcular numéricamente $p_k$ para un número suficientemente grande de $k\leq K$ tal que $\sum_{k=0}^Kp_k\approx 1$ e incluso puede haber una solución de forma cerrada. Entonces, dado $p_k$ podemos calcular la expectativa como

$$ \sum_{k=0}^\infty kp_k \approx \sum_{k=0}^K kp_k. $$

A continuación, supongamos que tenemos $n$ jugadores, y queremos saber después de cuántos pasos terminará el juego, es decir, cuando el primer jugador tenga todas sus cartas boca abajo. Podemos calcular fácilmente la probabilidad $q_k^n$ que al menos un jugador tenga todas las cartas boca abajo después de $k$ o menos pasos al observar que

$$ \begin{align*} q_k^n &= P(\text{at least one player has all cards face down after $k$ or fewer steps}) \\ &= 1-P(\text{all $n$ players need at least $k+1$ steps}) \\ &= 1-P(\text{ONE player needs at least $k+1$ steps})^n \\ &= 1-\bigg(\sum_{j=k+1}^\infty p_j\bigg)^n \\ &= 1-\bigg(1-\sum_{j=0}^k p_j\bigg)^n. \end{align*} $$

A partir de esto, podemos derivar la probabilidad $p^n_k$ que un juego de $n$ jugadores termina después de exactamente $k$ pasos:

$$ p^n_k = q_k^n-q_{k-1}^n = \bigg(1-\sum_{j=0}^{k-1} p_j\bigg)^n-\bigg(1-\sum_{j=0}^k p_j\bigg)^n. $$

Y a partir de esto, a su vez, podemos volver a calcular la duración esperada de un juego con $n$ jugadores:

$$ \sum_{k=0}^\infty kp^n_k \approx \sum_{k=0}^K kp^n_k. $$

---

Como escribí anteriormente, puede haber una solución de forma cerrada para el $p_k$ pero por ahora, podemos evaluarlos numéricamente usando R. Estoy usando $K=10,000$ para que $\sum_{k=0}^K p_k=1$ hasta la precisión de la máquina.

max_steps <- 10000
state_probabilities <- matrix(NA,nrow=max_steps+1,ncol=7,dimnames=list(0:max_steps,6:0))
state_probabilities[1,] <- c(1,0,0,0,0,0,0)
transition_matrix <- rbind(
    c(0,6,0,0,0,0,0),
    c(1,0,5,0,0,0,0),
    c(0,2,0,4,0,0,0),
    c(0,0,3,0,3,0,0),
    c(0,0,0,4,0,2,0),
    c(0,0,0,0,5,0,1),
    c(0,0,0,0,0,0,6))/6

for ( kk in 1:max_steps ) {
    state_probabilities[kk+1,] <- t(transition_matrix)%*%state_probabilities[kk,]
}

probs <- diff(state_probabilities[,7])
sum(probs)  # yields 1
sum(probs*seq_along(probs)) # yields 83.2

plot(probs[1:400],type="h",xlab="Number of steps",ylab="Probability",las=1)

A continuación, así es como obtenemos las probabilidades $p^4_k$ para $n=4$ jugadores:

n_players <- 4

probs_minimum <- sapply(1:max_steps,
    function(kk)(1-sum(probs[1:(kk-1)]))^n_players-(1-sum(probs[1:kk]))^n_players)
head(probs_minimum)
plot(probs_minimum[1:400],type="h",xlab="Number of steps",ylab="Probability",
    las=1,main=paste(n_players,"players"))

Por supuesto, cuatro personas terminan más rápido que una sola. Para $n=4$ obtenemos un valor esperado de

sum(probs_minimum*seq_along(probs_minimum))
[1] 25.44876

Por último, me gusta confirmar este tipo de cálculos mediante una simulación.

n_sims <- 1e5
steps_minimum <- rep(NA,n_sims)
pb <- winProgressBar(max=n_sims)
for ( ii in 1:n_sims ) {
    setWinProgressBar(pb,ii,paste(ii,"of",n_sims))
    set.seed(ii)    # for reproducibility
    states <- matrix(FALSE,nrow=6,ncol=n_players)
    n_steps <- 0
    while ( TRUE ) {
        n_steps <- n_steps+1
        for ( jj in 1:n_players ) {
            roll <- sample(1:6,1)
            states[roll,jj] <- !states[roll,jj]
        }
        if ( any ( colSums(states) == 6 ) ) {
            steps_minimum[ii] <- n_steps
            break
        }
    }
}
close(pb)

La distribución del número de pasos necesarios en nuestro $10^5$ juegos simulados coincide con el calculado $p^4_k$ bastante bien:

result <- structure(rep(0,length(probs_minimum)),.Names=seq_along(probs_minimum))
result[names(table(steps_minimum))] <- as.vector(table(steps_minimum))/n_sims
cbind(result,probs_minimum)[1:30,]
    result probs_minimum
1  0.00000    0.00000000
2  0.00000    0.00000000
3  0.00000    0.00000000
4  0.00000    0.00000000
5  0.00000    0.00000000
6  0.06063    0.06031414
7  0.00000    0.00000000
8  0.08072    0.07919228
9  0.00000    0.00000000
10 0.08037    0.08026479
11 0.00000    0.00000000
12 0.07382    0.07543464
13 0.00000    0.00000000
14 0.06826    0.06905406
15 0.00000    0.00000000
16 0.06409    0.06260212
17 0.00000    0.00000000
18 0.05668    0.05654555
19 0.00000    0.00000000
20 0.05180    0.05100393
21 0.00000    0.00000000
22 0.04570    0.04598101
23 0.00000    0.00000000
24 0.04078    0.04144437
25 0.00000    0.00000000
26 0.03749    0.03735245
27 0.00000    0.00000000
28 0.03241    0.03366354
29 0.00000    0.00000000
30 0.03026    0.03033861

Por último, la media de los pasos necesarios en los juegos simulados también coincide bastante bien con la expectativa calculada:

mean(steps_minimum)
[1] 25.43862

Answer 2

Creo que he encontrado la respuesta para el caso de un solo jugador:

Si escribimos $e_{i}$ para la duración restante esperada del juego si $i$ las cartas están boca abajo, entonces podemos resolverlo:

(i). $e_{5} = \frac{1}{6}(1) + \frac{5}{6}(e_{4} + 1)$

(ii). $e_{4} = \frac{2}{6}(e_{5} + 1) + \frac{4}{6}(e_{3} + 1)$

(iii). $e_{3} = \frac{3}{6}(e_{4} + 1) + \frac{3}{6}(e_{2} + 1)$

(iv). $e_{2} = \frac{4}{6}(e_{3} + 1) + \frac{2}{6}(e_{1} + 1)$

(v). $e_{1} = \frac{5}{6}(e_{2} + 1) + \frac{1}{6}(e_{0} + 1)$

(vi). $e_{0} = \frac{6}{6}(e_{1} + 1)$

(vi) y (v) nos dan entonces (vii). $e_{1} = e_{2} + \frac{7}{5}$ ;

(vii) y (iv) nos dan entonces (viii). $e_{2} = e_{3} + \frac{11}{5}$ ;

(viii) y (iii) nos dan entonces (ix). $e_{3} = e_{4} + \frac{21}{5}$ ;

(ix) y (ii) nos dan entonces (x). $e_{4} = e_{5} + \frac{57}{5}$ ;

(x) y (i) nos dan entonces $e_{5} = 63 $

Podemos entonces sumar para obtener $e_{0} = 63 + \frac{57}{5} + \frac{21}{5} + \frac{11}{5} + \frac{7}{5} + 1 = 83.2$ .

Ahora, ¿cómo se podría generalizar esto para encontrar la duración esperada del juego con $n$ ¿jugadores?