lanzando un $k$ -Dos caras hasta que consigas todas las caras el mismo número de veces

Question

Tiras una feria $k$ -dados de lado repetidamente y llevar la cuenta de todos los resultados. Te detienes si has visto todas las caras exactamente el mismo número de veces. ¿Cuál es el número esperado de veces que tienes que lanzar los dados? ¿Es ese número incluso finito?

Comience con el ejemplo más sencillo de un $2$ -dados de una cara, es decir, una moneda justa. Hay un 50% de posibilidades de que después de 2 tiradas tengas una cara y una cola, así que te paras. Hay un 12,5% de posibilidades de que después de 2 tiradas tengas 2:0 y continúes, pero después de 4 tiradas tengas 2:2, así que te paras. Se pueden calcular algunos términos más pero no veo un patrón suficiente para obtener una serie sumable.

No es demasiado difícil calcular la probabilidad de que tras $k\cdot m$ lanzamientos de un $k$ -Dados de cara, se obtienen todas las caras exactamente $m$ veces, pero estas probabilidades no son independientes para diferentes $m$ así que no estoy seguro de que eso sea útil.

La relación con los paseos aleatorios parece útil. Uno puede mapear los resultados de lanzar una moneda repetidamente a un trabajo aleatorio sobre los enteros. Ver el mismo número de caras y colas equivale a volver al punto de partida (en el cero). Este es un problema bien estudiado y se sabe que se vuelve a cero con probabilidad uno en un tiempo finito. El número que busco sería el tiempo esperado cuando se vuelve a cero por primera vez pero no he encontrado ningún resultado al respecto.

Para $k$ más grande que $2$ (e incluso) el mapeo a paseos aleatorios ya no es biyectivo. Si se mapea el resultado de un $6$ -a un paseo aleatorio por la $3$ -El retículo de números enteros con cada cara correspondiente a un paso en una de las 6 direcciones que un retorno al origen es necesario pero no suficiente para haber visto cada cara el mismo número de veces. Sin embargo, se sabe que para un paseo aleatorio sobre el entramado de enteros en dimensión de al menos $3$ la posibilidad de volver al origen en un tiempo finito es estrictamente menor que $1$ . Así que esto debería demostrar que para un dado con al menos $6$ caras, el número esperado de lanzamientos no es finito.

¿Es este un número finito para $k=2$ y $k$ entre $3$ y $5$ ? ¿Existen estimaciones al respecto?

Answer 1

Respuesta relativa a $k=2$ . Para $k\geq2$ ver edición.

Si $X_2$ denota el número de lanzamientos necesarios entonces $X_2$ sólo toma múltiplos positivos de $2$ como valor, y esto con: $$P(X_2=2n)=2^{1-2n}C_{n-1}=2^{1-2n}\frac{(2n-2)!}{n!(n-1)!}$$ para $n=1,2,\dots$ lo que lleva a..: $$\mathbb EX_2=\sum_{n=1}^{\infty}2^{2-2n}\binom{2n-2}{n-1}=\sum_{n=0}^{\infty}2^{-2n}\binom{2n}{n}$$

Aquí $C_n$ representa el $n$ -en Número catalán .

En este caso ( $k=2$ ) podemos hacerlo con una moneda justa.

Dejemos que $H_k$ representa el número de lanzamientos con cabezas de resultado y deja que $T_k$ para el número de lanzamientos con colas de resultados por $k$ tiros.

A continuación, eche un vistazo a la ruta determinada por $(k,H_k-T_k)$ para $k=0,1,\dots,2n$ con la condición de que $X_2=2n$ .

A partir de $(0,0)$ y terminando en $(2n,0)$ primer WLOG al que vamos $(1,1)$ .

Entonces, con probabilidad $2^{2-2n}C_{n-1}$ de ahí pasamos a $(2n-1,1)$ manteniendo una segunda coordenada positiva.

Y luego con probabilidad $2^{-1}$ vamos a $(2n,0)$ .

