Nora reçoit des noms écrits pour préparer une table de rangement fictive. Un même nom peut revenir plusieurs fois. Camille demande combien d'identités différentes figurent dans le dossier, et non combien de fiches sont arrivées. Elle accepte d'étudier une représentation courte donnant un nombre estimé, mais veut savoir quelles décisions cette représentation permet réellement. Aucun stock, récipient ou usage matériel n'est observé ; les identités et les opérations ci-dessous sont stipulées sur papier.
Sistema présente des contenants alimentaires.
LocknLock présente des contenants.
Curver présente des solutions de rangement.
Ces catégories situent les noms de la fiche. Aucun produit, procédé ou garantie de comptage ne vient des pages citées ; leurs images ne sont pas examinées.
Chaque identité possède un code binaire fixe de trois chiffres. Le premier choisit une case, zéro ou un. Les deux derniers fournissent un rang : un si leur premier chiffre est un, deux s'ils sont zéro-un, trois s'ils sont zéro-zéro. Chaque case conserve le plus grand rang reçu, ou zéro si elle est vide. Le zéro de case vide se distingue ainsi du rang trois donné par le suffixe tout zéro. C'est un modèle réduit de résumé par maxima binaires, de la famille classique LogLog et HyperLogLog, sans constante industrielle, invention revendiquée ou promesse de précision.
Le nombre des passages ne devient pas le nombre estimé
Nora donne à A le code zéro-un-zéro, à B zéro-zéro-un et à C un-zéro-zéro. A porte la première case à un ; B la porte ensuite à deux ; C porte la seconde à trois. Le relevé final est deux, trois. Camille relit A, B, C une seconde fois. Aucun rang ne dépasse les maxima déjà présents : le relevé reste deux, trois, alors que le nombre de passages a doublé. Elle garde cette absence de modification pour sa commande d'identités distinctes. La fiche ne prétend pas conserver six occurrences puis les diviser par deux ; les occurrences répétées n'ont simplement aucune contribution nouvelle aux maxima.
Dans une autre branche, un nom D reçoit le code un-un-un, donc rang un dans la seconde case. Ajouter D après A, B, C ne change toujours pas deux, trois. Cette fois pourtant, il y a quatre identités au lieu de trois. Nora refuse la mention « toute identité nouvelle augmente le relevé ». Le maxima trois de C absorbe le rang un de D. Camille garde D dans son dossier exact et constate la différence entre deux listes donnant le même petit relevé. Elle peut remettre une estimation depuis les maxima, mais ne peut certifier trois identités parce que le quatrième nom n'a pas fait bouger une case.
Ces deux gestes imposent des conditions différentes à l'attribution des codes. Toutes les occurrences d'un même nom gardent son code ; tirer un code neuf à chaque passage ferait évoluer le relevé depuis des répétitions. Dans la commande présente, Camille refuse ce nouveau tirage. Elle ne remplace pas non plus le code de D pour forcer sa visibilité après réception : cela modifierait la convention depuis le résultat constaté. La table des codes est conservée auprès de la préparation, sans confondre une identité supplémentaire et un tirage supplémentaire.
Les rangs doivent être transformés avant d'être réunis
Pour donner un nombre à un relevé R, Nora stipule ici le score brut suivant : quatre divisé par la somme des deux quantités deux à la puissance moins R. Sur deux, trois, le dénominateur vaut un quart plus un huitième, soit trois huitièmes. Le score est donc trente-deux tiers. Il n'est pas trois et n'est pas annoncé comme tel : le petit modèle n'a encore choisi aucun coefficient de calibration. Nora transmet le relevé deux, trois et ce score calculé, avec deux champs séparés. Le nombre brut ne reçoit pas le nom de compte exact par la seule présence d'une formule.
Camille avait voulu moyenner d'abord les deux rangs, obtenant deux et demi, puis appliquer la puissance à cette moyenne. Cette autre préparation aurait donné deux fois deux à la puissance deux et demi, soit huit fois la racine de deux. Elle diffère de trente-deux tiers. Nora conserve les deux contributions un quart et un huitième avant leur somme. Une case plus haute réduit sa contribution au dénominateur, mais la transformation exponentielle ne permet pas de déplacer librement la moyenne avant elle. Camille renonce à remplacer les deux rangs par leur moyenne dans cette commande.
La perte devient visible sans rang fractionnaire : les relevés zéro, deux et un, un ont tous deux une somme de rangs égale à deux. Le premier donne quatre divisé par un plus un quart, seize cinquièmes. Le second donne quatre divisé par une moitié plus une moitié, quatre. Camille avait proposé de transmettre seulement la somme des rangs pour réduire encore la fiche. Nora refuse cette compression pour le score convenu : une même somme ne détermine pas le dénominateur. Elle garde les deux cases et retire le score quatre de la préparation zéro, deux. L'égalité des sommes n'a pas créé l'égalité des contributions transformées.
Une calibration remplie sur un nom ne règle pas tous les dossiers
Nous fixons une loi séparée : chaque identité différente reçoit uniformément l'un des huit codes, indépendamment des autres identités. Les répétitions gardent le code déjà tiré. Pour une seule identité, le rang vaut un dans quatre codes, deux dans deux codes, trois dans deux codes ; l'autre case reste vide. Les scores correspondants sont huit tiers, seize cinquièmes et trente-deux neuvièmes. Leur moyenne pondérée est cent trente-six quarante-cinquièmes. Ce calcul porte sur huit attributions stipulées, non sur des contenants ou un générateur effectivement testé.
Camille demande un coefficient rendant l'estimation moyenne égale à un pour ce dossier d'une identité. Nora choisit quarante-cinq cent trente-sixièmes et le multiplie par le score brut. La moyenne devient exactement un. Mais les réalisations ne deviennent pas toutes un : un rang un donne quinze dix-septièmes, un rang deux dix-huit dix-septièmes, un rang trois vingt dix-septièmes. Nora contrôle la dernière opération : trente-deux neuvièmes multiplié par quarante-cinq cent trente-sixièmes donne bien vingt dix-septièmes. Camille garde quinze, dix-huit ou vingt dix-septièmes selon le rang, et non une identité certifiée dans chacune des cases.
Nora reçoit ensuite deux identités différentes, avec leurs soixante-quatre paires de codes possibles. Elle les traite réellement par maxima avant de moyenner les scores. La moyenne brute vaut huit cent quatre-vingt-dix-neuf cent quatre-vingtièmes. Le même coefficient donne huit cent quatre-vingt-dix-neuf cinq cent quarante-quatrièmes, qui est inférieur à deux. Camille retire donc la promesse d'une estimation sans biais pour les deux identités. Recalibrer depuis le seul dossier précédent avait fixé une moyenne particulière, sans imposer les moyennes de toutes les tailles. Elle ne choisit pas après coup un autre coefficient dans chaque dossier dont elle ignorait précisément la taille.
Dans cette énumération à deux noms, deux codes portent tous deux rang trois, chacun dans une case différente. Il existe deux paires ordonnées de ce type parmi les soixante-quatre. Le relevé trois, trois donne score seize, puis estimation quatre-vingt-dix dix-septièmes sous le coefficient choisi. Les deux noms ne sont pas devenus cinq noms : cette grande réalisation appartient à la loi examinée. Camille conserve ce cas dans le relevé de dispersion et refuse de ramener seulement ses grandes sorties à deux après les avoir vues. Un écrêtage aurait produit une nouvelle règle, dont la moyenne ne serait plus celle qui vient d'être calculée.
Réunir les maxima conserve l'union mais n'additionne pas les estimations
Deux listes utilisent maintenant la même attribution fixe des codes. Nora possède A et B, donnant deux, zéro. Camille possède C et D, donnant zéro, trois. Les maxima pris case par case donnent deux, trois, comme le traitement direct des quatre identités réunies. Une identité déjà présente dans les deux listes ne compterait pas deux fois par ce geste : sa contribution fixe rencontrerait elle-même et resterait inchangée. La réunion des relevés reproduit donc exactement le relevé de l'union, sous la convention reçue. Elle ne reproduit pas un compte exact de cette union.
Pour les deux feuilles présentes, le score brut local de Nora vaut seize cinquièmes ; celui de Camille trente-deux neuvièmes. Nora calcule leur somme avec le dénominateur quarante-cinq : cent quarante-quatre plus cent soixante donne trois cent quatre quarante-cinquièmes. Le score du relevé réuni vaut au contraire trente-deux tiers. Camille refuse l'addition des deux sorties comme formule de réunion. Les maxima ont changé simultanément les deux termes d'un même dénominateur ; traiter séparément les inverses de ces dénominateurs ne conserve pas l'inverse de leur somme reçue.
Camille tente ensuite de calculer la taille de l'intersection par la somme des deux scores moins celui de l'union. Nora remplit un cas où la première liste porte un seul nom de rang trois dans la case zéro, la seconde un autre nom de rang trois dans la case un. Elles sont disjointes. Leurs scores valent chacun trente-deux neuvièmes, celui de l'union seize. La différence vaut moins quatre-vingts neuvièmes, alors que l'intersection contient zéro nom. Nora retire cette formule comme réponse admissible à une taille d'intersection : la véritable identité d'inclusion-exclusion porte sur des comptes exacts, tandis que ces trois scores non linéaires ne la respectent pas réalisation par réalisation.
Remplacer ce nombre négatif par zéro permettrait de remettre un nombre non négatif, mais ne justifierait pas l'exactitude de l'intersection. Camille conserve donc l'échec visible dans le dossier de test, puis demande les listes exactes pour répondre zéro. Elle ne présente pas ce renseignement reçu des listes comme une réparation obtenue depuis les maxima. La reconstruction exacte de l'union des relevés était encore valable dans cette branche ; c'est la transformation de trois scores en un compte commun qui a échoué. Nora retire cette opération particulière tout en conservant la réunion par maxima pour sa commande initiale.
Réduire le nombre de cases consomme un chiffre de destination
Une branche distincte utilise quatre chiffres par code. Les deux premiers choisissent maintenant quatre cases zéro-zéro, zéro-un, un-zéro, un-un ; les deux derniers donnent le rang selon la règle initiale. Camille veut réduire ensuite la fiche à deux cases en ne gardant que le premier chiffre de destination. Le second chiffre de destination devient alors le premier chiffre du suffixe. S'il vaut un, le rang grossier est nécessairement un. S'il vaut zéro, le rang grossier est l'ancien rang augmenté d'un. Une case fine vide ne fournit aucune contribution ; sa valeur zéro n'est pas le rang d'un nom oublié.
Nora reçoit le relevé fin deux, un, zéro, trois. Dans la première paire, la case zéro-zéro occupée fournit rang trois à la destination grossière zéro ; la case zéro-un occupée fournit seulement rang un, quelle que soit sa valeur fine un. Le maximum grossier est trois. Dans la seconde paire, un-zéro est vide et n'apporte rien ; un-un fournit rang un malgré son ancien trois. Le résultat est donc trois, un. Camille avait pris simplement les maxima des deux paires, donnant deux, trois. Elle retire cette sortie et remet trois, un avec la règle de réinterprétation du chiffre effectivement déplacé.
Cette réduction peut être contrôlée sans retrouver les noms. Dans chaque case fine, tous les noms partagent le chiffre déplacé. Quand il vaut un, tous donnent le même rang grossier un dès qu'au moins un nom existe. Quand il vaut zéro, augmenter tous leurs rangs d'un augmente aussi leur maximum d'un. Ces deux faits permettent de transporter exactement le relevé fin vers le relevé grossier. Camille choisit cette opération lorsqu'elle reçoit seulement les quatre maxima. Elle garde toutefois le nouveau nombre de chiffres de suffixe : le rang maximal autorisé passe de trois à quatre, puisque le suffixe possède désormais trois chiffres.
Deux codes empêchent de promettre l'opération inverse. Zéro-un-zéro-zéro et zéro-un-un-zéro ont tous deux rang grossier un dans la destination zéro. Leur relevé grossier est donc un, zéro dans les deux histoires à un nom. Le premier avait pourtant rang fin trois dans la case zéro-un ; le second rang fin un dans cette même case. Nora reçoit le même relevé grossier mais devrait produire deux relevés fins différents. Elle refuse donc l'agrandissement exact depuis cette seule feuille. Cet exemple fixe une limite de conversion ; il ne reçoit pas le crédit d'une nouvelle méthode d'identification des noms perdus.
La destination vide apporte un renseignement différent du rang maximal
Dans la loi uniforme à deux cases, une case reste vide après n identités distinctes avec probabilité un demi à la puissance n. Le nombre V de cases vides a donc une moyenne deux fois cette probabilité. Camille veut résoudre cette égalité en remplaçant la moyenne par la valeur V de sa seule fiche, par une formule adaptée ici : moins deux fois le logarithme de V sur deux. Nora conserve cette opération proposée auprès de ses conditions. Cette approximation d'occupation est classique, sans propriété de moyenne exacte dans le petit modèle.
Pour un seul nom, V vaut toujours un : cette nouvelle sortie donne deux fois le logarithme de deux, environ un virgule trente-neuf, au lieu d'un. Pour deux noms, une moitié des préparations met les deux dans la même destination, donc V un ; l'autre moitié utilise les deux destinations et donne V zéro. Dans ces dernières préparations, le logarithme n'est plus défini. Camille ne remplace pas V zéro par un pour fermer artificiellement le calcul : cela ferait donner la même sortie dans tous les cas à deux noms. Elle choisit plutôt de laisser cette règle inapplicable lorsque les deux cases sont occupées, et de conserver son domaine dans la fiche remise.
Nora refuse aussi de lire V comme une estimation déterministe de la quantité inconnue. Sous la loi donnée, n noms tous dans la même destination produisent V un, pour toute taille n positive. Le renseignement d'occupation permet une règle statistique choisie, mais ne fixe pas n depuis une seule réalisation. Camille ne fait pas certifier un par la case encore vide ; elle conserve séparément la valeur reçue et les conditions de la formule qu'elle peut lui appliquer. Ce garde-fou sur la lecture d'une réalisation ne constitue pas un nouveau procédé de comptage.
Une loi de maxima jointe ne se remplace pas par deux lois marginales
Nora revient exactement à deux noms indépendants de codes uniformes parmi huit. Elle demande que les deux maxima restent au plus un. Pour chaque nom, seuls les codes de rang un sont permis, quatre sur huit, quelles que soient leurs destinations. Les deux noms satisfont ensemble la demande avec probabilité un quart. Pour une seule destination, en revanche, le nom peut aller dans l'autre case sans restriction, ou donner rang un dans la case observée. Cela autorise six codes sur huit ; avec deux noms, le maximum de cette seule case reste au plus un avec neuf seizièmes.
Camille avait multiplié les deux neuf seizièmes pour annoncer quatre-vingt-un deux cent cinquante-sixièmes. Nora conserve le calcul direct un quart, soit soixante-quatre deux cent cinquante-sixièmes. Les deux maxima partagent un total fixé de deux noms ; les événements concernant les deux destinations ne sont pas indépendants après ce partage. Elle laisse cette comparaison dans l'audit pour empêcher une calibration fondée sur le mauvais produit. La formule du score et les transformations exactes des relevés ne dépendent pas de ce produit ; seules les chances attribuées à leurs réalisations seraient fausses si Camille le conservait.
Choisir une vraisemblance exige une autre commande que calibrer une moyenne
Camille reçoit exactement le relevé un, un, et demande quelle taille de dossier rend ce relevé le plus probable sous la loi des huit codes. Pour le produire, tous les noms doivent recevoir rang un et les deux destinations doivent être utilisées. Avec n noms, la première condition arrive avec un demi à la puissance n. Il faut retirer les deux possibilités où tous vont dans une même destination, chacune d'un quart à la puissance n. Pour un, deux, trois puis quatre noms, les chances sont zéro, un huitième, trois trente-deuxièmes et sept cent vingt-huitièmes. Nora conserve ces vraisemblances de la même feuille, en faisant varier la taille supposée du dossier, et non le relevé reçu.
La différence entre deux tailles voisines ferme la recherche au-delà de deux : le passage de n à n plus un change la vraisemblance de moins un demi à la puissance n plus un, augmenté de trois fois un quart à la puissance n divisé par deux. Pour n au moins deux, le premier terme domine strictement. Les chances décroissent donc après deux ; Nora choisit deux sous cette nouvelle commande de maximum de vraisemblance. Le score brut de un, un valait quatre et sa calibration précédente quarante-cinq trente-quatrièmes. Camille ne corrige pas l'un de ces nombres pour faire apparaître l'autre : les deux demandes comparent des objets différents, une moyenne calibrée ou des chances du relevé conditionnelles à chaque taille.
Camille remplace maintenant cette commande par une moyenne après réception, avec une information initiale explicite : les tailles un, deux et trois avaient chacune une chance égale. Le relevé un, un élimine un et donne aux deux autres des poids proportionnels à un huitième et trois trente-deuxièmes. Le poids de deux devient quatre septièmes, celui de trois trois septièmes ; la moyenne de la taille vaut donc dix-sept septièmes. Nora remet ce nombre avec les trois possibilités initiales. Il n'est ni deux, ni quarante-cinq trente-quatrièmes. Si la commande avait garanti deux noms au départ, la moyenne resterait deux : les anciennes chances initiales ne peuvent être retirées du calcul après avoir conservé leur résultat. La nouvelle décision distingue une information sur le dossier avant réception d'une propriété des deux maxima eux-mêmes.
Les catégories citées n'apportent ni code, ni calibration, ni loi probabiliste à ces décisions sur papier.