Cadena de Variables Aleatorias, calculando $E[T]$ donde T es el más pequeño $\mathbb{N}$ s.t. Todos los números $1$ A través de $n$ Han mostrado hasta el momento $T$

Question

Estoy tratando de resolver lo siguiente:

Consideremos una cadena de variables aleatorias independientes que toman valor en el conjunto $\{1,\dots, n\}$ con igual probabilidad. Sea $T$ sea el menor número entero positivo para que todos los números $1$ a través de $n$ han aparecido en la cadena hasta el momento $T$ . Calcule el valor esperado $E[T]$ y describir cómo crece como $n\rightarrow \infty$ . Sea $S$ sea el menor número entero positivo para que al menos un número haya aparecido dos veces en la cadena hasta el momento $S$ . Calcula $E[S]$ y describir cómo crece como $n\rightarrow \infty$ .

Dado que queremos calcular los valores esperados de $T$ y $S$ deben ser variables aleatorias. Pero, ¿cómo puedo definir $T$ y $S$ Además, ¿cómo puedo relacionar $T$ y $S$ a la $X's$ ? Se agradece cualquier ayuda.

Answer 1

Esta respuesta es en realidad una pista extendida ya que, como señala BGM en los comentarios, el primer problema es el bastante conocido "problema del coleccionista de cupones", por lo que debería ser fácil encontrar una solución buscando.

Sugerencia para $T$ : Intenta definir la variable aleatoria $T_i$ para ser el momento de ver el $i$ -ésima cifra distinta en $\{1,\dots,n\}$ después de ver el $i-1$ -ésimo número distinto. (en el lenguaje del problema del recolector de cupones, el tiempo para recolectar el $i$ -el cupón después de cobrar $i-1$ de ellos). $T_i$ tiene una distribución geométrica y deberías ser capaz de calcular su parámetro y por tanto $\mathbb{E}[T_i]$ . Entonces $T = T_1 + \dots + T_n$ por lo que aplicando la linealidad de la expectativa se obtiene $\mathbb{E}[T]$ .

Sugerencia para $S$ : $S$ resulta ser en algunos sentidos una variable aleatoria más simple que $T$ y puedes escribir fácilmente una fórmula para la expectativa. Recordemos $\mathbb{E}[S] = \sum_{k=0}^n \mathbb{P}(S > k)$ y luego anotar $\mathbb{P}(S \gt k) = \frac{n!}{(n-k)! n^k}$ .