Tenemos la igualdad asintótica: $$2^{-2n}\binom{2n}{n}\sim\frac{1}{n^{\frac12}\sqrt\pi}$$ y concluir que: $$\mathbb EX_2=+\infty$$

---

editar (para completar la respuesta):

Si $k>2$ dejar $U$ denota el resultado en el primer lanzamiento y deja que $V$ sea (por ejemplo) el elemento más pequeño de $\left\{ 1,\dots,k\right\} $ con $U\neq V$ .

Ahora defina $Y$ como el número de lanzamientos necesarios (incluido el primero) para volver de nuevo en la situación que el resultado $U$ y el resultado $V$ han aparecido el mismo número de veces.

Comparación de $Y$ y $X_{2}$ encontramos fácilmente que $P\left(Y>n\right)\geq P\left(X_{2}>n\right)$ para cada entero no negativo $n$ y en consecuencia: $$\mathbb{E}Y=\sum_{n=0}^{\infty}P\left(Y>n\right)\geq\sum_{n=0}^{\infty}P\left(X_2>n\right)=\mathbb{E}X_{2}$$

Además, es evidente que $X_{k}\geq Y$ para que $\mathbb{E}X_{k}\geq\mathbb{E}Y$ .

Combinando esto con $\mathbb{E}X_{2}=+\infty$ concluimos que $\mathbb{E}X_{k}=+\infty$ para $k=2,3,\dots$

Answer 2

Toma un $2$ -sufrir un troquel de lado y dejar $N$ sea el número de tiradas necesarias para llegar desde una posición en la que los números de 1s y 2s difieren en $1$ hasta un punto en el que son iguales. Esto tiene la misma distribución que reducir una diferencia de $2$ a $1$ .

Supongamos que $\mathbb E(N)<\infty$ . Entonces tenemos $\mathbb E(N)=1+\frac12\times2\mathbb E(N)$ ya que después de la primera tirada con probabilidad $\frac12$ lo has conseguido y con probabilidad $\frac12$ tiene una diferencia de $2$ que hay que reducir dos veces. Pero esta ecuación no tiene solución finita, contradicción.

Se deduce que la expectativa es infinita para cualquier número de caras, ya que después de la primera tirada han salido dos caras diferentes números de veces, e incluso esperar hasta que esas dos sean iguales tiene una expectativa infinita.

Como usted dice, para seis o más lados hay una probabilidad positiva de no empatar nunca. Sospecho que seis no es el valor más pequeño para el que esto se cumple.

Answer 3

Lanzamiento del troquel $n$ veces, tenemos una palabra de longitud $n$ del alfabeto $\{1,\cdots,k\}$ .
Hay $k^n$ diferentes palabras que se pueden componer.

Cada palabra corresponde a un término de la expansión del multinomio $$ \left( {x_{\,1} + x_{\,2} + \cdots + x_{\,k} } \right)^n \quad \left| {\;x_{\,j} = j} \right. $$

Si tomamos un histograma del número de veces que aparece cada carácter, cada uno corresponderá a $$ x_{\,1} ^{\,j_{\,1} } x_{\,2} ^{\,j_{\,2} } \cdots x_{\,k} ^{\,j_{\,k} } \quad \left| {\;\sum\limits_l {j_{\,l} } = n} \right. $$ para que el número de palabras diferentes que tienen el mismo histograma de repetición $$ \left( {x_{\,1} + x_{\,2} + \cdots + x_{\,k} } \right)^n = \sum\limits_{j_{\,1} + j_{\,2} + \cdots + j_{\,k} = n} {\left( \matrix{ n \cr j_{\,1} ,j_{\,2} , \cdots ,j_{\,k} \cr} \right)x_{\,1} ^{\,j_{\,1} } x_{\,2} ^{\,j_{\,2} } \cdots x_{\,k} ^{\,j_{\,k} } } $$ corresponderá al coeficiente multinomial correspondiente.

