Promenade aléatoire sur un polygone

[tournesol]

Bonsoir à tous
On met un petit cheval sur l'un des sommets d'un n-gone.
A chaque étape on choisit de façon équiprobable l'un des deux sommets qui lui sont adjacents puis on y place le petit cheval.
La partie s'arette lorsque tout les sommets ont été parcourus.
On trouve par simulation que le nombre moyen d'étapes d'une partie est n(n-1)/2
Je n'arrive pas à le démontrer sauf pour n=3 .
Si quelqu'un a une idée.
Par avance Merci

[tournesol]

Je viens de trouver les états intermédiaires pour un calcul direct lorsque n est donné.
Ça a fonctionné pour n=4 , mais c'est trop limité et le cas général n'est pas démontré.
Donc à vous si vous savez.

[lyceen95]

Je verrais bien une chaine de Markov. Chaque position est définie par :
- le nombre de sommets déjà visités.
- la position courante par rapport aux sommets déjà visités.

Par exemple, si j'ai actuellement visité 5 sommets et que je suis à la position 0 (une des 2 extrémités du groupe de 5 points visités), on peut aller vers (6,0), ou vers (5,1)
Si on est en (3,1), on va forcément vers (3,0), parce que je considère que l'extrémité droite ou l'extrémité gauche d'un segment, c'est pareil.
Ici, je stocke les états de façon peut-être trop optimisée.

Soyens moins radin ... Si on est en (3,1), on peut aller en (3,0) (=extrémité droite d'un segment de longueur 3) ou en (3,2)(=extrémité gauche d'un segment de longueur 3)
Ainsi, on a une matrice de transition de taille n(n-1)/2, avec des 1/2 de part et d'autre de la diagonale.
Plus une ligne avec l'état final, et un 1 sur la diagonale.

Et j'imagine que cette matrice de Markov est connue, et que le temps moyen d'arrêt est de n(n-1)/2 ???

[tournesol]

Merci lyceen95 pour ton éclairage , et bonne nuit.

[GaBuZoMeu]

Bonjour,

Ce problème est intéressant. On peut le traiter de la manière suivante.
Soit et plaçons un poivrot rond comme une queue de pelle en . Comme il se doit, notre poivrot fait un pas à gauche avec probabilité 1/2 ou un pas à droite avec probabilité également 1/2. Notons l'espérance du nombre de pas au bout duquel le poivrot sort pour la première fois de .
1°) Établir le système des équations linéaires dont est la solution.
2°) Montrer que l'unique solution de ce système est donnée par pour .
3°) En déduire que la réponse au problème de tournesol est bien .

[tournesol]

Merci beaucoup
Je vais faire cela et te répondre.

[tournesol]

Bonjour GaBuZoMeu
Les l équations:
et
Pour i appartenant à [3;l] ,
Les déterminants des matrices associées vérifient
équation caractéristique :
Forme des :
On obtient facilement et donc
est donc non nul , Cramer, etc .
Il suffit donc de vérifier la solution que tu proposes:
et
Pour les l-2 autres, on a sous une forme générale:
Il me reste à utiliser ce résultat pour passer de la ligne ouverte à la ligne fermée...

[GaBuZoMeu]

Pour vérifier l'unicité de la solution, on peut aussi montrer que le système homogène associé n'a que la solution nulle. Ce système linéaire homogène peut être vu comme disant que la température à une place donnée est la moyenne des températures aux deux places adjacentes, en mettant la température 0 à la place 0 et à la place . S'il y a une place où la température est non nulle, alors il y a une place où la valeur absolue de cette température est maximale avec à côté une place où cette valeur absolue est strictement plus petite : absurde.
Le passage au polygone se fait sans difficulté en considérant l'ensemble des sommets déjà visités par le poivrot (à l'instant zéro, réduit à son point de départ).

[tournesol]

Je n'ai pas encore réfléchi au passage au polygone.
J'ai bien aimé ton argumentation pour l'unicité mais il n'est pas utile de raisonner par l'absurde.
Soit k dans [1;l] tel que est de valeur absolue maximale;
On a alors
Il est alors facile de montrer que tous les sont égaux et donc en particulier à .

[GaBuZoMeu]

C'est vrai.

[tournesol]

Bonjour GaBuZoMeu ,
J'ai compris ton idée: visiter l points , c'est en visiter l-1 en étant situé sur un des points extrêmes , puis sortir de la ligne ouverte qui contient ces l-1 points . On a donc avec des notations évidentes :
et comme , on arrive rapidement à
Mais la rédaction rigoureuse me parait délicate et je dois y réfléchir.
Par exemple , pourquoi les espérances de "visiter l-1 points" et "sortir de la ligne ouverte qui contient ces l-1 point" s'ajoutent-elles ?
Et ce n'est qu'un exemple.

[GaBuZoMeu]

Par exemple , pourquoi les espérances de "visiter l-1 points" et "sortir de la ligne ouverte qui contient ces l-1 point" s'ajoutent-elles ?

C'est tout simplement l'additivité de l'espérance : l'espérance d'une somme de variables aléatoires est la somme de leurs espérances;

[tournesol]

OK mais il faut que je définisse clairement ces variables aléatoires.
Je te recontacterai lorsque j'aurai rédigé cet exo.
Merci à toi.