¿Cuál es la probabilidad de una serie explícita de números enteros en una distribución aleatoria limitada?

Question

Digamos que recojo 40 números enteros perfectamente aleatorios entre 1 y 400. ¿Cuál es la probabilidad de que un número entero se repita seis veces consecutivas en un sorteo tan aleatorio?

Lo que estoy buscando es la posibilidad de secuencias como [372, 193, 42, 42, 42, 42, 42, 42, 274, 42, 7, ...] , [372, 193, 42, 42, 42, 42, 42, 42, 274, 242, 7, ...] o [372, 193, 42, 42, 42, 42, 42, 42, 42, 42, 42, ...] ya que todos ellos cumplen con lo que estoy buscando. Como un ejemplo contrario [372, 193, 42, 42, 42, 42, 42, 77, 274, 42, 7, ...] no satisface mis condiciones porque los seis 42 no se repiten consecutivamente.

El problema del cumpleaños da que es un 87% de posibilidades de que dos de los 40 sean el mismo número, pero no puedo pasar de eso a calcular la posibilidad de que un cierto número entero se repita n veces consecutivas en la colección aleatoria.

Answer 1

Puedes atacar esto con una cadena de Markov, con seis estados (el número de números consecutivos del último recorrido), y con un estado final absorbente. Así que la matriz estocástica está dada por

 N = 400
 P =  [ 1-1.0/N   1.0/N    0.0      0.0      0.0      0.0    ;
        1-1.0/N   0.0      1.0/N    0.0      0.0      0.0    ;
        1-1.0/N   0.0      0.0      1.0/N    0.0      0.0    ;
        1-1.0/N   0.0      0.0      0.0      1.0/N    0.0    ;
        1-1.0/N   0.0      0.0      0.0      0.0      1.0/N  ;
        0.0       0.0      0.0      0.0      0.0      1.0    ]

Y así la probabilidad deseada es

octave > ([1 0 0 0 0 0 ] * P^39 )(6)
ans = 3.4097e-012

Debido a que las probabilidades son tan bajas, la aproximación más ingenua (sólo calcula la probabilidad de que unas 6 carreras tengan números consecutivos: el límite superior en la respuesta de Yuval) es bastante precisa. Tal vez quieras intentarlo con otros números para obtener resultados más interesantes.

Añadido : Un enfoque asimtótico, para grandes valores de intentos $L$ y no tan bajas probabilidades: Piensa en las longitudes de las carreras como variables aleatorias. Aproximadlas por $m$ iid variables geométricas $x_i$ con $p=1-1/N$ y $m$ elegido de manera que $m E(x_i) = L$ y calcular la probabilidad de que todos $x_i < k$ (en la pregunta original $N=400$ , $L=40$ , $k=6$ ). Esta aproximación (salvo errores) da :

$$ \approx 1 - \left ( 1 - \frac {1}{N^{k-1}} \right )^{ \frac {N-1}{N} L }$$

Answer 2

Aquí está mi enfoque simplista para calcular la probabilidad.

Podemos ver esto como si tiráramos un dado con 400 caras 40 veces. Es 1/400 para sacar cualquier número. Da $1/(400^k)$ oportunidad de dibujar un cierto número $k$ veces. No estamos interesados en un cierto número, pero cualquiera de los 400 servirá y eso da $400/(400^k)$ .

Tenemos $40-6+1$ las oportunidades de tener una racha de $6$ números repetidos consecutivamente.

$$ (L-k+1)N/N^{k} $$

$N=400, L=40, k=6$

$$ (40-6+1)400/400^{6} \approx 3,418e{-12}$$

Pero como leonbloy y Yuval Ya he señalado $N/N^{k}$ es igual a $N^{1-k}$ y por lo tanto puede ser escrito como

$$ (L-k+1)N^{1-k} $$

$$ 35*400^{-5} \approx 3,418e{-12}$$

Es una pequeña posibilidad.

Answer 3

Puedes usar la inclusión-exclusión para poner límites a esto. Para $A \subset [40]$ de longitud $6$ que $S_A$ sea el caso de que todos los números en $A$ son iguales. La probabilidad $p$ que quieres está entonces limitado por $$ \sum_A \Pr [S_A] - \sum_ {A \neq B} \Pr [S_A \text { and } S_B] \leq p \leq \sum_A \Pr [S_A]. $$ Desde $ \Pr [S_A] = 400^{-5}$ es fácil calcular el límite superior: es $$ \binom {40}{6} 400^{-5} \approx 0.000000375.$$ Calcular el límite inferior es más complicado, así que te lo dejo a ti. Mi suposición es que estará bastante cerca del límite superior. Si no lo está, siempre puedes tomar más términos en la fórmula de inclusión-exclusión.