Après un dîner imaginaire, Nora prépare une liste d'étiquettes associées à des douceurs fictives. Camille les reçoit une à une et conserve seulement une candidate dans une case. Une nouvelle étiquette peut remplacer celle qu'elle gardait ; une étiquette écartée n'est plus disponible dans cette case. Nora ne demande pas la meilleure douceur. Elle souhaite que chaque position de la liste ait la même chance d'être retenue quand une fin extérieure est annoncée. Camille devra compter les arrivées sans supposer d'avance combien il y en aura.
HARIBO présente des confiseries.
Ferrero présente des produits sucrés.
Lindt & Sprüngli présente des chocolats.
Ces catégories seules ont été lues. Aucun produit ou procédé n'est adapté ; étiquettes, arrivées, poids et chances sont stipulés, sans consommation ni mélange réel examiné.
Chaque étiquette possède d'abord un identifiant distinct. Les choix aléatoires du modèle sont indépendants : à la ième arrivée, Camille tire uniformément un entier entre un et i. Elle garde la nouvelle étiquette si cet entier vaut un, et conserve son ancienne candidate sinon. Elle garde nécessairement la première. La règle est classique, appelée échantillonnage par réservoir ; nous ne revendiquons pas son invention. La case contient un identifiant, le compteur contient le nombre d'arrivées, et la fin initiale ne dépend pas de l'identifiant actuellement retenu.
Une moitié à chaque arrivée favorise la dernière
Camille essaie d'abord une règle plus simple : à chaque nouvelle étiquette, une chance sur deux de remplacer la candidate. La liste donnée comporte A, B puis C. Après B, A et B possèdent chacune une moitié. À l'arrivée de C, C reçoit directement une moitié ; A conserve seulement la moitié de son ancienne moitié, un quart, et B également un quart. Nora refuse cette distribution pour sa demande de trois positions équiprobables. Les deux décisions ont été symétriques entre garder et remplacer, mais elles n'ont pas traité les trois arrivées symétriquement.
Camille emploie donc le compteur. À l'arrivée de B, elle remplace A avec une chance sur deux. À celle de C, elle remplace la candidate avec une chance sur trois et la conserve avec deux chances sur trois. C reçoit un tiers ; A et B obtiennent chacune une moitié multipliée par deux tiers, soit un tiers. Nora retient cette règle pour les trois arrivées. Elle ne corrige pas le résultat de la règle précédente en donnant un autre titre aux quarts : elle change effectivement la chance de remplacement au troisième geste.
La justification se poursuit sans connaître la fin. Avant l'arrivée i, supposons que chaque ancienne position soit gardée avec une chance de un sur i moins un. Elle survit au geste courant avec une chance de i moins un sur i. Le produit vaut un sur i. La nouvelle position entre elle-même avec un sur i, par la décision du tirage. Toutes les positions possèdent donc la même chance après ce geste. La première position fournit le départ de la preuve, puisqu'elle est initialement seule et gardée. Camille applique ce même contrôle à chaque arrivée, sans recalculer une règle nouvelle seulement lorsque Nora annonce la longueur finale.
Cette propriété n'exige pas que Camille sache si une autre arrivée suivra. Si Nora clôt la liste après six étiquettes, chacune des six possède une chance sur six dans la case ; si elle la clôt après sept, chacune possède une chance sur sept. Camille n'a pas promis à la première une chance fixée à un sixième dès son arrivée. Sa chance se réduit lorsque de nouveaux noms deviennent candidats. La règle conserve une égalité sur le préfixe effectivement reçu, et non une proportion constante attribuée à un nom avant de connaître ses concurrents.
Nora reçoit comme réalisation les trois tirages de rangs un, deux et un pour les arrivées A, B, C. A entre d'abord, le deux à la deuxième arrivée la conserve, puis le un à la troisième la remplace par C. Cette réalisation finit donc sur C. La preuve des trois tiers ne dit pas que Camille aurait gardé un tiers de chacune des trois étiquettes. Elle garde un nom entier, et les chances comparent les différentes suites de tirages prévues par la règle. Nora conserve C comme résultat de cette réalisation, avec les entiers qui expliquent son entrée.
Tirer deux cases séparément ne garantit pas deux identifiants différents
Pour une autre remise, Nora veut exactement deux positions différentes si la liste contient au moins deux étiquettes. Camille propose deux cases qui exécuteraient chacune la première règle uniforme, avec leurs tirages indépendants. Sur A, B, C, chacune est uniforme. Pourtant les deux peuvent finir sur A, sur B ou sur C ensemble. La chance d'un doublon vaut trois fois un tiers au carré, soit un tiers. Nora refuse ce dispositif pour sa commande de deux identifiants distincts. Une bonne chance marginale dans chaque case ne suffit pas à contrôler leur couple.
Camille ne supprime pas seulement l'une des deux occurrences après le tirage : elle remettrait alors un seul identifiant dans les réalisations qui avaient donné un doublon. Sa commande exige deux positions. Elle choisit un réservoir commun de deux cases. A occupe la première, B la seconde. À l'arrivée i suivante, elle tire un entier entre un et i ; un remplace la première case, deux la seconde, les autres entiers ne remplacent rien. La même arrivée ne peut prendre les deux cases. Une étiquette nouvelle remplace donc exactement l'une des anciennes ou reste hors de la paire, ce qui conserve deux identifiants distincts.
Sur les trois arrivées A, B, C, les trois entiers du dernier geste donnent C avec B, A avec C, ou A avec B. Les trois paires non ordonnées possèdent chacune un tiers. Nora choisit une réalisation où le tirage vaut deux : les cases contiennent A et C. Elle peut ensuite présenter cette paire comme les positions un et trois retenues, sans inventer un deuxième passage de C dans la liste. Le choix ne revient pas à appliquer deux décisions indépendantes à C ; un seul entier détermine sa place éventuelle et l'ancien identifiant qui quitte la paire.
Nora teste une autre proposition sur quatre noms, A, B, C, D : choisir A avec B dans une moitié des cas, et C avec D dans l'autre. Chaque identifiant appartient à la paire avec une chance sur deux, le même nombre que dans une paire uniforme de deux parmi quatre. Pourtant A avec C, A avec D, B avec C et B avec D sont impossibles. Nora refuse donc d'attester l'uniformité des six paires depuis les quatre seules chances individuelles. Elle demande de vérifier la distribution des paires elles-mêmes, avec leur dépendance entre deux membres.
Toutes les paires doivent recevoir le même poids
Camille commence par une paire qui ne contient pas la nouvelle position i. Pour qu'elle soit gardée après le geste, il faut que cette paire exacte soit déjà présente et que le tirage n'atteigne aucune de ses deux cases. Si les anciennes paires étaient uniformes, la première chance vaut l'inverse du nombre de paires parmi i moins un ; la conservation vaut i moins deux sur i. Leur produit est l'inverse du nombre de paires parmi i. Camille ne donne pas une chance supplémentaire à une paire dont les noms seraient plus courts : seul le nombre d'anciennes positions et de cases entre dans ce calcul.
Elle examine ensuite une paire contenant la nouvelle position i et un ancien identifiant T. Avant le geste, T devait être gardé avec un autre ancien identifiant. Cet autre pouvait être n'importe lequel des i moins deux anciens noms différents de T. Pour chacun de ces couples, il existe exactement un entier du tirage qui remplace l'autre case et laisse T présent ; sa chance vaut un sur i. Les i moins deux possibilités contribuent donc ensemble le même produit que pour une paire sans i. Camille a couvert les deux familles de paires, celles qui contiennent le nouveau nom et celles qui ne le contiennent pas. Elles reçoivent toutes le même poids, et le départ A, B était l'unique paire possible après deux arrivées.
À quatre arrivées, cette preuve donne six paires, chacune avec un sixième. A avec B et C avec D ne sont plus seules à se partager tout le poids. Nora peut donc conserver le réservoir commun pour sa commande uniforme, plutôt que la proposition limitée à deux paires. Elle retient dans une réalisation B avec D, et garde les tirages qui y ont conduit. La règle ne lui demandait pas de fabriquer les six paires sur une même table ; elle lui demandait un procédé du modèle qui n'en écarte aucune et leur donne les mêmes chances.
Une paire uniforme ne fixe pas un ordre uniforme dans les cases
Sur A, B, C, les cases du réservoir commun donnent seulement A puis B, A puis C, ou C puis B. Chacun de ces trois arrangements possède un tiers. Les arrangements B puis A, C puis A et B puis C n'apparaissent pas. Nora avait pourtant demandé une nouvelle remise où les deux identifiants joueraient deux rôles différents, gauche et droite, et où les six arrangements devraient être équiprobables. Camille ne lui transmet donc pas les deux numéros de cases comme s'ils avaient déjà produit cet ordre uniforme. Les cases étaient un moyen de conserver une paire, pas un départage symétrique de ses rôles.
Camille ajoute une décision après la fin : une chance sur deux d'échanger les deux identifiants, indépendante de tous les tirages précédents. La paire A, C, de chance un tiers, donne ainsi A à gauche et C à droite avec un sixième, et C à gauche et A à droite avec un sixième. Les deux autres paires donnent de la même manière les quatre arrangements restants. Nora accepte cette remise ordonnée, puis conserve les rôles effectifs d'une réalisation où C est à gauche et A à droite. Le geste final n'a pas sélectionné deux nouveaux noms ; il a réparti les deux noms déjà retenus entre les rôles que la paire seule ne fixait pas.
La même identité arrivée deux fois n'est pas une nouvelle identité
Nora donne maintenant une liste A, B, A. Les trois positions restent des arrivées distinctes, même si deux étiquettes portent le même nom. La règle à une case leur attribue chacune un tiers. Le nom A apparaît donc finalement avec deux tiers, B avec un tiers. Camille garde cette conséquence si la commande porte sur les positions d'arrivée. Elle ne la présente pas comme un choix uniforme entre les deux noms différents. Leur nombre de passages dans la liste intervient précisément dans la probabilité du nom final.
Pour une commande sur les noms différents, Camille change l'information conservée. Elle tient un registre des identités déjà rencontrées et compte seulement leurs premières apparitions. Sur A, B, A, le second A est reconnu dans le registre et ne provoque ni augmentation de ce nouveau compteur ni tirage supplémentaire. A et B gardent chacune une moitié. Si C arrive ensuite, C est une troisième identité nouvelle et reçoit une chance sur trois ; les deux anciennes gardent chacune un tiers. Nora retient cette méthode pour sélectionner un nom différent, en acceptant que le registre conserve davantage de noms que la seule case de candidate.
Camille ne peut pas retrouver ce registre depuis la seule candidate présente. Après A puis B, la candidate peut être B et le compteur vaut deux. Après C puis B, la candidate peut également être B avec le même compteur. Si A arrive ensuite, c'est une répétition dans le premier historique et une identité nouvelle dans le second. L'état B, deux ne permet pas de savoir laquelle des deux corrections du compteur est requise. Nora conserve donc le registre dans la commande qui distingue les noms. Elle ne retire pas cet état supplémentaire du document tout en promettant les mêmes décisions de reconnaissance.
Ce manque d'information affecterait réellement les chances. Après les deux premières identités A, B, remplacer B par un A répété ajouterait une chance d'A à sa moitié déjà présente, sans possibilité inverse depuis la candidate A ; pour garder les deux moitiés, ce remplacement doit avoir une chance nulle. Après C, B puis un A nouveau, en revanche, B ne peut finir avec le tiers demandé qu'en survivant depuis sa moitié avec deux tiers, donc le remplacement de B par A doit avoir une chance d'un tiers. Le même état candidate B, compteur deux, arrivée A exigerait zéro dans un historique et un tiers dans l'autre. Sans registre, cette information perdue ne peut être réparée par le seul compteur.
Des poids annoncent une autre chance que l'égalité des positions
Une branche séparée conserve trois identifiants distincts A, B, C et leur donne des poids deux, un et trois. Nora veut une chance proportionnelle à ces poids, pas un tiers à chacun. Les poids sont des données de la feuille, sans préférence mesurée. Camille garde la première étiquette, puis à chaque arrivée compare son poids au total des poids reçus, nouvelle arrivée comprise. Elle remplace la candidate avec cette fraction. Elle conserve donc deux compteurs possibles dans ses dossiers : le nombre d'arrivées pour la règle uniforme, et le poids total pour la règle pondérée.
Après B, le poids total est trois et B remplace A avec une chance sur trois. A possède deux tiers, B un tiers. Après C, le total vaut six et C remplace la candidate avec trois sur six, une moitié. A conserve alors un tiers, B un sixième et C obtient une moitié. Nora accepte ces trois chances pour sa commande pondérée. Employer un sur trois au dernier geste aurait au contraire rendu C trop rare pour son poids trois ; garder la règle du seul nombre d'arrivées ne répond plus à la proportion demandée.
La conservation fonctionne pour tous les anciens poids positifs. Si un ancien nom de poids w possédait une chance w sur le total antérieur W, il survit avec W sur W plus le poids nouveau. Le produit devient w sur le total nouveau. La nouvelle étiquette reçoit directement son propre poids sur ce total. Camille a donc conservé la proportion sans connaître la somme finale. Elle garde les poids d'origine auprès des identifiants, afin que deux passages différents d'un même nom ne soient pas fusionnés automatiquement dans la règle destinée aux positions. Une commande pondérée sur les identités distinctes demanderait aussi la convention qui traite leurs répétitions.
Choisir la fin depuis la candidate change la distribution
Nora revient à une case uniforme avec les arrivées A, B, C. Elle ferme maintenant après B si la candidate est B ; si la candidate est A, elle reçoit C puis ferme. Camille ne peut plus citer sa preuve à longueur extérieure fixe pour annoncer une égalité des trois noms dans le résultat final. Après deux arrivées, B est présent avec une moitié et provoque directement l'arrêt. Dans l'autre moitié, A est encore présent et C entre avec un tiers. La distribution finale devient B avec une moitié, A avec un tiers et C avec un sixième. Nora conserve ces trois fractions et refuse de les appeler trois tiers.
Le conditionnement par longueur montre précisément le changement. Quand la liste s'arrête après deux, la candidate est toujours B, et non A ou B avec une moitié chacune. Quand elle s'arrête après trois, la branche avait nécessairement conservé A après B ; B y est absent. A finit avec deux tiers dans cette branche et C avec un tiers. La règle de remplacement n'a pas été modifiée. C'est la décision de fermer, prise depuis l'identifiant présent, qui a sélectionné certains historiques de tirage. Nora retire donc la mention d'une fin indépendante de la candidate sur cette nouvelle feuille.
Elle compare avec un autre choix de fin, annoncé indépendamment des tirages : une moitié des listes s'arrêtera après deux, l'autre après trois. Conditionnellement à chaque longueur, les positions reçues sont cette fois uniformes. Sur la totalité des listes, A et B obtiennent pourtant chacune cinq douzièmes : une moitié d'une moitié, plus une moitié d'un tiers. C obtient un sixième, puisqu'elle n'est reçue que dans la seconde moitié. Nora peut donc attester l'uniformité sur chaque liste effectivement terminée sans promettre une égalité globale entre trois identifiants dont l'un manque dans la moitié des listes. Elle joint la règle de fin à ses résultats, au lieu de comparer ces fractions à trois tiers sous une condition que la collection n'avait pas remplie.
Nora remet enfin les dossiers séparés : une case pour une position uniforme, deux cases pour une paire non ordonnée, un échange final pour deux rôles, un registre pour les noms différents et le total des poids pour les proportions choisies. Chaque réalisation garde ses arrivées et ses tirages. Le dernier nom n'est pas qualifié de meilleur, et les chances ne remplacent pas les identifiants retenus. La commande précise reste ce qui permet de décider quelle information conserver et quelle distribution attester au moment de la fin.