denombrement étonnant

[invite636fa06b]

Bonsoir,

Je n'ai pas trouvé ce problème assez ancien sur le forum, aussi je vous le propose.

Six personnes portant chacune un chapeau se rendent au restaurant et déposent leurs couvre-chefs avant de déjeuner. Après un repas bien arrosé, elles reprennent chacun un chapeau au hasard car elles ne sont pas en état de choisir.
1 Quelle est la probabilité qu'aucune ne reprenne son propre chapeau.
2 généralisation à n personnes et n chapeaux et limite de la probabilité.
Il est intéressant d'essayer de répondre à la question finale avant de faire les calculs, on risque d'être surpris.
-----

[shokin]

Pas si simple, je trouve une "méthode" pour calculer n en fonction de (n-1) et ainsi je peux trouver chaque nombre.

Mais si n est très grand, ça risque de durer.

Voici comment :

Pour 1, 2, 3 chapeaux, je fais sans formule (par énumération).

Soit p(x;y) la probabilité de trouver x chapeaux justes parmi y chapeaux.

Alors p(x;y) = [y!/[(x+1)!(y-x-1)!] * p(0;y-x) ]/y! pour x naturel non nul.

Et pour calculer p(x;y) avec x nul :

p(0;y) = 1 - Somme des p(i;y), i allant de 1 à y. Je n'ai pas trouvé d'autres trucs.

Je ne vois pas de formule a priori.

Doit pourtant y avoir un truc.

Si j'appelle p(x;y) la probabilité de retrouver x chapeaux justes parmi y chapeaux, je trouve :

p(a;a) = 1/a! pour tout a naturel non nul
p(a-1;a) = 0/a! pour tout a naturel non nul
p(a-2;a) = [n(n-1)/2]/a! pour tout a naturel non nul

Shokin

[invite636fa06b]

Pas si simple, je trouve une "méthode" pour calculer n en fonction de (n-1) et ainsi je peux trouver chaque nombre.
Mais si n est très grand, ça risque de durer.
Shokin

Je n'ai pas encore bien compris tes formules mais il y a effectivement plus simple.
Il faut établir une récurrence sur le nombre de personnes en posant par exemple X(n) = nombre de permutations de n objets tels qu'aucun ne retrouve sa place initiale et ensuite essayer d'établir X(n+1) en fonction de X(n), X(n-1)....
Le raisonnement n'est pas évident mais les formules sont simples et avec un peu d'astuce, on peut faire les calculs avec les doigts d'une seule main.

Au fait, à ton avis, intuitivement, vers quoi va tendre la proba quand n grandit ?

[GuYem]

Intuitivement évidemment on a l'impression que la proba va tendre vers 0 quand n grandit : plus ya de monde, plus ya du bordel, moins les gens vont retrouver leur chapeau.

Cependant mon petit doigt me dit que ce sera pas 0 ... à suivre

[A voir en vidéo sur Futura]

[invite636fa06b]

p(x;y) = [y!/[(x+1)!(y-x-1)!] * p(0;y-x) ]/y! pour x naturel non nul.
Shokin

Bonjour,
Je dirais plutôt p(x;y) = [y!/[(x)!(y-x)!] * p(0;y-x) * (y-x)! ]/y!
Cela se simplifie beaucoup : p(x;y) = p(0;y-x)/(x)!
Tu as introduit un "+1" étrange et sans doute confondu proba et nombre de cas.
Je pense qu'on peut y arriver avec ta démarche mais je n'ai pas encore réussi...

[GuYem]

Avec ton indication Zinia : pour X(n) je, trouve la relation de récurrence :
X(n) = (n-1)( X(n-1) + X(n-2) ) en distinguant deux cas :
-l'image de 1, appelons la i est a nouveau envoyée sur 1 apr la permutation, cela donne le terme (n-1)X(n-2)
-i n'est pas envoyé sur 1, cela donne le terme (n-1)X(n-1)

Cette relation à l'air de marcher au moins pour n=4, puisqu'on trouve dans S_4 9 permutations qui ne fixent personne : les 6 4-cycles et les 3 doubles permutations ; et que 9 = 3*(2+1) = (n-1)(X(3) + X(2)).

Avec cette formule on trouve X(6) = 265, et donc la proba cherchée à la première question serait 256/6! = 0.24 si je sais me servir de la calculatrice de windows.

Reste à trouver une expression fermée de X(n) en fonction de n, ou peut-être juste de trouver la limite de X(n)/n! pour voir apparaitre la chose étrange dont tu parles.

[invite636fa06b]

Avec cette formule on trouve X(6) = 265, et donc la proba cherchée à la première question serait 256/6! = 0.24 si je sais me servir de la calculatrice de windows.

Bravo tout a tout juste sauf qu'il faudrait apprendre à te servir d'une calculatrice 265/6! = 0.368

