génération en ligne d'échantillons uniformes

Question

Une source fournit un flux d'articles, $ x 1 x 2, \ points $. A chaque $ étape n $ nous voulons sauver un échantillon aléatoire $ S_n \ subseteq \ {(x_i, i) | 1 \ le i \ le n \} $ de taille $ k $, soit $ S_n $ devrait être un uniforme choisi échantillon de tous $ \ tbinom {n} {k} $ échantillons possibles composé d'éléments vus. Donc, à chaque étape $ n \ ge k $ il faut décider d'ajouter l'article suivant à $ S $ ou non. Dans ce cas, nous devons aussi décider des éléments actuels à supprimer de $ S $.

Etat un algorithme pour le problème. Prouver son exactitude.

Answer 1

En raison de la nature douteuse de la question, je ne fournissent que des notes.

Avez-vous essayé l'évidence? Avec une probabilité $ \ frac {1} {n} $, ajoutez le nouvel élément à l'échantillon. S'il est ajouté, choisissez l'un des éléments déjà dans l'échantillon uniformément au hasard et déposez-le. Sons sur le juste, ne ce pas?

Pour preuve, vous devrez procéder inductivement. Dans l'étape, on suppose que $ S_ {n-1} $ est en effet un échantillon uniforme. De cela et la façon dont vous choisissez d'inclure $ x_n $ et qui élément à tomber, vous devez obtenir que $ S_n $ est un échantillon uniforme, aussi.

Essayez si vous pouvez prouver au-dessus idée correcte. Dans le cas contraire, savoir où le problème et le corriger. Voir cette réponse à une question similaire pour une application détaillée de cette technique.

Answer 2

Le meilleur algorithme pour votre problème est Réservoir d'échantillonnage algorithme. Lire cette