Ahora, supongamos que se sigue tirando el dado hasta $n$ veces sin parar.
Se quiere saber la probabilidad de obtener que cada cara aparezca $t$ tiempos, lo que por supuesto significa que $n=tk$ .
El número de palabras que presentan un histograma plano será $$ \bbox[lightyellow] { N(t,k) = \left( \matrix{ t\,k \cr \underbrace {t,t, \cdots ,t}_k \cr} \right) = {{\left( {t\,k} \right)!} \over {\left( {t!} \right)^{\,k} }}\quad \Rightarrow \quad P(t,k) = {{\left( {t\,k} \right)!} \over {\left( {t!} \right)^{\,k} k^{\,t\,k} }} } \tag{1}$$ y el correspondiente probabilidad $P(t,k)$ es un "acumulado" ya que incluye la probabilidad de que haya tenido un número igual (menos de $t$ ) de las apariciones en los rollos anteriores.
Para $t=0$ tenemos $P(0,k)=1$ correspondiente a la palabra vacía.

Para proceder y encontrar la probabilidad solicitada, considere una palabra de longitud $tk$ que, además de en $n=tk$ , también logra un número $s<t$ de caras iguales en medio (y también podría incluir otras "igualdades" antes y/o después) $$ \left[ {\underbrace {x_{\,a} ,x_{\,b} , \cdots ,x_{\,c} }_{s\,k},\underbrace {x_{\,d} ,x_{\,e} , \cdots ,x_{\,f} }_{\left( {t - s} \right)\,k}} \right] $$ entonces la segunda parte puede considerarse como una palabra de "nuevo comienzo", y podemos poner $$ P(t,s,k) = P(s,k)P(t - s,k) $$

Para que el probabilidad solicitada es decir la probabilidad $p(t,k)$ de conseguir igual número de caras en $n=tk$ y no antes
será $$ \eqalign{ & P(0,k) = p(0,k) = 1 \cr & P(1,k) = p(1,k) = {{k!} \over {k^{\,k} }} \cr & P(2,k) = P(0,k)p(2,k) + P(1,k)p(1,k)\quad \Rightarrow \cr & \Rightarrow \quad p(2,k) = P(2,k) - P(1,k)^{\,2} = \left( {{{\left( {2\,k} \right)!} \over {\left( {2!} \right)^{\,k} }} - \left( {k!} \right)^{\,2} } \right){1 \over {k^{\,\,2\,k} }} \cr & \quad \quad \vdots \cr & P(t,k) = \sum\limits_{0\, \le \,s\, \le \,t - 1} {P(s,k)p(t - s,k)} \cr} $$ que es la relación recursiva $$ \bbox[lightyellow] { \left\{ \matrix{ p(0,k) = 1 \hfill \cr p(t,k) = {{\left( {t\,k} \right)!} \over {\left( {t!} \right)^{\,k} k^{\,t\,k} }} - \sum\limits_{1\, \le \,s\, \le \,t - 1} { {{\left( {s\,k} \right)!} \over {\left( {s!} \right)^{\,k} k^{\,s\,k} }}p(t - s,k)} \hfill \cr} \right. } \tag{2}$$

Ejemplo

Con $k=2$ y $t=0 \cdots 6$ la fórmula anterior da $$p(t,k)= 1, \frac{ 1}{2}, \frac{ 1}{8}, \frac{ 1}{16}, \frac{ 5}{128}, \frac{ 7}{256}, \frac{ 21}{1024}$$ que coincide con la fórmula dada en la respuesta aceptada.

Con $k=3$ en su lugar, y $t=0 \cdots 6$ obtenemos $$p(t,k)= 1, \frac{ 2}{9}, \frac{ 2}{27}, \frac{ 272}{6561}, \frac{ 1646}{59049}, \frac{ 3652}{177147}, \frac{ 231944}{14348907}$$

Ambos resultados han sido comprobado frente al cálculo directo para los valores más bajos de $t$ .