[GuYem]

lolo, les calculatrices, ça sert à rien.

Par contre pour la suite je suis un peu embété puisque je ne parviens pas à déduire ni une expression de X(n) en fonction de n, ni la limite de X(n)/n!
Si je divise ma relation par n! et que je fais n->oo, ça me donne, en appelant L la limite cherchée ; L = L, super !

[invite636fa06b]

essaie la suite u(n)=P(n)-P(n-1) avec P(n)=X(n)/n!

[GuYem]

Rhaa, moi qui croyais que ça servait jamais de regarder des séries télescopiques ! Va falloir changer d'avis.

[GuYem]

Alors après indication, on trouve une relation simple sur u_n qui est :
u_n = -1/n * u_{n-1}
Vu que u(2) = 1/2 on déduit que u_n = (1-)^n/n! et que la somme des u_n de 2 plus l'infini fait 1/e.
Comme ça se bidouille bien pour les premiers termes et que p(1)=0, cette limite 1/e est également la limite de la proba recherchée quand n tends vers +oo.

C'est réconfortant puisque 1/e = 0.36787 et on voit que pour n=6, on est à 0.38, ce qui n'est pas loin du tout. Cela confirme le fait que la série converge trés vite vers sa limite.

[invite6b1e2c2e]

Alors après indication, on trouve une relation simple sur u_n qui est :
u_n = -1/n * u_{n-1}
Vu que u(2) = 1/2 on déduit que u_n = (1-)^n/n! et que la somme des u_n de 2 plus l'infini fait 1/e.
Comme ça se bidouille bien pour les premiers termes et que p(1)=0, cette limite 1/e est également la limite de la proba recherchée quand n tends vers +oo.

C'est réconfortant puisque 1/e = 0.36787 et on voit que pour n=6, on est à 0.38, ce qui n'est pas loin du tout. Cela confirme le fait que la série converge trés vite vers sa limite.

Très très joli

__
rvz, qui avait essayé d'attaquer le problème initial, mais sans succès...

[GuYem]

Très très joli

__
rvz, qui avait essayé d'attaquer le problème initial, mais sans succès...

C'est vrai que ça fait toujours bizarre de voir sortir des e dans des exos de probas comme celui-là.
Si ça t'intéresse je t'invite à regarder ce fil : http://forums.futura-sciences.com/thread43917.html
où le brave e sort aussi d'on ne sait où ; les probas, c'est beaaaau.

[invite636fa06b]

Bravo GuYem
Je pense que la difficulté majeure était d'établir la relation de récurrence.
En regardant le fil que tu cites, je me suis demandé quelle était l'espérance du nombre K d'objets inchangés dans une permutation aléatoire (uniforme) de n objets.
En utilisant la démarche de shokin, je suis arrivé à 1, ce qui semble faible mais va savoir !

[invite636fa06b]

Bonjour,

Je reviens à la charge : l'espérance du nombre d'objets inchangés dans une permutation est effectivement égale à un et ce quel que soit le nombre d'objets permutés de 1 à l'infini.
En outre à partir d'un nombre assez petit, la variable aléatoire K= nombre d'objets inchangés suit presque exactement une loi de Poisson de paramètre .
Par exemple la proba d'avoir trois objets non modifiés est égale à 6,2 % pour n=3,
6,11 % pour n=5,
6,131 % pour n=7
6,1313 % (1/6e) pour n= 12 843
Qui aurait une explication logique à cette belle convergence ?

[GuYem]

Euh j'avoue que la loi de Poisson je connais pas trop !
Mais il me semble qu'on peut approximer des B(n,p) par des poissons sous certaines conditions sur n et p non ?

Comment as-tu fait pour trouver que l'espérance en question est 1 ?

[invite636fa06b]

Comment as-tu fait pour trouver que l'espérance en question est 1 ?

Désolé, c'est d'une simplicité decevante :
Comme indiqué, je pars de la démarche de shokin en posant
p(k,n) = probabilité pour qu'une permutation de n objets en laisse k inchangés.
On a possibilités de choisir les k inchangés et pour les autres il existe X(n-k) avec les notations précédentes.
On établit donc facilement que p(k,n)= (i)
Donc E(K) =
en réutilisant la relation (i) : E(K)= = 1
Concernant Poisson, une chose est certaine, on n'a pas de loi binomiale là dedans.

[shokin]

A plusieurs nous y arrivons.

Arg ! ces probabilités !

Shokin

[invite986312212]

voir:
http://en.wikipedia.org/wiki/Rencontres_number

[invite636fa06b]

voir:
http://en.wikipedia.org/wiki/Rencontres_number

