Simular un muestreo aleatorio con reemplazo

Question

¿Alguna idea sobre cómo abordar este problema?

(Debido a Karp) Considere un contenedor que contiene d bolas elegidas al azar (sin reemplazo) de una colección de n bolas distintas. Sin poder ver o contar las bolas en el contenedor, nos gustaría simular un muestreo aleatorio con reemplazo del conjunto original de n bolas. Nuestro único acceso a las bolas es que podemos hacer un muestreo sin reemplazo del contenedor.

Considere la siguiente estrategia. Supongamos que hasta ahora se han extraído k < d bolas del cajón. Se lanza una moneda con una probabilidad de que aparezca HEAD de k / n. Si aparece HEAD, se elige una de las k bolas extraídas anteriormente de forma uniforme y aleatoria; en caso contrario, se extrae una bola al azar del cubo. Demuestre que cada elección está distribuida de forma independiente y uniforme sobre el espacio de las n bolas originales. ¿Cuántas veces podemos repetir el muestreo?

Answer 1

Inicialmente hay $k$ ver las bolas que se han sacado de la papelera, $d-k$ bolas que no se ven en la papelera, y $n-d$ bolas invisibles que nunca llegaron a la papelera.

Hay una probabilidad $\frac{k}{n}$ de sacar de la $k$ bolas vistas y todas son igualmente probables por lo que la probabilidad de cada una es $\frac{1}{k}\times \frac{k}{n}=\frac{1}{n}$ . También hay una probabilidad $\frac{n-k}{n}$ de elegir uno de los $d-k+n-d = n-k$ bolas no vistas haciendo que la probabilidad de escoger una bola no vista en particular también $\frac{1}{n}$ . Así, cada bola tiene la misma probabilidad de ser extraída, independientemente de si ya ha sido vista o no.

Una vez que se extrae una bola no vista, se convierte en vista, aumentando el número de bolas vistas y reduciendo el número de bolas no vistas en la papelera. Así que este proceso puede continuar durante al menos $d-k$ sorteos. Después de eso, hay una probabilidad positiva de que no queden bolas sin ver en la papelera, por lo que el proceso y el análisis anterior pueden fallar.