Nora prépare cinq cartes fictives pour une activité après dîner. Les cartes portent zéro, un, deux, trois et quatre, et doivent recevoir exactement la même chance d'être remises à Camille. Les seules décisions aléatoires disponibles sont des bits zéro ou un. Nous stipulons d'abord des bits indépendants, chacun avec une moitié. Aucun lancer de pièce réel n'est observé ; leur équité appartient au modèle. Camille souhaite compter les bits utilisés, en distinguant une bonne moyenne d'une promesse de finir avant un nombre fixé.
Rhicreative présente des cartes de vœux.
Ugmonk présente des cartes papier.
Peter Pauper Press présente des cartes de correspondance.
Ces catégories situent les cartes ; aucun dessin, produit ou procédé n'est adapté. Les bits, rôles et chances sont stipulés, sans tirage physique examiné.
Un bloc de trois bits donne huit valeurs, de zéro à sept, avec chances égales. Nora peut donc lire ces bits comme l'écriture binaire d'un nombre. Réduire ce nombre modulo cinq donnerait toujours une carte, mais ne la donnerait pas toujours avec un cinquième. Nous comparons ce raccourci à deux constructions classiques, rejet complet et recyclage d'une plage résiduelle, sans revendiquer leur invention. La carte remise doit porter un seul des cinq numéros, et le protocole peut déclarer qu'il attend encore des bits.
Une réduction modulo cinq favorise trois cartes
Camille associe zéro et cinq à la carte zéro, un et six à un, deux et sept à deux, puis trois à trois et quatre à quatre. Les trois premières cartes reçoivent chacune deux huitièmes, les deux dernières seulement un huitième. Nora retire cette proposition de la commande uniforme, même si aucune réalisation ne donne un numéro interdit. Le problème ne porte pas sur la possibilité de lire une carte, mais sur le nombre de blocs binaires qui lui sont attribués. Renommer les trois restes répétés ne permettrait pas de répartir huit blocs également entre cinq cartes.
Nora conserve alors seulement les valeurs de zéro à quatre. Si elle reçoit cinq, six ou sept, elle jette le bloc entier et demande trois nouveaux bits indépendants. Dans chaque tentative, chacune des cinq cartes possède un huitième, le refus trois huitièmes. Une carte peut être obtenue dès la première tentative, après un refus, après deux refus, ou plus tard. Pour chaque carte, la somme de ces chances vaut un huitième multiplié par un plus trois huitièmes plus le carré de trois huitièmes et ainsi de suite, soit un cinquième. Camille accepte donc l'uniformité du rejet complet.
Chaque tentative utilise trois bits et réussit avec cinq huitièmes. Le nombre moyen de tentatives vaut huit cinquièmes ; la consommation moyenne est vingt-quatre cinquièmes de bits, quatre virgule huit. Nora conserve cependant le refus comme une issue réelle de chaque tentative. La suite de blocs sept, sept puis deux utiliserait neuf bits et remettrait deux. Deux blocs sept ne rendent pas le troisième moins susceptible d'être refusé, puisque nous stipulons de nouveaux bits indépendants. La moyenne ne transforme pas cette procédure en un tirage terminé après au plus cinq bits.
Les trois valeurs refusées conservent une décision à trois issues
Au lieu de jeter cinq, six et sept, Camille soustrait cinq et conserve respectivement zéro, un ou deux, avec une chance conditionnelle d'un tiers. Elle garde ainsi une valeur c dans une plage de taille v égale à trois. Le bit suivant transforme c en deux c plus le bit, et v en deux v. Les six valeurs de zéro à cinq sont maintenant équiprobables, conditionnellement au refus initial. Zéro à quatre peuvent remettre leur carte ; cinq est de nouveau refusé. Nora a utilisé le choix entre les trois anciennes valeurs au lieu de refaire tout le tirage depuis zéro.
La réalisation un, zéro, un donne cinq au premier bloc, donc c zéro dans la plage trois. Le bit suivant un donne c un dans la plage six, et Camille remet la carte un après quatre bits. Si elle avait jeté le premier bloc, ce bit seul aurait commencé une autre tentative sans encore permettre de remettre une carte. Nora conserve l'état zéro, trois et sa transformation en un, six pour justifier la remise. La nouvelle carte n'est pas choisie en divisant la valeur cinq par une autre constante ; elle provient du rang résiduel et d'un bit réellement supplémentaire.
Le seul échec au quatrième bit vient de la première valeur sept suivie d'un. Le rang résiduel était deux, puis devient cinq. Camille soustrait cinq à c et à v : elle retrouve c zéro, v un, l'état de départ. La suite un, un, un, un ne remet donc aucune carte et revient à cet état après quatre bits. Avec les trois bits suivants zéro, zéro, zéro, la carte zéro est remise au septième bit. Nora maintient ce retour exact au départ seulement dans cette branche. Les deux autres valeurs initialement refusées peuvent terminer au quatrième bit et ne doivent pas être transformées en redémarrages inutiles.
La plage et son rang doivent être corrigés ensemble
Camille formalise la règle avec deux nombres : v, la taille de la plage encore disponible, et c, un rang entier entre zéro et v moins un. Elle commence avec v un et c zéro. À chaque bit, elle double v et remplace c par deux c plus ce bit. Tant que v reste inférieur à cinq, elle attend. Dès que v atteint au moins cinq, elle remet c si c est inférieur à cinq ; sinon, elle soustrait cinq à c et à v, puis continue. Dans cette construction pour cinq cartes, la plage reste inférieure à cinq après un refus, donc un nouveau bit suffit pour décider si un autre test est nécessaire.
La propriété utile est conditionnelle : parmi les préparations qui attendent encore dans une même plage v, c est uniforme sur ses v rangs. Un bit équilibré et indépendant donne chaque nouveau rang de la plage deux v avec la même chance. Le test c inférieur à cinq attribue un rang à chacune des cinq cartes. Dans la branche refusée, les autres rangs restent équiprobables, et soustraire cinq à chacun les transforme en zéro jusqu'à deux v moins six. Nora conserve leur taille deux v moins cinq. Cette propriété permet la continuation sans supposer que tous les préfixes ont déjà utilisé le même nombre de bits.
Camille avait essayé de soustraire cinq au rang refusé tout en laissant la plage à six. Après le refus du quatrième bit, elle aurait eu c zéro, v six, bien que c fût alors toujours zéro et non uniforme sur six possibilités. Le bit suivant aurait produit seulement zéro ou un ; d'autres rangs annoncés dans la plage n'auraient jamais été possibles. Nora retire cet état. Elle soustrait cinq à v autant qu'à c, obtient une plage un et retrouve la bonne propriété d'un rang uniforme sur cette seule possibilité. Le nombre de possibilités conservées fournit une information effective, pas une étiquette que l'on peut laisser inchangée après en avoir éliminé cinq.
Les deux profondeurs de sortie donnent la même chance à chaque carte
Dans un cycle partant de zéro, un, chaque carte possède une sortie à trois bits, de chance un huitième. Elle possède aussi une sortie à quatre bits : pour les six prolongements des valeurs initialement refusées, cinq sont attribués aux cartes. Chacune de ces cinq suites possède un seizième. La carte zéro correspond au bloc cinq puis zéro ; un au bloc cinq puis un ; deux au bloc six puis zéro ; trois au bloc six puis un ; quatre au bloc sept puis zéro. La dernière suite, bloc sept puis un, redémarre. Chaque carte obtient donc trois seizièmes par cycle, et le retour au départ un seizième.
En répétant les cycles seulement dans cette dernière branche, chaque carte obtient trois seizièmes multiplié par un plus un seizième plus son carré et ainsi de suite, exactement un cinquième. Les sorties de longueurs trois et quatre n'ont pas la même chance individuelle, mais leur somme est identique pour les cinq cartes. Camille avait attribué la même chance à chaque feuille terminale parce qu'elle portait un numéro ; elle retire cette affirmation. La longueur du chemin détermine le poids d'une feuille binaire, et c'est le regroupement de ces poids par carte qui établit l'uniformité.
Le coût moyen d'un cycle, redémarrage compris, vaut trois bits dans les cinq huitièmes qui terminent au troisième, quatre dans les trois huitièmes qui lisent aussi le quatrième. Cela donne vingt-sept huitièmes. Avec un seizième de retour au départ, la consommation moyenne totale E vérifie E égal à vingt-sept huitièmes plus E sur seize. Elle vaut donc dix-huit cinquièmes, trois virgule six bits, au lieu de vingt-quatre cinquièmes. Nora choisit ce recyclage pour la commande qui réduit la moyenne. Elle garde les sorties et le coût du redémarrage dans l'équation : le quatrième bit de la suite refusée est lui aussi consommé.
Aucun arbre binaire borné ne partage toutes ses feuilles en cinq parts égales
Camille demande maintenant de finir toujours avant un nombre N fixé de bits, sans répondre autrement que par une carte. Même si certaines branches finissent plus tôt, Nora peut prolonger fictivement leurs sorties jusqu'à N bits : tous les prolongements reçoivent le même numéro déjà remis. Les deux à la puissance N mots de longueur N auraient alors été répartis entre les cinq cartes. Pour obtenir cinq chances égales, chacune devrait recevoir deux à la puissance N divisé par cinq mots, un nombre entier. Cinq ne divise aucune puissance de deux. Nora refuse donc la promesse d'une fin toujours bornée avec ce modèle de seuls bits équilibrés.
La demande reste possible si un échec explicite est permis. Avec quatre bits au maximum, la construction recyclée remet chaque carte dans trois des seize mots, et attend encore seulement pour un, un, un, un. Nora clôt cette dernière branche en répondant « pas de carte remise ». La chance de réussite vaut quinze seizièmes ; conditionnellement à la réussite, chaque carte possède trois quinzièmes, un cinquième. Camille garde cette condition dans sa feuille. Elle ne remet pas zéro dans la branche restante : zéro aurait alors quatre seizièmes tandis que chacune des autres cartes n'en aurait que trois, et l'égalité de la commande serait perdue.
Nora contrôle aussi ce qu'un autre protocole uniforme pourrait avoir terminé à chaque profondeur k. Chaque mot binaire de longueur k a une chance de un sur deux à la puissance k. Les préfixes ayant déjà remis une carte ne peuvent lui donner plus d'un cinquième de chance, puisque les sorties futures ne retireront aucun poids déjà attribué. Chaque carte peut donc avoir terminé dans au plus la partie entière de deux à la puissance k divisé par cinq préfixes. Au total, au moins le reste de cette division doit encore attendre. Ce compte donne une borne sur toutes les procédures binaires exactes, pas seulement sur la règle particulière que Camille vient de réaliser.
Pour k zéro, un, deux et trois, les restes sont un, deux, quatre et trois. Divisés par les nombres de préfixes possibles, ils donnent un, un, un et trois huitièmes comme chances minimales d'attente. La multiplication par seize recommence le même cycle de restes quatre profondeurs plus tard. La somme de ces chances minimales vaut donc vingt-sept huitièmes multiplié par un plus un seizième plus son carré et ainsi de suite, dix-huit cinquièmes. Or la consommation moyenne de bits est la somme des chances d'attendre après chaque profondeur. Le recyclage atteint exactement ces restes à chaque profondeur ; Nora dispose donc ici d'une preuve de sa moyenne minimale parmi les procédures exactes autorisées, sans s'appuyer seulement sur la comparaison avec le rejet complet.
La borne porte sur l'expérience annoncée : cinq issues uniformes, bits équilibrés et indépendants, aucune autre décision aléatoire gratuite. Nora ne la remet pas comme un temps minimum en secondes ni comme le coût d'une pièce réelle. Son calcul a compté des chemins binaires. Les numéros des cartes peuvent être permutés sans changer les chances ; leur décoration ou leur longueur écrite ne fournit aucun bit supplémentaire. Cette limite du modèle reste une garde générale, sans crédit pour une nouvelle construction de tirage.
Une entrée biaisée peut donner un bit équitable, sous une autre hypothèse
Une autre branche fournit des bits indépendants avec une probabilité p de un, constante mais inconnue, strictement entre zéro et un. Nora ne peut plus utiliser directement les huit mots de trois bits comme des issues équiprobables. Elle groupe les bits d'entrée par paires. Les paires zéro, un et un, zéro possèdent chacune la chance p multiplié par un moins p. Elle remet un bit équitable pour ces deux orientations opposées, l'une codée zéro, l'autre un. Les paires zéro, zéro et un, un sont écartées, et deux nouveaux bits d'entrée sont lus. Ce procédé classique d'extraction est explicitement distinct du recyclage des cinq cartes.
La probabilité de succès d'une paire vaut deux p fois un moins p. Le nombre moyen de bits d'entrée nécessaires pour remettre un bit équitable vaut donc deux divisé par cette probabilité, soit un sur p fois un moins p. Pour p trois quarts, les deux orientations utilisables possèdent chacune trois seizièmes ; le succès vaut trois huitièmes, et le coût moyen seize tiers de bits d'entrée. Nora conserve ce coût avant de lancer le tirage des cinq cartes. Un bit équitable extrait n'est pas assimilé à un seul bit d'entrée simplement parce qu'il est remis comme zéro ou un.
Chaque bit extrait utilise un nouveau segment de la suite indépendante d'entrée. Dans un segment qui termine après plusieurs paires, les refus précédents ont le même poids quelle que soit l'orientation finale ; zéro, un et un, zéro ont encore la même chance. Le bit remis est donc équitable même conditionnellement au nombre de paires utilisées pour cette extraction. Nora peut ainsi alimenter le recyclage avec des bits équitables successifs, tandis que leurs coûts moyens d'entrée restent comptés. Pour p trois quarts, le coût moyen du choix parmi cinq cartes vaut dix-huit cinquièmes multiplié par seize tiers, quatre-vingt-seize cinquièmes de bits d'entrée. Camille ne présente pas trois virgule six comme ce second coût : il désignait les bits équitables remis par l'extracteur.
Camille essaie une autre entrée où les bits restent indépendants, mais les positions impaires donnent un avec trois quarts et les positions paires avec un quart. Sur une paire, un puis zéro possède alors neuf seizièmes, zéro puis un seulement un seizième. Conditionnellement à une paire utilisable, les orientations ont les chances neuf dixièmes et un dixième. Nora refuse donc l'annonce d'un bit équitable dans cette branche. L'indépendance des deux positions n'avait pas remplacé la constance de leur probabilité. Elle conserve les probabilités distinctes et isole cette entrée, plutôt que de donner ses bits à la procédure des cinq cartes sous l'ancienne hypothèse.
Si p vaut exactement zéro ou exactement un, aucune orientation utilisable ne se produit : toutes les paires sont égales. Nora ne promet pas une fin du procédé à partir de cette entrée. Le modèle constant entre zéro et un possède un coût moyen fini pour chaque p fixé, mais ce coût peut devenir arbitrairement grand lorsque p approche une extrémité. Camille garde donc la clause qui exclut les deux extrêmes et renonce à une borne commune de coût pour tous les p possibles. Cette limite ne change ni le calcul à trois quarts ni la preuve du tirage uniforme depuis les bits équitables effectivement extraits.
Les catégories de cartes citées n'apportent ni équité, ni biais, ni protocole de tirage à ces choix stipulés sur papier.