Oui, effectivement en cherchant "problème des rencontres" sur Google, on trouve de tout avec là dedans les résultats énoncés mais pas de justification de la convergence vers Poisson (à moins de j'ai raté quelque chose ?)

[invite6de5f0ac]

Bonsoir,

Apparemment, tout le monde a trouvé le Wiki sur le nombre de "dérangements" (permutations sans point fixe).

Donc j'arrive trop tard... mais c'est vrai que le résultat est (un peu) surprenant. En fait, plus il y a de monde, moins il y a de chances que le bordel soit vraiment complet, on peut toujoursdse dire que sur le tas ce serait vraiment pas de bol qu'il n'y en ait pas au moins un qui retrouve son chapeau...

-- françois

[invite986312212]

Oui, effectivement en cherchant "problème des rencontres" sur Google, on trouve de tout avec là dedans les résultats énoncés mais pas de justification de la convergence vers Poisson (à moins de j'ai raté quelque chose ?)

je ne sais pas quel genre de justification tu voudrais, mais la loi de Poisson est la loi limite dans pas mal de situations. C'est une loi "infiniment divisible" c'est-à-dire que pour tout entier n, il existe une distribution dont elle est la n-ième puissance de convolution.

[invite986312212]

j'essaie de répondre à la question de Zinia: quel est la raison profonde de la convergence vers la loi de Poisson, et je ne trouve rien d'intelligent à dire. Je remarque juste que si les personnes choisissaient leurs chapeaux au hasard et indépendamment, alors le nombre de personnes retrouvant leur chapeau (ou le nombre de chapeaux retrouvant leur tête) suivrait une loi binomiale de paramètres n et 1/n, et il est bien connu que quand n croît, ça converge vers une loi de Poisson de moyenne 1. Mais les choix ne sont pas indépendants (tirage avec remise) et donc il doit se faire que quand n croît, les tirages "deviennent de moins en moins dépendants". Ca me fait penser à ce qu'on appelle en proba les "conditions de mélange" pour les processus aléatoires (mixing processes) mais comme cette notion dépend de l'ordre de l'ensemble des indices, je ne vois pas comment l'étendre au cas des chapeaux (qui ne sont pas numérotés).

par contre, j'ai déniché un truc intéressant: un autre cas de proba qui vaut 1/e. Il s'agit du fameux "problème de la secrétaire": un employeur veut embaucher une secrétaire (ou un, ne soyons pas sexiste), et il reçoit
les candidat(e)s un(e) par un(e). S'il laisse passer un candidat sans le choisir, il ne pourra plus le revoir (ce problème date d'une période de plein-emploi...). Les candidats sont en nombre fini. Le problème est de trouver la stratégie qui maximise la probabilité de choisir le meilleur candidat. Je vous laisse essayer de résoudre le problème, mais la probabilité en question, si on suit la stratégie optimale, n'est autre que 1/e.

[invite35452583]

par contre, j'ai déniché un truc intéressant: un autre cas de proba qui vaut 1/e. Il s'agit du fameux "problème de la secrétaire": un employeur veut embaucher une secrétaire (ou un, ne soyons pas sexiste), et il reçoit
les candidat(e)s un(e) par un(e). S'il laisse passer un candidat sans le choisir, il ne pourra plus le revoir (ce problème date d'une période de plein-emploi...). Les candidats sont en nombre fini. Le problème est de trouver la stratégie qui maximise la probabilité de choisir le meilleur candidat. Je vous laisse essayer de résoudre le problème, mais la probabilité en question, si on suit la stratégie optimale, n'est autre que 1/e.

Bonjour,
ce que j'ai mis en gras, ce n'est pas plutôt la limite de la probabilité quand n tend vers l'infini?
Ceci dit je ne sais le montrer que partiellement (je connais la stratégie qui donne ce résultat et c'est l'optimum en empruntant une stratégie du même type)
Je ne donne pas la réponse je connaissais déjà (je laisse chercher les intéressés) mais je suis intéressé par ce qui me manque : la stratégie que je connais est bien l'optimale de "manière absolue", pas mon domaine ces problèmes là.

Autre apparition de e (et non 1/e), on coupe un bâton d'un mètre en deux on en jette une partie on garde l'autre. On continue et on met bout à bout les morceaux conservés. En moyenne, au bout de combien de coups le tronçon ainsi constitué atteint ou dépasse un mètre?
"Preuve rapide" : c'est clairement plus grand que 2, on sent que c'est moins que 3, or il n'y a qu'un nombre intéressant entre 2 et 3, c'est e Il ya évidemment une preuve sérieuse (pas très difficile)

[invite986312212]

oui, ça doit être la limite (si n=1 ce n'est pas 1/e). Je vais chercher pour les autres stratégies, je crois qu'il y a une abondante littérature sur le sujet.

[invite35452583]

Précision : le en tête de mon précédent post est une erreur de manip (je viens seulement de le voir).
ambrosio, j'espère que tu ne l'as pas mal pris, je désirais seulement faire une précision, désolé.