generación en línea de muestras uniformes

Question

Una fuente proporciona un flujo de artículos $ x_1, x_2, \ dots $. En cada paso $ n $ queremos salvar una muestra aleatoria $ S_n \ subseteq \ {(x_i, i) | 1 \ le i \ le n \} $ de tamaño $ k $, es decir, $ S_n $ debe ser una manera uniforme elegido muestra de todo $ \ tbinom {n} {k} $ posibles muestras que consta de los elementos vistos. Así que en cada paso $ n \ ge $ k tenemos que decidir si se debe agregar el siguiente elemento a $ S $ o no. Si es así también hay que decidir cuál de los elementos actuales de eliminar de $ S $.

Estado un algoritmo para el problema. Demostrar su corrección.

Answer 1

Debido a la naturaleza dudosa de la cuestión, que sólo proporcionan consejos.

¿Usted ha intentado lo obvio? Con probabilidad $ \ frac {1} {n} $, añadir el nuevo elemento a la muestra. Si se añade, elegir uno de los elementos ya en la muestra uniformemente al azar y deje caer. Sonidos justo, ¿no es así?

En una prueba, que tendrá que proceder inductivamente. En el paso, se asume que $ S_ {n-1} $ es de hecho una muestra uniforme. De esto y de la forma que elija si desea incluir $ x_n $ y qué elemento a la baja, usted tiene que conseguir que S_n $ $ es una muestra uniforme, también.

Trate si puede demostrar por encima de la idea correcta. Si no es así, averiguar dónde está el problema y solucionarlo. Ver esta respuesta a una pregunta similar para una aplicación detallada de esta técnica.

Answer 2

El mejor algoritmo para su problema es el reservorio de muestreo algoritmo. Leer este