Este dilema se puede abordar de diferentes formas, pero te enseñamos la que en nuestra opinión es la solución más completa.
Buen problema! Gracias por publicar.
Lo primero que debe notar es que en cualquier estado del juego, si tiene $ a $ jugadores restantes, entonces la probabilidad de ceder $ b $ los jugadores de la siguiente ronda es independiente de la ronda en la que te encuentres. De ahí que podamos hablar de $ P (a, b) $, la probabilidad de pasar de $ a $ jugadores a $ b $ jugadores en una ronda.
Jugando una ronda con $ a> 1 $ jugadores, hay $ K ^ a $ posibles rollos. Para encontrar la cantidad de formas en que terminamos $ b geq 1 $ jugadores, primero notamos que hay $ a elija b $ formas de elegir cual $ b $ los jugadores continúan. Entonces, dejando $ k $ denotar el valor que estos $ b $ los jugadores ruedan, encontramos que hay $ (k-1) ^ ab $ formas para que los jugadores obtengan este resultado: el $ b $ los jugadores que continúan deben rodar todos $ k $, y los jugadores restantes deben rodar entre $ 1 $ y $ k-1 $. Por tanto, podemos escribir (con la convención $ 0 ^ 0 = 1 $)
$$ P (a, b) = frac a elige b Displaystyle sum_ k = 1 ^ K (k-1) ^ ab K ^ a $$
Una vez que tenga estas probabilidades, el juego en sí es una cadena de Markov. Tus estados son los números enteros de $ 1 $ a $ M $ que denota el número de jugadores restantes. En cualquier paso, la probabilidad de pasar del estado $ a $ a estado $ b $ con $ a ge b ge 1 $ y $ a ne 1 $ es exactamente $ P (a, b) $. El estado 1 es un estado absorbente y las transiciones al estado 1 con probabilidad 1. Todas las demás probabilidades de transición son 0. Entonces, su matriz de transición se ve así
$$ 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 matrix 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, dado que este es un estado absorbente, esta es la probabilidad de que el juego termine en la ronda $ n $o antes. Para obtener la probabilidad de terminar después de exactamente $ n $ rondas, debe restar la entrada en la esquina superior derecha de $ T ^ n-1 $ desde la entrada superior derecha de $ T ^ n $.
El objetivo de esta respuesta es presentar una solución de forma cerrada para el problema. Representa un mayor desarrollo de la idea descrita en la respuesta de Jeremy Dover. La parte difícil y probablemente aburrida de la prueba se dará en el apéndice.
Por conveniencia reescribimos el $ M veces M $ matriz dimensional $ T (M, K) $ presentado por Jeremy Dover como:
$$ T_ ij = frac 1 K ^ i binom ij sum_ k = 0 ^ K-1 k ^ ij. $$
En el sentido de estados de transición, el proceso comienza en $ T_ MM $ y termina en $ T_ M1 $.
Como la matriz $ T $ es triangular sus valores propios son trivialmente sus elementos diagonales $ lambda_m = T_ mm = frac 1 K ^ m-1, ; m = 1 puntos M. $ Como todos los valores propios son distintos, la matriz es aparentemente diagonalizable mediante una transformación de similitud:
$$ text diag ( lambda_1, lambda_2, dots, lambda_M) = X ^ – 1 TX. $$
Conociendo la matriz de transformación $ X $ los poderes de la matriz $ T $ se puede calcular 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 $ X $ y $ X ^ – 1 $ son bastante simples (ver Apéndice):
$$ X_ ij = (1- delta_ i, j-1) binom i j-1; quad X ^ – 1 _ ij = frac 1i binom ij b_ ij, $$
donde $ b_k $ son los números de Bernoulli ($ b_1 = – frac12 $).
Colocando 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 de que el juego termine en el $ n $-a ronda dice:
$$ 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 agregada:
Puede ser conveniente reescribir la expresión (2) como:
$$ T ^ n_ M1 (M, K) = cal B _M left ( frac1 K ^ n right), $$
donde la funcion $ 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_Mleft(frac1xright)-b_Mright], $$
con $ B_M (x) $ siendo el polinomio de Bernoulli.
Apéndice
Proposición 1. La siguiente identidad es válida para cualquier $ p, n in mathbb Z _ + $:
$$ sum limits_ k = 0 ^ p-1 binom p k sum limits_ j = 0 ^ n-1 j ^ k = n ^ p. tag * $$
Prueba:
$$ begin align & (j + 1) ^ p = sum limits_ k = 0 ^ p binom p k j ^ k \ implica & (j + 1 ) ^ p – j ^ p = sum limits_ k = 0 ^ p-1 binom p k j ^ k \ implica & sum limits_ j = 0 ^ n-1 left[(j+1)^p – j^pright] = sum limits_ j = 0 ^ n-1 sum limits_ k = 0 ^ p-1 binom p k j ^ k \ implica & n ^ p = sum limits_ k = 0 ^ p-1 binom p k sum limits_ j = 0 ^ n-1 j ^ k. end align $$
Introduciendo la notación $ S ^ (n) _ k = suma límites_ j = 0 ^ n-1 j ^ k $ el conjunto de las ecuaciones PS PS con el exponente de $ n $ variando desde $ 1 $ a $ p $
es equivalente a la ecuación matricial:array$$ 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 fin
derecho). $$ Denotando la matriz de coeficientes binomiales como$ X $
, se observa que su determinante es distinto de cero y la ecuación se puede invertir obteniendo:array$$ left ( begin array l S ^ (n) _ 0 \ S ^ (n) _ 1 \ S ^ (n) _ 2 \ vdots \ S ^ (n) _ p-1 finarray 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
derecho). $$
Comparando la expresión con la conocida:
$$ S ^ (n) _ p-1 = frac1p sum_ j = 0 ^ p-1 binom pj b_j n ^ pj = frac1p sum_ j ‘= 1 ^ p binom p j ‘ b_ p-j’ n ^ j ‘, tag ** $$
Se obtiene: Proposición 2. Los elementos de la matriz de $ X ^ – 1 $
son:
$$ X ^ – 1 _ ij = frac 1i binom ij b_ ij, $$ donde $ b_k equiv b ^ -_ k $ son los números de Bernoulli tomados con la convención$ b_1 = – frac12 $ . Observe que en la citada página de Wikipedia se da una fórmula similar a (**) para $ S ^ (n + 1) _ p $ en términos de $ b ^ + $
sin una mención directa de esto.
La proposición 2 también se puede probar directamente. Proposición 3. Las columnas de la matriz $ X $ son los vectores propios de la matriz$ T $
. Prueba. Actuando por matriz $ T $ sobre el$ m $ -a columna de la matriz$ X $
:
$$ v ^ (m) _ j = begin cases 0, & 1 le j
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 ^ ij \ & = frac 1 K ^ i binom i m-1 sum_ j = m ^ i binom i + 1-m ij sum_ k = 0 ^ K-1 k ^ ij \ & = frac 1 K ^ i binom i m-1 sum_ j ‘= 0 ^ im 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 $$
Si para ti ha sido de ayuda este artículo, sería de mucha ayuda si lo compartes con el resto entusiastas de la programación de esta forma nos ayudas a dar difusión a nuestro contenido.