Récurrence dans l'avion

Oliv84

Bonjour,

Des collègues m'ont soumis un petit problème de proba qui semble élémentaire mais après avoir formalisé et pas mal cherché je n'arrive pas à bien conjecturer la récurrence qui mène à la solution. C'est étrange, ce genre de petit problème amusant peut causer plus de tracas que d'autres ayant l'air plus méchants.
Je pense qu'un problème équivalent a déjà pu faire l'objet d'un fil ici même.

"Un avion contient 100 places numérotées, les 100 passagers ont un billet avec le numéro de leur place. Le premier passager est ivre et ne parvient pas à lire son numéro, il s'assoit donc au hasard. Tous les autres passagers (du second au dernier) entrent (pas simultanément, séquentiellement) et ont le comportement suivant :
- Si la place correspondant à celle du billet est occupée, le passager s'assoit à une autre place au hasard
- Si sa place est bien libre, le passager s'y installe

Quelle est la probabilité que le dernier passager soit assis à sa place ?"


Je peux poster mes réflexions, mais j'ai comme dans l'idée que la solution est déjà sur le forum ou que quelqu'un verra le "truc" qui m'échappe.

Merci à tous.

Oliv

gb

Un petit "truc" : il faut considérer la décomposition en cycles à support disjoints de la permutation de $\{1,2,\ldots,100\}$ induite par le placement des passagers

Oliv84

Bonsoir,

Je suis désolé mais j'ignore absolument ce que sont des "cycles à support disjoints" ...

vg1

Bonjour,
Mon truc c'est de considérer $P(n)$ : la solution du problème avec $n$ passagers. J'arrive à calculer $P(2)$ qui correspond au problème avec 2 places en tout dans l'avion. Puis $P(3)$ en remarquant que j'utilise $P(2)$, $P(4)$ en utilisant $P(3)$ et $P(n)$ par récurrence sur $n$. Je trouve cela plutôt simple mais l'indication de gb me fait douter.

vg1

Je faisais bien de douter, ma solution est fausse.

aléa

Oliv84: il s'agit de représenter la permutation par la famille des orbites (si ces mots te sont plus familiers).

J'ai fini par trouver, grâce à l'indication de gb, mais je dois bien avouer que ça m'a donné du fil à retordre...
Pour ma part, j'ai commencé par caractériser les permutations possibles, puis, pour chaque permutation possible, calculé sa probabilité. Ensuite, il faut encore réfléchir un peu, mais le plus dur est fait.

Remarque: il me semble que cet exercice aurait plus sa place dans une section "combinatoire", si elle existait.

algo0

Si cela intéresse quelqu'un, ce problème a été proposé dans un numéro récent du magazine "Quadrature".
Je ne sais pas si une solution a été publiée depuis.

gb

aléa a écrit:

Remarque: il me semble que cet exercice aurait plus sa place dans une section "combinatoire", si elle existait.

C'est techniquement simple : l'univers des possibles est l'ensemble des permutations de {1,2,...,100} dont une orbite au plus n'est pas réduite à un point, les cas favorables étant les telles permutations pour lesquelles l'orbite de 100 est réduite à un point.

Et effectivement, c'est la partie "combinatoire" du dénombrement qui est la plus délicate.

aléa

Salut gb,

Sans doute n'avons nous pas tout à fait la même modélisation.
J'ai fait la modélisation suivante: le premier qui entre dans l'avion est appelé 1, le 2e est appelé 2, etc... On note $\sigma(x)$ le numéro du propriétaire légitime de la place occupée par l'individu $x$.
Ainsi, pour moi, les $\sigma$ possibles sont celles où il y a au plus une orbite pas réduite à un point: celle de 1, avec la condition supplémentaire que l'orbite de 1 est croissante: Ainsi (1 3 7) est possible, mais pas (1 3 2).

gb

Bonjour aléa,

Nous avons en fait la même modélisation...

