¿Cuándo termina el juego?

Question

Una reciente pregunta ha inspirado a la siguiente.

$M$ personas ($M\ge2$) jugar el siguiente. En cada ronda cada persona admitida a la ronda de los rollos de una $K$caras de los dados ($K\ge2$), los lados están marcados con números de $1$ a $K$. Si una sola persona tiene el puntaje más alto, el juego termina. De lo contrario, la gente con la puntuación más alta son admitidos a la siguiente ronda y el juego continúa. ¿Cuál es la probabilidad de que el juego termina exactamente en $n$ rondas?

Answer 1

Limpio problema! Gracias por publicar.

La primera cosa a notar es que, en cualquier estado del juego, si usted tiene $a$ jugadores restantes, entonces la probabilidad de ceder a $b$ jugadores en la próxima ronda es independiente de la ronda. De ahí que podamos hablar de $P(a,b)$, la probabilidad de transición de $a$ a los jugadores a $b$ jugadores en una ronda.

Jugar una ronda con $a > 1$ a los jugadores, no $K^a$ posible rollos. Para hallar el número de maneras de acabar con $b \geq 1$ a los jugadores, lo primero que nota que hay $a \choose b$ maneras de escoger la $b$ jugadores continúan. Luego, dejando $k$ denotar el valor que estos $b$ jugadores rollo, nos encontramos con que no se $(k-1)^{a-b}$ formas para que los jugadores rollo este resultado: la $b$ continuar los jugadores deben rollo $k$, y el resto de jugadores deben rollo entre $1$ e $k-1$. Por lo tanto podemos escribir (con la convención de las $0^0 = 1$) $$P(a,b) = \frac{{a\choose b}\displaystyle\sum_{k=1}^K (k-1)^{a-b}}{K^a}$$

Una vez que usted tiene estas probabilidades, el juego en sí es una cadena de Markov. Sus estados son los enteros de $1$ a $M$ que indica el número de jugadores que quedan. En cualquier paso, la probabilidad de transición de estado $a$ estado $b$ con $a \ge b \ge 1$ e $a \ne 1$ es exactamente $P(a,b)$. Estado 1 es un estado de absorción, y las transiciones de estado 1 con probabilidad 1. Todas las demás probabilidades de transición son 0. Por lo que su matriz de transición se parece a $$T=\left(\begin{matrix}P(M,M) & P(M,M-1) & P(M,M-2) & \cdots & P(M,1)\\ 0 & P(M-1,M-1) & P(M-1,M-2) & \cdots & P(M-1,1)\\ &&\vdots\\0 & 0 & \cdots & P(2,2) & P(2,1)\\ 0 & 0 & \cdots & 0 & 1\end{de la matriz}\right)$$

La entrada en la esquina superior derecha de $T^n$ es la probabilidad de estar en el estado 1 (es decir, el juego ha terminado) después de $n$ rondas. Pero, puesto que este es un estado de absorción, esto es la probabilidad de que el juego termina en la ronda $n$ o antes. Para obtener la probabilidad de terminar después de exactamente $n$ rondas, deberá restar de la entrada en la esquina superior derecha de $T^{n-1}$ a partir de la parte superior derecha de la entrada de $T^n$.

Answer 2

El objetivo de esta respuesta es presentar una forma cerrada de solución para el problema. Representa un mayor desarrollo de la idea descrita en la respuesta de Jeremy Dover. El duro y probablemente aburrido parte de la prueba se dará en el apéndice.

Para la conveniencia podemos reescribir la $M\times M$ dimensiones de la matriz $T(M,K)$ introducido por Jeremy Dover como: $$ T_{ij}=\frac 1{K^i}\binom ij\sum_{k=0}^{K-1}k^{i-j}. $$ En el sentido de estados de transición el proceso se inicia a $T_{MM}$ y termina a las $T_{M1}$.

Como la matriz $T$ es triangular, sus autovalores son trivialmente los elementos de su diagonal $\lambda_m=T_{mm}=\frac{1}{K^{m-1}},\; m=1\dots M.$ Como todos los autovalores son distintos a los de la matriz es apparantly diagonalizable por semejanza de transformación: $$ \text{diag}(\lambda_1,\lambda_2,\dots,\lambda_M)=X^{-1}TX. $$ Conocer la transformación de la matriz $X$ a los poderes de la matriz $T$ puede ser calculada como: $$ T^n=X\text{diag}(\lambda_1^n,\lambda_2^n,\dots,\lambda_M^n)X^{-1}.\tag1 $$

Afortunadamente, las estructuras de las matrices de $X$ e $X^{-1}$ es bastante simple (véase el Apéndice): $$ X_{ij}=(1-\delta_{i,j-1})\binom i{j-1};\quad X^{-1}_{ij}=\frac 1i\binom ij b_{i-j}, $$ donde $b_k$ son los números de Bernoulli ($b_1=-\frac12$).

El taponamiento de los valores en (1) se obtiene: $$ T^n_{M1}(M,K)=\sum_{m=1}^M X_{Mm}\lambda_m^n X^{-1}_{m1} =\sum_{m=1}^M\binom M{m-1}\frac{b_{m-1}}{K^{(m-1)n}} =\sum_{m=0}^{M-1}\binom M{m}\frac{b_{m}}{K^{nm}}.\tag2 $$

Finalmente, la probabilidad para que el juego final en la $n$-th ronda lee: $$ \boxed{P_n(M,K)=T^n_{M1}-T^{n-1}_{M1}=\sum_{m=0}^{M-1}\binom M{m}\frac{1-K^m}{K^{nm}}b_{m}.} $$

