Démontrant cette probabilité pour chaque résultat possible est uniforme à la fin d'un algorithme

Question

J'ai la mémoire de $ K $ éléments que vous pouvez imaginer être représenté par un tableau. Un par un, le tableau reçoit une valeur correspondant à l'indice de temps, par exemple à $ t= 1 $ la valeur sera $ 1 $ . À un moment donné ( $ T= K + 1 $ ) Le tableau sera plein et nous devons choisir une valeur à l'intérieur de la matrice à remplacer par le nouveau. L'objectif est de trouver un algorithme qui génère un sous-ensemble uniforme de $ K $ éléments. Par exemple, avec $ k= 2 $ et $ t= 3 $ il sortira avec une probabilité uniforme une des suivants: $ \ {1,2 \ \} $ , $ \ {1,3 \ \} $ ou $ \ {2,3 \} $ . Un algorithme possible est le suivant:

1. Créer une matrice de $ K $ éléments
2. pour $ t= 1 ,. \ ldots, t $ :
3. Si la matrice n'est pas complète Insérer un espace vide
4. recevoir une entrée
5. Jeter l'entrée avec probabilité 1 $ - k / t $
6. sinon insère l'entrée à un emplacement uniforme
7. fin pour
8. Retour Array

Il est facile de mettre en œuvre un tel programme et de vous convaincre que c'est une solution pour le problème, mais comment puis-je le démontrer? Essentiellement, j'ai besoin de démontrer que chaque sous-ensemble a une probabilité 1 $ / \ binom tk $ est le résultat à la fin (c'est parce que $ \ binom tk $ est le nombre de sous-ensembles possibles de $ k $ éléments à l'heure $ t $ < / span>).

Answer 1

La preuve est par induction. Le cas de base $ t= k $ est clair. Supposons que la revendication soit vraie à un moment donné $ t $ . Nous le prouverons pour le temps $ t + 1 $ .

laissez le premier $ t + 1 $ éléments be $ x_1, \ ldots, x_ {t + 1} $ . Par l'hypothèse d'induction, à l'heure $ t $ chacun de la $ \ binom {t} {k} $ possible $ k $ -Subsets de $ x_1, \ ldots, x_t $ se trouve dans le tableau avec probabilité égale. La probabilité que à l'étape $ t + 1 $ Le tableau reste la même est la même chose est $ 1-k / (t + 1) $ , d'où chacun des $ k $ -Subsets de $ x_1, \ ldots, x_t $ apparaît au temps $ t + 1 $ avec probabilité $$ \ frac {t + 1-k} {t + 1} \ frac {1} {\ binom {t} {k}}=frac {1} {\ binom {t + 1} {k}}. $$ Maintenant, considérons une partie k $ k $ -subset $ s $ de $ x_1, \ ldots, x_ {t + 1} $ contenant $ x_ {t + 1} $ . Pour que cet ensemble soit apparue à l'heure $ t + 1 $ , les deux événements suivants doivent se produire: au temps $ $ , le tableau consistait en $ s \ seminus \ {x_ {t + 1} \} $ avec l'une des $ t- (k-1) $ éléments restants; et au temps $ t + 1 $ , cet élément a été remplacé par $ x_ {t + 1} $ . Au total, la probabilité est $$ \ frac {k} {t + 1} \ cdot \ frac {1} {k} \ cdot \ frac {t-k + 1} {\ binom {t} {k}}=frac {1} {\ binom {t + 1} {k}}. $$