problème des rencontres

Quatre personnes déposent leur chapeau, puis chacun en reprend un au hasard. Il y a rencontre dès qu'une personne récupère son propre chapeau. Le problème demande la probabilité qu'au moins une telle coïncidence se produise.

La même question se lit avec deux jeux de cartes mélangés : une rencontre apparaît lorsque deux cartes identiques occupent le même rang. Une permutation sans aucune rencontre porte un nom précis : un dérangement.

Le problème des rencontres étudie des coïncidences entre un rang et une étiquette. Dans la version de l'urne, les nombres entiers positifs n et r désignent respectivement le nombre d'étiquettes possibles et leur multiplicité commune ; le nombre total de boules est m = nr. Toutes les mises en ordre des boules physiques sont supposées équiprobables. Une rencontre au rang i a lieu si la boule tirée à ce rang porte le numéro i. Comme les étiquettes vont de 1 à n, seuls les n premiers rangs peuvent produire une rencontre.

Pour calculer l'absence de rencontre, la formule du crible additionne puis soustrait les intersections de ces n événements. En notant (nr)_k le produit décroissant nr(nr − 1)…(nr − k + 1), avec un produit vide égal à 1 pour k = 0, on obtient :

La probabilité d'au moins une rencontre est le complément à 1. Lorsque r = 1, chaque tirage correspond à une permutation de n objets et l'absence de point fixe est un dérangement. La comparaison de deux jeux de cartes distinctes relève de ce cas. Pour r fixé, quand n augmente, les termes alternés de la formule du crible se rapprochent de ceux du développement de 1/e : c'est pourquoi la probabilité d'absence tend vers 1/e. Cette question, aussi appelée problème des chapeaux, a été étudiée sous diverses formes par Montmort, De Moivre, Nicolas Bernoulli, Laplace, Bertrand, Andrade et Catalan.

Quatre personnes reprennent au hasard les quatre chapeaux distincts. Toutes les attributions sont supposées équiprobables. Nous calculons la probabilité qu'au moins une personne récupère son chapeau.

Données.
Nombre de personnes et de chapeaux : n = 4.
Multiplicité de chaque étiquette : r = 1.
Nombre total d'attributions : 4! = 24.

Étape 1. La formule du crible compte les attributions sans rencontre :

On part des 24 attributions, on retire celles où une personne donnée retrouve son chapeau, puis on rajoute celles où deux personnes le retrouvent, car elles ont été retirées deux fois. Les termes suivants poursuivent cette alternance pour trois puis quatre rencontres.

Étape 2. Il reste donc 24 − 9 = 15 attributions avec au moins une rencontre. La probabilité cherchée vaut 15/24 = 5/8, soit 62,5 %.

Contrôle. La probabilité contraire vaut 9/24 = 3/8. La somme 5/8 + 3/8 = 1 confirme que les 24 attributions sont réparties sans oubli entre les deux cas.

Pour reconnaître un problème de rencontres, on repère des objets placés au hasard et une position de référence propre à chacun. Si la question porte sur l'égalité entre l'étiquette et son rang, le modèle convient ; si elle porte seulement sur deux étiquettes égales entre elles, il faut choisir un autre modèle.

Pour un petit nombre d'objets distincts, on compte exactement les dérangements par la formule du crible, puis on prend le complément pour obtenir au moins une rencontre. Une énumération directe reste un bon contrôle lorsque toutes les permutations tiennent dans une courte liste.

Pour un grand nombre d'objets et une multiplicité r fixée, 1/e donne une approximation de la probabilité d'absence. Il faut employer 1 − 1/e si l'on cherche au contraire la présence d'au moins une rencontre. Une simulation est utile pour contrôler une variante, mais elle ne remplace pas la valeur exacte lorsqu'elle est accessible.

Problème des rencontres et problème des anniversaires. Dans le premier, chaque objet est comparé à un rang fixé qui lui correspond. Dans le second, on cherche si deux personnes partagent une même date, sans rang de référence. Deux chapeaux identiques entre eux ne constituent donc pas une rencontre au sens étudié ici.

Problème des rencontres et dérangement. Le problème est une question de probabilité sur toutes les permutations. Un dérangement est une issue particulière, sans aucun point fixe. Avec quatre chapeaux, les 9 dérangements forment le cas contraire des 15 attributions comportant une rencontre.

Les rencontres ne sont pas indépendantes. Fixer un objet à sa place modifie les choix restants. Multiplier naïvement les probabilités d'absence rang par rang donne donc un résultat faux ; la formule du crible tient compte des intersections.

Le cas r > 1 n'est pas une permutation ordinaire. Plusieurs boules portent alors la même étiquette. Il faut utiliser la formule avec la multiplicité r, et non compter les seuls dérangements de nr objets comme si chaque rang possédait une étiquette correspondante.

Les rangs au-delà de n ne peuvent pas rencontrer leur numéro. L'urne contient des étiquettes de 1 à n, même si elle contient m = nr boules. Au rang n + 1, aucune boule ne porte le numéro n + 1.

La limite 1/e concerne l'absence. Pour r fixé et n grand, la probabilité d'aucune rencontre approche 1/e, tandis que celle d'au moins une rencontre approche 1 − 1/e. Pour n = 4 et r = 1, les valeurs exactes restent 3/8 et 5/8.

Le Dérangement isole le cas sans point fixe et donne le vocabulaire combinatoire associé au problème classique des chapeaux.

La formule du crible de Poincaré détaille le mécanisme d'inclusion-exclusion utilisé pour réunir les événements de rencontre sans les compter plusieurs fois.

Le nombre e éclaire la constante dont l'inverse apparaît comme limite de la probabilité d'absence de rencontre.