Número esperado de ensayos para ver x valores únicos de N valores totales

Question

Soy nuevo en estos foros, así que por favor, perdonadme si mi pregunta está mal redactada/formulada. Supongamos que tengo una lista de N enteros únicos de los que estoy sacando, uno a la vez, con sustitución. Deje que x sea el número de enteros no repetidos que he sacado hasta ahora (o, dicho de otro modo, el número de ensayos hasta ahora cuyo resultado era distinto de todos los ensayos anteriores). Por último, dejemos que n sea la cantidad de enteros no repetidos que busco, n estando (obviamente) entre [0, N ]. ¿Cuántas pruebas se necesitan, por término medio, antes de que x=n ?

Por ejemplo, tomemos una baraja de cartas. Si saco con reemplazo, ¿cuántas pruebas tardaré en ver 26 cartas diferentes?

Answer 1

Bienvenido. Tu problema está planteado de forma muy sucinta y, de hecho, es una variación del famosísimo el problema del coleccionista de cupones (que es su problema para $x=n$ ). La página de la wikipedia a la que he enlazado esboza una solución, pero permítanme repetirla aquí para completarla.

Dejemos que $T_i$ sea el número de intentos para obtener el $i$ después del primer objeto $i-1$ ya se han obtenido. Entonces el número esperado de intentos para ver $x$ objetos es $$\operatorname{E}[T]=\operatorname E[T_1]+\cdots + \operatorname E[T_x]$$ Centrémonos ahora en cada $\operatorname E[T_i]$ . Supongamos que tiene un total de $n$ objetos, todos igualmente susceptibles de ser dibujados y que ya has visto $i-1$ de ellos. La probabilidad de que dibujes un objeto no visto anteriormente es el complemento de la probabilidad de dibujar un objeto que ya has visto. Por lo tanto, $$\Pr(\text{draw}\ i\text{th item})=1-\frac{i-1}{n}=\frac{n-i+1}{n}$$ El número esperado de sorteos es entonces el recíproco de esta probabilidad $$\operatorname E[T_i] = \frac{n}{n-i+1}$$ Su suma es entonces $$\operatorname{E}[T]=\sum_{i=1}^x\frac{n}{n-i+1}=n\left(H_n - H_{n-x}\right)$$ donde $H_i$ es el $i$ Número armónico (con $H_0 = 0$ ).

Para responder a su ejemplo, para un $52$ baraja de cartas, se esperaría que tomara $$\operatorname{E}[T_{26}] = 52\left(H_{52} - H_{26}\right) \approx 35.5$$ Así que alrededor de treinta y cinco y medio sorteos para ver la mitad de las cartas de una baraja.

Answer 2

Siguiendo con este la respuesta es $$ \sum_{k=0}^{x-1}\frac{N}{N-k}=N\sum_{k=N-x+1}^{N}\frac1k. $$

Answer 3

Pensemos en esto: La primera carta extraída no puede ser una repetición de ninguna carta anterior, ya que no hay cartas anteriores. Entonces, ¿cuál es la probabilidad de que la segunda carta repita la primera? ¿Cuál es la probabilidad de que la tercera carta repita la primera o la segunda? Sigue calculando hasta que veas un patrón y puedas obtener una fórmula para la probabilidad de que la $n$ Esta tarjeta repite cualquiera de las primeras $n-1$ tarjetas.

Hay algunos otros detalles que tratar; esto es sólo el punto de partida de mi mente en la búsqueda de una solución.