Tout d'abord, j'ai bien précisé que les cas favorables sont obtenus pour l'orbite de 100 réduite à un point, mais je n'ai malheureusement pas dit que l'orbite non réduite à un point était nécessairement celle de 1, tellement cela me paraissait évident.

D'autre part, je me suis mal exprimé dans mon dernier message parce que j'ai repris ton terme d'orbite, alors que j'avais en tête le support, dont je parlais dans mon indication initiale. Un cas favorable est parfaitement défini par le support de l'orbite de 1, c'est-à-dire par une partie de $\{2,3,\ldots,100\}$. Pour les cas favorables, ce support doit être une partie de $\{2,3,\ldots,99\}$, d'où la probabilité de $\dfrac{1}{2}$.

aléa

Nous sommes d'accord !

egoroff

Salut tout le monde,

Bravo à aléa et gb pour cette modélisation astucieuse. J'avais essayé quelquechose à base de chaînes de Markov mais sans trop de succès. Bon j'ai quand même une petite objection : est-il vraiment évident que les cas sont équiprobables ?

aléa

Non, les cas ne sont pas équiprobables, mais il y a une bijection entre les cas favorables et défavorables qui envoie chaque élément sur un élément de même probabilité.

Oliv84

J'avais soigneusement évité toute approche combinatoire pour privilégier un raisonnement sans doute un peu dans l'esprit de ce à quoi a du penser Egoroff....enfin je présme. Je vais continuer à réfléchir à mon approche bien que moins subtile que ce qui a été exposé par gb et aléa, je pense qu'on peut y arriver différemment. Je posterai une solution alternative si j'aboutis à qqch.

(Si ce petit problème a donné du fil a retordre à aléa, je me sens un peu décomplexé!)

Merci en tout cas

Oliv

jacquot

aléa a écrit:

Non, les cas ne sont pas équiprobables, mais il y a une bijection entre les cas favorables et défavorables qui envoie chaque élément sur un élément de même probabilité.

Bonsoir,

C'est cette dernière remarque qui m'a permis de comprendre la solution.
Voici une illustration de cette bijection qui peut aider.
J'ai pris le cas d'un avion à 5 places: on peut commencer à entrevoir comment ça marche.
Cases jaunes : passagers s'asseyant au hasard, en noir les passagers qui trouvent leur place libre.


A droite, le passager n°5 n'a plus le choix: la seule place qui lui reste est celle du N°1, bien sûr: si celle ci avait été occupée précédemment, le dérangement aurait cessé!

gb

A gauche, le passager n°5 n'a pas plus de choix : la seule place qui reste est la sienne.

Heuristiquement, cela peut aider à comprendre cette probabilité de $0,5$ : le dernier passager est contraint d'occuper la dernière place ligne qui est la sienne, ou celle du passager numéro 1.

Lorsque je propose de caractériser chaque permutation par le support de l'orbite de 1, la seule éventuellement non réduite à un point, donc par une partie de $\{2,3,...,n\}$, il faut voir qu'un cas favorable, caractérisé par $A$ avec $n\notin A$, et le cas défavorable $A\cup\{n\}$ ont la même probabilité.

Serge13790

Bonjour,
Je déterre ce sujet qui me parait très intéressant.

@aléa a a écrit :
« Pour ma part, j'ai commencé par caractériser les permutations possibles, puis, pour chaque permutation possible, calculé sa probabilité. Ensuite, il faut encore réfléchir un peu, mais le plus dur est fait. »

Pouvez-vous préciser l'ensemble des permutations possibles ainsi que la probabilité attachée à chacune d'elle ?
Pouvez-vous donner la suite de vos réflexions ?

@gb a écrit :
« C'est techniquement simple : l'univers des possibles est l'ensemble des permutations de {1,2,...,100} dont une orbite au plus n'est pas réduite à un point, les cas favorables étant les telles permutations pour lesquelles l'orbite de 100 est réduite à un point.
Et effectivement, c'est la partie "combinatoire" du dénombrement qui est la plus délicate. »

Pouvez vous préciser la partie "combinatoire" du dénombrement  ?

Merci d'avance.
Cordialement.