---

Nota añadida:

Puede ser conveniente volver a escribir la expresión (2) como: $$ T^n_{M1}(M,K)={\cal B}_M\left(\frac1{K^n}\right), $$ en función de las ${\cal B}_M(x)$ se define como: $$ {\cal B}_M(x)=\sum_{m=0}^{M-1}\binom M{m}b_{m}x^m\equiv x^M\left[B_M\left(\frac1x\right)-b_M\right], $$ con $B_M(x)$ siendo el polinomio de Bernoulli.

---

Apéndice

Proposición 1. La siguiente identidad se cumple para cualesquiera $p,n\in\mathbb Z_+$: $$ \sum\limits_{k=0}^{p-1} {\binom {p} k} \sum\limits_{j=0}^{n-1} j^k=n^p.\la etiqueta{*} $$

Prueba: $$\begin {align} &(j+1)^{p}=\sum\limits_{k=0}^{p} {\binom {p} k} j^k\\ \implies& (j+1)^{p} - j^{p} =\sum\limits_{k=0}^{p-1} {\binom {p} k} j^k\\ \implies&\sum\limits_{j=0}^{n-1} \left[(j+1)^{p} - j^{p}\right] = \sum\limits_{j=0}^{n-1} \sum\limits_{k=0}^{p-1} {\binom {p} k} j^k\\ \implies& n^{p}= \sum\limits_{k=0}^{p-1} {\binom {p} k} \sum\limits_{j=0}^{n-1} j^k. \end {align} $$ La introducción de la notación $S^{(n)}_k= \sum\limits_{j=0}^{n-1} j^k$ el conjunto de las ecuaciones $(*)$ con el exponente de $n$ variación de $1$ a $p$ es equivalente a la ecuación de matriz: $$ \left(\begin{array}l n\vphantom{\binom00}\\ n^2\vphantom{\binom00}\\ n^3\vphantom{\binom00}\\ \vdots\\ n^p\vphantom{\binom00} \end{array}\right)= \begin{pmatrix} \binom10&0&0&\cdots& 0\\ \binom20&\binom21&0&\cdots& 0\\ \binom30&\binom31&\binom32&\cdots& 0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ \binom p0&\binom p1&\binom p2&\cdots& \binom p{p-1}\\ \end{pmatrix} \left(\begin{array}l S^{(n)}_0\\ S^{(n)}_1\\ S^{(n)}_2\\ \vdots\\ S^{(n)}_{p-1} \end{array}\right). $$

Denota la matriz de los coeficientes binomiales como $X$, se observa que su determinante es distinto de cero y la ecuación puede ser invertida la obtención de: $$ \left(\begin{array}l S^{(n)}_0\\ S^{(n)}_1\\ S^{(n)}_2\\ \vdots\\ S^{(n)}_{p-1} \end{array}\right)= \begin{pmatrix} X^{-1}_{11}&0&0&\cdots& 0\\ X^{-1}_{21}&X^{-1}_{22}&0&\cdots& 0\\ X^{-1}_{31}&X^{-1}_{32}&X^{-1}_{33}&\cdots& 0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ X^{-1}_{p1}&X^{-1}_{p2}&X^{-1}_{p3}&\cdots& X^{-1}_{pp}\\ \end{pmatrix} \left(\begin{array}l n\vphantom{\binom00}\\ n^2\vphantom{\binom00}\\ n^3\vphantom{\binom00}\\ \vdots\\ n^p\vphantom{\binom00} \end{array}\right). $$

La comparación de la expresión con la bien conocida: $$ S^{(n)}_{p-1}=\frac1p\sum_{j=0}^{p-1}\binom pj b_j n^{p-j}= \frac1p\sum_{j=1}^{p}\binom p{j'} b_{p-j'} n^{j'},\etiqueta{**} $$ se obtiene:

Proposición 2. Los elementos de la matriz de $X^{-1}$son: $$ X^{-1}_{ij}=\frac 1i\binom ij b_{i-j}, $$ donde $b_k\equiv b^-_k$ son los números de Bernoulli toma con la convención de las $b_1=-\frac12$. Observar que en la antes citada página de la Wikipedia, la fórmula similar a (**) se da por $S^{(n+1)}_p$ en términos de $b^+$ sin una mención directa de este.

Proposición 2 puede ser demostrado también directamente.

Proposición 3. Las columnas de la matriz $X$ son los vectores propios de la matriz $T$.

Prueba. Actuando por la matriz $T$ sobre el $m$-ésima columna de la matriz $X$: $$ v^{(m)}_j=\begin{cases} 0,& 1\le j<m;\\ \binom{j}{m-1},& m\le j\le M. \end{casos} $$ se obtiene: $$\begin{align} \sum_{j=1}^M T_{ij} v^{(m)}_j &=\sum_{j=m}^M\frac 1{K^i}\binom ij\binom{j}{m-1}\sum_{k=0}^{K-1}k^{i-j}\\ &=\frac 1{K^i}\binom i{m-1}\sum_{j=m}^i\binom{i+1-m}{i-j}\sum_{k=0}^{K-1}k^{i-j}\\ &=\frac 1{K^i}\binom i{m-1}\sum_{j'=0}^{i-m}\binom{i+1-m}{j'}\sum_{k=0}^{K-1}k^{j'}\\ &\stackrel{(*)}=\frac 1{K^i}\binom i{m-1}K^{i+1-m}\\ &=\frac 1{K^{m-1}}\binom i{m-1}=\lambda_m v^{(m)}_i. \end{align} $$