Comment choisir au hasard un message parmi un flux dont on ne connaît pas la longueur à l'avance ?

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

Pour un projet de NSI, je voulais afficher un message tiré au hasard parmi tous ceux postés sur un forum pendant une journée, sans savoir combien il y en aurait ni pouvoir tous les stocker. Cela semblait impossible : comment tirer uniformément sans connaître le nombre total ? J'ai découvert l'échantillonnage par réservoir, dont la preuve tient en un produit qui se simplifie.

L'enjeu et les notions du programme

Démontrer l'uniformité d'un algorithme par un produit de probabilités indépendantes qui se simplifie (produit télescopique).

Le plan de l'exposé en 9,5 min

1. 1. Introduction

   1 min

   Des éléments arrivent un par un et l'on ne peut en garder qu'un seul en mémoire. On veut, à la fin, avoir choisi chacun avec la même probabilité $\frac{1}{n}$1/n, sans connaître $n$n à l'avance. Problématique : est-ce possible ?

2. 2. NSI : l'algorithme

   2,5 min

   On garde le premier élément. À l'arrivée du $i$i-ème élément, on tire un nombre au hasard : avec la probabilité $\frac{1}{i}$1/i, on remplace l'élément gardé par le nouveau ; sinon, on garde l'ancien.

   L'algorithme n'a besoin que d'une case mémoire et d'un compteur. Il fonctionne en un seul passage, quelle que soit la longueur du flux, et peut s'arrêter à tout moment : à chaque instant, l'élément gardé est uniforme parmi ceux déjà vus.

3. 3. Mathématiques : un produit qui se simplifie

   4,5 min

   L'élément numéro $i$i est le choix final s'il est retenu à son arrivée (probabilité $\frac{1}{i}$1/i) puis n'est remplacé par aucun des suivants. Le $j$j-ème élément ne le remplace pas avec la probabilité $1-\frac{1}{j}=\frac{j-1}{j}$1-1/j=(j-1)/j. Les tirages étant indépendants :
   $P=\frac{1}{i}\times \frac{i}{i+1}\times \frac{i+1}{i+2}\times \cdots \times \frac{n-1}{n}$P=1/itimesi/(i+1)×(i+1)/(i+2)×…×(n-1)/n.

   Chaque numérateur se simplifie avec le dénominateur précédent : c'est un produit télescopique, qui vaut $\frac{1}{i}\times \frac{i}{n}=\frac{1}{n}$1/itimesi/n=1/n. Tous les éléments ont la même probabilité $\frac{1}{n}$1/n.

   Exemple avec $n=4$n=4 : élément 2 : $\frac{1}{2}\times \frac{2}{3}\times \frac{3}{4}=\frac{1}{4}$1/2×2/3×3/4=1/4 ; élément 4 : $\frac{1}{4}$1/4. On peut aussi le démontrer par récurrence sur $n$n : si chacun des $n-1$n-1 premiers est gardé avec la probabilité $\frac{1}{n-1}$1/(n-1), après le $n$n-ième chacun l'est avec $\frac{1}{n-1}\times \frac{n-1}{n}=\frac{1}{n}$1/(n-1)×(n-1)/n=1/n, et le dernier avec $\frac{1}{n}$1/n.

4. 4. Conclusion

   1,5 min

   On peut tirer uniformément dans un flux de longueur inconnue en gardant le $i$i-ème élément avec la probabilité $\frac{1}{i}$1/i : le produit télescopique donne $\frac{1}{n}$1/n pour chacun. Une case mémoire suffit. J'ouvre sur la version qui garde $k$k éléments à la fois, utilisée pour sonder les très grandes bases de données.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

Conclusion : la réponse à la question

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Les pièges qui coûtent des points

• Remplacer avec une probabilité 1/2 à chaque fois, ce qui favorise les derniers éléments.
• Oublier la probabilité d'être retenu à l'arrivée.
• Croire qu'il faut connaître n.

Revoir les notions

• Probabilités conditionnelles (Première spé maths) →
• Suites : récurrence et limites (Terminale spé maths) →

Autres questions : hasard et simulation

• Comment un ordinateur, machine parfaitement déterministe, peut-il produire du hasard ?
• Comment mélanger une liste pour que tous les ordres soient vraiment équiprobables ?
• Comment simuler un dé à six faces équitable avec une simple pièce de monnaie ?
• Peut-on obtenir un tirage parfaitement équitable avec une pièce truquée dont on ignore le biais ?

Toutes les questions maths-nsi →