Nora prépare deux listes fictives pour une table où chacun écrira une carte. Camille veut comparer les noms inscrits sans conserver, dans la feuille de comparaison, la totalité des deux listes. Elle souhaite une proportion de noms communs parmi les noms présents au moins une fois. Chaque nom représente ici une identité distincte, sans qualité mesurée du matériel. Une liste répétant le même nom reste le même ensemble. La scène ne constitue ni un essai de fournitures ni une recommandation d'achat.
TWSBI présente des accessoires pour stylos.
Nahvalur présente des instruments d'écriture.
Laban présente des stylos-plume.
Ces catégories situent les listes écrites ; aucun produit, dessin ou procédé n'est adapté. Les ensembles, ordres et probabilités sont stipulés, sans garantie empruntée aux fabricants.
Dans le premier modèle, la liste de Nora contient a et b, celle de Camille b et c. Les lettres sont seulement des identifiants. Leur réunion contient trois noms et leur intersection un nom. La ressemblance demandée est donc un tiers. Nous choisissons uniformément l'un des six ordres des trois noms, puis utilisons exactement cet ordre dans les deux listes. Chaque liste retient son premier nom selon cet ordre commun. Cette construction classique appartient à la famille des signatures par minimum ; nous n'en revendiquons pas l'invention.
Deux choix uniformes séparés ne répondent pas à la même demande
Camille propose d'abord de tirer un nom dans sa liste, indépendamment du nom tiré chez Nora. Chacune des deux listes possède deux noms ; chaque choix local leur donne une moitié. Pour que les résultats soient identiques, Nora et Camille doivent chacune choisir b. Cela arrive avec une moitié multipliée par une moitié, soit un quart. Les deux autres possibilités communes n'existent pas : a manque chez Camille et c chez Nora. Camille retire le quart de la case où elle devait remettre la ressemblance d'un tiers. Les choix locaux étaient uniformes, mais leur indépendance ne produisait pas le renseignement demandé sur la réunion des noms.
Nora réalise maintenant les six ordres partagés. Si b est premier dans la réunion, les deux listes retiennent b, quelle que soit la position respective d'a et c après lui. Cela couvre b, a, c et b, c, a. Si a est premier, Nora retient a et Camille b ou c ; si c est premier, Camille retient c et Nora a ou b. Il y a donc deux accords sur six ordres, un tiers. Dans une réalisation a, c, b, Nora garde a et Camille c. Leur désaccord n'annonce pas que les listes sont disjointes : b figure encore dans les deux listes, mais passe après les deux noms privés dans cet ordre.
Camille demande pourquoi le premier de la réunion suffit à expliquer tous les accords. Si les minima locaux sont égaux à un nom t, aucun nom de l'une ou l'autre liste ne passe avant t : t est donc premier dans leur réunion et appartient aux deux. Inversement, si le premier de la réunion appartient aux deux listes, aucune des deux ne peut choisir un autre premier nom. L'accord des minima équivaut exactement à cette appartenance commune du premier global. Puisque chaque nom de la réunion est premier avec la même chance, la probabilité d'accord est le nombre de noms communs divisé par le nombre de noms réunis. Camille conserve cette équivalence, qui porte sur une priorité commune, plutôt que deux preuves séparées d'uniformité locale.
Dans une autre remise, Nora inscrit a, b, c et Camille b, c, d. Les deux noms communs se partagent deux des quatre possibilités de premier global. L'accord arrive avec une moitié. Deux tirages locaux indépendants auraient donné seulement deux neuvièmes : les possibilités b avec b et c avec c, chacune d'un neuvième. Nora ne choisit pas entre les deux nombres après avoir vu un résultat favorable ; elle choisit avant le tirage le protocole correspondant à la fraction intersection sur réunion. Les quatre noms peuvent être placés sur une même feuille d'ordre même lorsque chaque liste en ignore un.
Des petites valeurs avec égalités changent le premier nom
Camille souhaite remplacer l'ordre par un numéro zéro ou un tiré indépendamment pour chaque nom. Elle conserve le nom de plus petite valeur dans chaque liste et départage les égalités par l'ordre alphabétique a, b, c. Elle pense que les valeurs tirées symétriquement donneront encore un premier global uniforme. Nora énumère les huit triplets de valeurs. a est choisi premier dans cinq triplets, b dans deux, c dans un. En particulier, chaque fois qu'a vaut zéro, il passe avant les autres noms de valeur zéro ; lorsque toutes les valeurs sont un, il passe encore devant eux. Le départage alphabétique a donc réintroduit une préférence que les petits numéros seuls n'avaient pas distinguée.
L'équivalence entre accord local et premier global commun reste valable pour cet ordre complet « valeur, puis lettre ». Ce qui change est la loi de ce premier global. Dans les listes a, b et b, c, les résultats s'accordent exactement quand b gagne la réunion. Les deux triplets où cela arrive sont les valeurs un, zéro, zéro et un, zéro, un. L'accord vaut donc deux sur huit, un quart. Camille conserve les valeurs de ces deux réalisations et retire la mention d'un tiers. Le défaut ne vient pas d'une collision entre deux noms remis comme identiques : elle avait bien conservé les identifiants. Il vient du poids inégal attribué aux premiers noms par la règle de départage.
Nora essaie un départage tiré une seule fois pour toute la réunion. Indépendamment des trois petites valeurs, elle choisit l'un des six ordres de priorité avec chances égales. Un nom passe avant un autre si sa petite valeur est plus faible ; à valeur égale, l'ordre de priorité commun les départage. Les quarante-huit préparations possibles sont symétriques entre a, b et c. Permuter les noms dans une préparation donne une autre préparation de même chance, dont le vainqueur porte le nom permuté. Chacun reçoit ainsi seize premières places. Camille retrouve un tiers d'accord sans interdire les égalités de numéros, en conservant un départage partagé qui respecte cette symétrie.
Dans la préparation où les trois valeurs sont zéro et la priorité c, b, a, Nora retient b tandis que Camille retient c. Si Camille départageait sa seule égalité en choisissant b, les deux listes annonceraient au contraire un accord : pourtant le premier global restait c, qui manque chez Nora. Elle renonce à cette seconde décision locale. Le départage commun n'est pas un détail facultatif après le tirage des numéros ; il fait partie de l'ordre qui relie les deux minima à la réunion. La feuille remise conserve donc les identifiants et la priorité effective, pas seulement la valeur zéro qui ne permettrait pas de retrouver ces premiers noms.
Réunir les premiers noms conserve un minimum, pas les noms communs
Sous un ordre partagé donné, Nora prend le premier de sa liste et Camille celui de la sienne. Le plus tôt des deux est aussi le premier de leur réunion. Pour la réalisation c, b, a, d sur les listes a, b, c et b, c, d, chacune retient c ; la réunion retient c également. Pour a, d, b, c, Nora retient a et Camille d ; la réunion retient a. Aucun nom oublié localement ne pouvait passer avant ces deux premiers : il aurait alors été choisi dans la liste où il figurait. Nora peut donc réunir deux signatures pour préparer la signature de leur réunion, sans recevoir de nouveau toutes les listes.
La remise change si Camille réclame le premier de l'intersection exacte. Avec l'ordre a, b, c, d, la liste a, b et la liste b, d gardent a et b ; leur intersection possède b. Remplaçons seulement la première liste par a, c : les deux signatures restent a et b, les deux tailles restent deux, mais l'intersection devient vide. Nora ne donne donc pas b comme un premier commun depuis ces seules signatures. Elle maintient la réunion de minima, qui était justifiée, et refuse la reconstruction de l'intersection. Ce contre-exemple est un contrôle de la limite du résumé, sans devenir une preuve nouvelle sur chaque nom absent.
Deux premiers noms permettent un échantillon commun de la réunion
Camille souhaite maintenant conserver deux premiers noms distincts dans chaque liste. Elle choisit un seul ordre sur a, b, c, d, puis garde les deux premiers disponibles chez Nora et chez elle. Pour obtenir les deux premiers de leur réunion, elle réunit ces petits relevés, élimine leurs identités répétées et conserve les deux premiers selon le même ordre. Si un nom figurait parmi les deux premiers globaux mais manquait dans le relevé d'une liste qui le contient, cette liste posséderait déjà au moins deux noms avant lui. La réunion aussi en posséderait au moins deux avant lui, ce qui contredirait sa place parmi les deux premiers globaux. Le nom demandé ne peut donc avoir été oublié localement.
Cette observation fournit aussi son appartenance aux deux listes. Un nom retenu dans les deux premiers globaux et présent dans une liste doit apparaître dans ses deux premiers locaux. Il est commun exactement quand il figure dans les deux petits relevés. Camille peut donc compter, parmi les deux noms globaux conservés, ceux qui appartiennent aux deux listes, sans demander la totalité de leurs noms. Elle ne généralise pas cette reconnaissance à un nom arrivé plus tard dans l'ordre : les listes auraient pu l'oublier chacune pour des raisons différentes. La borne de rang donne précisément le renseignement qui manquait dans la précédente demande d'intersection complète.
Pour l'ordre a, d, b, c, Nora conserve a, b et Camille d, b. La réunion des relevés contient a, d, b ; ses deux premiers sont a et d. Aucun n'apparaît dans les deux relevés, donc la proportion commune de cet échantillon vaut zéro. Le b présent dans les deux relevés passe trop tard pour cet échantillon. Camille le laisse hors du numérateur, même si le compter rendrait l'annonce plus proche de la véritable moitié. Sa procédure avait choisi les deux premiers de la réunion, et non tous les noms encore visibles quelque part dans les signatures locales.
Pour l'ordre b, a, d, c, Nora conserve b, a et Camille b, d. Les deux premiers réunis sont b et a. b figure dans les deux relevés, a seulement dans celui de Nora : la proportion commune de l'échantillon vaut une moitié. Pour b, c, a, d, les deux relevés contiennent b, c ; leurs deux premiers globaux sont tous deux communs, donnant un. Ces trois réalisations remettent zéro, une moitié et un sans changer les listes initiales. Nora conserve les deux identités échantillonnées près du résultat afin que le numérateur puisse être contrôlé depuis les signatures reçues.
Le dénominateur n'est pas la taille de tous les noms encore visibles
Camille propose une autre formule : prendre les noms communs aux deux petits relevés, puis diviser par tous les noms visibles dans leur réunion. Sur a, d, b, c, les relevés a, b et d, b donnent un nom commun sur trois, soit un tiers, au lieu du zéro de l'échantillon global a, d. Les noms visibles n'ont pas tous été retenus par la même règle de rang global. b a survécu parce que chaque liste possédait un seul nom avant lui ; il occupait pourtant la troisième place globale. Nora refuse de le faire contribuer comme si les trois noms réunis formaient un échantillon uniforme de taille trois.
L'énumération des vingt-quatre ordres montre l'effet de cette formule sur les listes a, b, c et b, c, d. Si les deux premiers globaux sont b et c, les signatures locales sont identiques et la formule donne un. Cela arrive dans quatre ordres : les deux noms communs occupent les deux premières places, dans leurs deux ordres possibles, puis les deux autres dans leurs deux ordres possibles. Dans les vingt autres ordres, les signatures locales partagent exactement un nom et leur réunion en contient trois, donnant un tiers. La moyenne obtenue est donc quatre vingt-quatrièmes plus vingt vingt-quatrièmes d'un tiers, soit quatre neuvièmes. Elle n'est pas la moitié demandée.
Nora remet la bonne fraction : nombre de noms communs parmi les deux premiers globaux, divisé par deux. Chaque paire de noms de la réunion est première avec la même chance, un sixième, car les deux membres peuvent occuper les deux premières places dans deux ordres et les deux autres les places suivantes dans deux ordres. Les six paires sont a, b ; a, c ; a, d ; b, c ; b, d ; c, d. a, d donne zéro, b, c donne un, les quatre autres donnent une moitié. Leur moyenne est une moitié. Camille a changé le dénominateur et les noms admissibles au numérateur ensemble, en reconstruisant d'abord un échantillon global de taille fixée.
Nora peut justifier cette moyenne sans réénumérer tous les ordres lorsque les listes changent. Si leur réunion possède N noms, chaque nom est retenu dans les deux premiers avec chance deux sur N. Le nombre de noms communs retenus est une somme d'indicateurs, un pour chaque identité commune ; sa moyenne vaut donc le nombre commun multiplié par deux sur N. Diviser par deux remet la fraction intersection sur réunion. Les deux indicateurs de présence ne sont pas indépendants, puisqu'exactement deux noms sont retenus ; la somme de leurs moyennes suffit néanmoins pour ce calcul. Camille conserve cette preuve et ne remplace pas l'échantillon sans remise par deux tirages indépendants.
Dans les listes de quatre noms déjà données, l'échantillon donne zéro avec un sixième, une moitié avec quatre sixièmes et un avec un sixième. Sa moyenne vaut une moitié, mais une seule remise peut s'en éloigner d'une moitié. Le carré moyen de cet écart vaut deux fois un sixième d'un quart, soit un douzième. Avec un seul premier nom, le résultat serait zéro ou un avec chances égales et le carré moyen de l'écart un quart. Nora choisit ici les deux noms parce que ce protocole précis réduit ce carré moyen à un tiers du précédent, tout en conservant la moyenne voulue. Elle ne transforme pas cette comparaison exacte du petit modèle en marge garantie pour chaque réalisation.
Le même rang doit servir aux deux signatures reçues
Une dernière préparation conserve a, b chez Nora et b, c chez Camille, mais emploie deux ordres incompatibles. L'ordre de Nora est a, b, c ; celui de Camille b, c, a. Les signatures à un nom sont a et b. Camille reçoit seulement ces résultats et propose de garder b comme premier de la réunion, en utilisant son ordre à elle. Pourtant, sous son ordre, la liste de Nora aurait également dû garder b plutôt qu'a. La signature a a été construite avec une autre priorité. Nora refuse donc d'attribuer au couple reçu les propriétés d'un échantillon commun, même si les lettres et les tailles des listes n'ont pas changé.
Camille retrouve la liste exacte de Nora et la relit sous l'ordre b, c, a déjà choisi pour la nouvelle préparation. Elle obtient b ; les deux signatures sont désormais b et b, et le premier de la réunion est bien b. Cette reconstruction est un geste sur la liste retrouvée, pas une traduction automatique d'a en b depuis l'ancienne signature. Pour continuer ensuite les ajouts, Nora conserve cette même priorité globale : un nouveau nom remplace le premier s'il le précède, et prend éventuellement place dans les deux premiers en faisant sortir le dernier. Les signatures demeurent ainsi comparables parce que leur convention de rang et leurs identités ont été reçues ensemble.
Les catégories de fournitures citées n'apportent aucun ordre de priorité ou garantie probabiliste supplémentaire à ces modèles sur papier.