Pour une activité fictive de feuilles écrites, Nora remet quatre noms A, B, C et D. Camille doit tirer un nom avec des chances proportionnelles aux poids un, un, deux et quatre. Les poids sont des données stipulées avant le tirage, sans préférence ou quantité réelle mesurée. Elle souhaite préparer une petite table où un tirage choisit d'abord une colonne, puis l'une de ses deux sorties. Les quatre colonnes devront rester équiprobables même si les quatre noms ne le sont pas.
Scout Books présente des carnets.
Smitten on Paper présente de la papeterie.
Scribble & Dot présente des carnets à points.
Ces catégories situent les feuilles ; aucun produit, format ou dessin n'est adapté. Les poids, colonnes et chances sont stipulés, sans usage matériel examiné.
La somme des poids vaut huit ; les probabilités demandées sont donc un huitième pour A, un huitième pour B, un quart pour C et une moitié pour D. La méthode classique des alias prépare des colonnes de même poids total, chacune avec au plus deux identités possibles. Elle ne signifie pas que l'on choisit uniformément l'une des deux identités de toutes les colonnes. Le seuil propre à la colonne règle leur partage, et le choix de colonne doit être indépendant du tirage qui sert à ce partage. Nous ne revendiquons pas l'invention de cette représentation.
Deux billets pour chaque colonne peuvent porter des noms différents
Nora commence avec huit billets équiprobables : A, B, C, C, D, D, D, D. Elle les range en quatre colonnes de deux billets. La colonne A contient A et D ; la colonne B, B et D ; la colonne C, deux C ; la colonne D, deux D. Camille tire une colonne parmi quatre, puis un billet parmi deux dans cette colonne, indépendamment. Les huit couples de choix sont équiprobables. A et B n'occupent chacun qu'un couple, C deux, D quatre, ce qui remet les probabilités demandées sans rendre les colonnes inégales.
Camille conserve comme réalisation la colonne A puis son second billet, D. Le nom remis est donc D, pas A. Le nom de la colonne désigne son adresse dans la table ; le billet qui s'y trouve fournit la sortie. Quand la colonne C est choisie, les deux billets conduisent à C ; Camille n'exige pas une nouvelle identité pour le second. Elle refuse la proposition qui remettait simplement le nom de chaque colonne : les quatre noms auraient reçu un quart, en effaçant la répartition des billets préparés. La table de sorties garde précisément les chances que les seules adresses ne portaient pas.
Nora peut remplacer les deux billets identiques des colonnes C et D par un seuil égal à un : toute la part de la colonne remet son propre nom. Pour A et B, le seuil vaut une moitié ; en dessous, on remet le nom de la colonne, sinon D. Camille stipule un nombre de comparaison indépendant qui prend zéro ou une moitié avec chances égales. La comparaison est strictement « plus petit que le seuil ». Le zéro donne A dans sa colonne, la moitié donne D ; les deux valeurs restent inférieures au seuil un de C et D. Le cas d'égalité appartient donc à la seconde sortie, conformément aux deux billets représentés.
La préparation remplit les colonnes sans modifier les masses demandées
Pour préparer la table depuis les poids, Nora multiplie chaque probabilité par quatre. Les quantités deviennent une moitié pour A, une moitié pour B, un pour C et deux pour D. Chaque colonne à remplir possède une capacité un dans ces unités. A ne suffit pas à remplir sa colonne ; Nora y place sa moitié puis prend une moitié de D pour compléter. La colonne A est fixée, et D possède encore une quantité trois demis. B reçoit ensuite sa moitié et une autre moitié de D. Il reste exactement un pour C et un pour D : leurs colonnes sont pleines avec leur seul nom.
Le geste sur D compte les parts effectivement utilisées. Après avoir complété A, laisser encore deux unités de D aurait créé une moitié supplémentaire à distribuer. Camille retire cet état et conserve trois demis. Compléter B consomme encore une moitié et ramène D à un. Les deux colonnes fixes portent chacune une unité totale ; les deux masses restantes font ensemble deux unités. Nora peut donc vérifier à chaque geste la masse déjà rangée et la masse encore disponible, au lieu de contrôler seulement la taille de chaque colonne après avoir oublié d'où venait sa seconde part.
La même préparation fonctionne avec des poids quelconques non négatifs dont la somme est positive. Parmi les quantités restantes, Nora choisit une identité de quantité inférieure à un et une autre d'au moins un. La première remplit sa propre part ; la seconde fournit le complément jusqu'à un. Ce complément ne peut dépasser ce que la seconde possède, puisqu'il vaut au plus un. Une colonne est ainsi fixée à chaque geste, et la masse encore à ranger baisse d'une unité. Les seuils enregistrent la petite part utilisée, les alias enregistrent l'identité qui a rempli son manque. Les deux sorties n'ont pas besoin de recevoir chacune une moitié.
S'il reste plusieurs colonnes sans aucune quantité supérieure à un, leur masse totale égale pourtant leur nombre : chaque colonne encore libre demande une unité. Toutes leurs quantités doivent donc être exactement un. Une quantité strictement plus petite laisserait un manque que les autres, toutes au plus un, ne pourraient remplir. Nora termine alors par les sorties uniques. Cette égalité de masse justifie le dernier geste de la préparation ; elle ne force pas à arrondir les petites quantités restantes à un. Avec des fractions exactes, les seuils et les quantités conservent les mêmes valeurs jusqu'à la fin.
Les deux tirages doivent former les couples annoncés
Camille reçoit une autre règle : la colonne reste uniforme parmi A, B, C, D, et le bit de partage reçoit globalement autant de zéros que de uns. Les couples possibles sont pourtant seulement A avec zéro, B avec un, C avec zéro et D avec un, chacun avec un quart. Dans la table préparée, ces quatre couples remettent A, D, C et D. A possède désormais un quart, B aucune chance, C un quart et D une moitié. Nora refuse donc cette règle pour les poids un, un, deux, quatre, malgré l'uniformité de la colonne et l'équilibre du bit pris séparément.
Le manque de B est explicite : B n'était présent que dans la première moitié de sa colonne, et le nouveau couplage y envoie toujours le second choix. La bonne marginale du bit, une moitié, est compensée par ses zéros dans d'autres colonnes et ne rétablit aucune première sortie chez B. Camille garde les huit couples indépendants du premier dispositif plutôt que les quatre couples de cette proposition. Ce contrôle porte sur la distribution des couples réellement utilisée par la table ; il ne redessine pas les poids après avoir observé leur résultat.
Nora justifie la formule sous le bon couplage. Chaque colonne possède un quart. Si le seuil de la colonne i vaut q, son nom reçoit q quarts depuis cette colonne, et son alias un moins q quarts. Les contributions à une même identité s'additionnent depuis toutes les colonnes où elle figure. A reçoit la moitié d'un quart, un huitième ; B également. C reçoit l'unité entière de son quart. D reçoit son quart, puis les deux moitiés provenant d'A et B, une moitié en tout. Camille vérifie ainsi chaque sortie depuis ses contributions, sans donner au seul seuil de D la charge de toutes ses apparitions dans la table.
Deux tables peuvent avoir la même loi et remettre des noms différents au même couple
Nora construit une autre table pour les mêmes poids. La colonne A possède A puis C ; la colonne B, B puis C ; les colonnes C et D possèdent chacune deux D. Les huit couples équiprobables donnent toujours un A, un B, deux C et quatre D. La loi finale est donc identique. La colonne C de cette nouvelle représentation utilise seulement une identité qui porte un autre nom que son adresse ; elle peut être enregistrée avec un seuil zéro et un alias D. Rien dans la commande des chances ne demandait que chaque colonne remette parfois son propre nom.
Pour le couple A puis second choix, la première table remettait D et la seconde C. Le même changement a lieu dans B ; dans C, les deux couples passent de C à D. Quatre des huit couples changent donc de sortie lorsque les deux tables lisent exactement les mêmes tirages. Nora conserve ce désaccord dans sa trace. Une égalité de distributions n'était pas une égalité de résultats pour chaque réalisation partagée. Si Camille veut refaire une remise à partir d'un couple sauvegardé, elle doit conserver aussi la table effectivement utilisée. La seconde table peut remplacer la première pour de nouveaux tirages, mais pas expliquer rétroactivement les anciens noms remis.
La vérification par masses admet les deux représentations. Dans la première, C possède une colonne complète ; dans la seconde, sa quantité totale un est répartie entre deux moitiés. D récupère alors les deux colonnes complètes C et D au lieu de sa colonne et des deux moitiés d'A et B. Nora ne prend donc pas une différence de seuil ou d'alias comme un défaut en soi. Elle recalcule les contributions de chaque identité avec les quatre colonnes et le protocole commun. Les masses peuvent être rangées autrement sans changer leur total par nom, tant que chaque colonne possède une unité et que toutes les parts restent non négatives.
Retirer un nom doit atteindre aussi ses alias
Camille interdit maintenant D et demande un tirage parmi les anciens poids restants A un, B un, C deux. Elle propose de supprimer seulement la colonne D, puis de choisir uniformément l'une des trois autres. La colonne A remet encore D dans une moitié, B également ; C remet C dans sa totalité. D garde donc une chance d'un tiers, les deux moitiés de deux tiers de colonnes. A et B reçoivent chacune un sixième, C un tiers. Nora refuse cette suppression des seules adresses : le nom interdit demeurait présent dans deux autres colonnes comme alias.
Nora peut conserver la première table à condition de refuser toutes les sorties D, puis de refaire un tirage indépendant complet. Les anciennes chances d'A, B, C étaient un huitième, un huitième, un quart, de somme une moitié. Conditionnellement à une sortie autorisée, elles deviennent un quart, un quart et une moitié, les proportions souhaitées après retrait. La probabilité de réussite par tentative est une moitié, donnant deux tentatives en moyenne. Camille conserve aussi les refus venant des colonnes A et B ; si elle refusait seulement ceux de la colonne D, elle obtiendrait le mauvais dispositif qu'elle vient d'écarter.
Une nouvelle préparation peut éviter ces refus. Les probabilités A un quart, B un quart, C une moitié et D zéro donnent, après multiplication par quatre, les quantités un, un, deux et zéro. Nora fixe A et B comme sorties uniques. La colonne D, de part propre nulle, est entièrement remplie par C ; il reste une unité de C pour sa propre colonne. Les quatre colonnes sont encore choisies uniformément, et D peut même être leur adresse sélectionnée dans un quart des réalisations. Pourtant le nom D n'est jamais remis, puisque son seuil vaut zéro et sa seule sortie est C. Camille garde cette différence entre une colonne disponible et une identité de poids nul.
Certaines modifications sont locales, d'autres changent plusieurs seuils
Nora revient aux poids initiaux et transfère une unité de D vers A, donnant deux, un, deux et trois, toujours de somme huit. Elle peut conserver les anciens alias, mais rendre la colonne A entièrement dédiée à A. Sa seconde moitié, qui remettait D, passe donc à A ; B garde une moitié vers B et une moitié vers D, C reste C, D reste D. Les huit couples donnent maintenant deux A, un B, deux C et trois D. Camille accepte cette modification locale, puisqu'elle vérifie effectivement le transfert d'un huitième de chance. Elle ne reconstruit pas toutes les colonnes pour une opération que cette table permet déjà de réaliser exactement.
Une autre commande augmente seulement le poids de D de quatre à cinq. La somme des poids devient neuf, et les chances attendues sont un neuvième, un neuvième, deux neuvièmes et cinq neuvièmes. L'ancien seuil une moitié de A lui donnerait toujours un huitième, puisque sa colonne garderait une chance d'un quart. Modifier seulement la colonne D, qui ne contenait aucune sortie A, ne corrigerait pas cette contribution. Nora refuse donc cette seule modification pour la nouvelle commande. L'augmentation d'un poids avait renormalisé aussi les trois autres probabilités, même si leurs numérateurs étaient restés un, un et deux.
La préparation corrigée donne à A et B des seuils quatre neuvièmes et à C un seuil huit neuvièmes, avec D comme alias de chacune ; la colonne D reste entièrement D. Multipliés par un quart, les trois seuils remettent un neuvième, un neuvième et deux neuvièmes. Les compléments vers D apportent onze trente-sixièmes : deux fois cinq neuvièmes d'un quart et une fois un neuvième d'un quart, plus le quart direct de D, donnent cinq neuvièmes. Nora conserve les trois seuils changés. Leur somme avec les contributions d'alias, et non le seul nouveau poids cinq écrit près de D, contrôle la loi remise.
Pour comparer ces seuils exactement, Camille utilise un entier de zéro à huit, uniforme et indépendant de la colonne. Dans A et B, les valeurs zéro à trois remettent le nom local, les cinq autres D. Dans C, les valeurs zéro à sept remettent C, huit remet D. Les trente-six couples colonne, entier possèdent donc le même poids : quatre donnent A, quatre B, huit C et vingt D. Cette réalisation en cases entières évite de remplacer quatre neuvièmes par une moitié pour simplifier le partage. Le tirage uniforme sur neuf est ici une donnée du protocole ; la préparation de la table ne lui confère pas automatiquement un coût fixe en bits.
La table porte une loi, pas une promesse de nombre gratuit de bits
Si Camille tient à produire ce nombre parmi neuf depuis des bits indépendants équilibrés, elle doit ajouter un procédé de tirage approprié. Lire quatre bits donne seize valeurs ; refuser neuf jusqu'à quinze puis recommencer donne chacune des neuf valeurs avec la même chance. Les tentatives lisent quatre bits, réussissent avec neuf seizièmes et utilisent en moyenne soixante-quatre neuvièmes de bits. Les deux bits permettant de choisir une colonne parmi quatre s'ajoutent à ce coût dans ce dispositif séparé. Nora ne compte donc pas un tirage de colonne et une comparaison comme deux bits seulement : ce sont deux opérations dont les entrées aléatoires sont précisées ailleurs.
La première table à poids un, un, deux, quatre peut au contraire être réalisée directement avec deux bits pour la colonne et un bit pour son billet, trois bits au total. Le relevé des huit billets avait le même coût si trois bits en choisissaient un uniformément. Nora n'attribue donc pas ici un gain d'entropie à la représentation par quatre colonnes. Elle choisit cette représentation pour conserver ses parts et alias auprès des adresses et vérifier les modifications demandées. Ce commentaire sur le coût ne reprend pas la recherche d'un tirage binaire optimal : il sépare seulement le nombre d'opérations de table des décisions aléatoires stipulées pour les remplir.
Reconstituer la loi d'une adresse reçue exige un autre partage
Une branche ne conserve que le nom remis, et Camille doit reconstruire aléatoirement une adresse et son billet qui aient la même loi jointe que dans la première table. Ce n'est pas retrouver l'adresse historique effacée. Si elle reçoit D, trois colonnes sont compatibles, A, B et D, mais leurs chances conditionnelles ne sont pas trois tiers. A avait fourni un huitième du total, B un huitième, D un quart ; rapportées à la moitié de chance du nom D, ces contributions donnent un quart, un quart et une moitié. Nora refuse donc le choix uniforme parmi les trois adresses. Elle tire uniformément l'un des quatre couples compatibles A avec second billet, B avec second billet, D avec premier ou D avec second. Les quatre couples avaient la même chance initiale ; conserver leurs deux possibilités dans D remet justement la moitié à cette adresse, au lieu de traiter trois colonnes comme trois événements de même poids.
Camille complète la reconstruction pour les autres noms. A impose la colonne A et son premier billet ; B impose B et son premier. C partage uniformément ses deux billets dans la colonne C. Pour le nom D, de chance une moitié, chacun des quatre couples reconstruits reçoit conditionnellement un quart : sa chance totale devient un huitième. A et B donnent directement leur couple avec un huitième ; les deux couples de C reçoivent chacun la moitié de son quart, également un huitième. Les huit couples reconstruits possèdent donc la même loi jointe que le premier tirage. Si Camille choisissait toujours la colonne D après la sortie D, cette adresse aurait au contraire une moitié de chance totale, contre le quart prévu. Nora accepte la remise conditionnelle remplie pour reconstruire une distribution de couples, et garde les tirages nouveaux qui la produisent ; elle ne les date pas comme les anciens choix perdus.
Les catégories citées n'apportent ni poids, ni indépendance, ni table de choix à ces préparations sur papier.