Du paysage que decouvre un ivrogne...

[invite4c324090]

Bonjour, voilà une question sur laquelle je suis totalement coincé:
Soit un graphe G à n sommet. Soit une marche aléatoire M.
Quelle est l'espérance du nombre d'itérations de M nécessaire pour avoir atteint k*n sommets distincts? où 0<k<1 (euh...ça fai peur comme ça T_T)

En d'autre terme, pour k=3/4 par exemple,
combien de fois faut-il se deplacer au hasard sur notre graphe pour avoir atteint au moins une fois les 3/4 des sommets du graphe?

L'expérience avec maple montre que pour des graphes de tailles raisonnables (qui ne font pas planter maple en fait...) on obtention quelquechose de type E=a.n.

Quelqu'un voit-il comment le montrer? et si possible comment calculer ou au moins approcher a en fonction de k?

Merci
-----

[taladris]

Salut,

cela dépend beaucoup des propriétés de ton graphes (connexité notamment) et de ta matrice de transition (présence d'états récurrents,...).
Cherche des cours sur les chaînes de Markov, il y a aura sûrement ton bonheur (mes souvenirs sont un peu flous)

Cordialement

[invite4c324090]

Graphe connexe, j'ai oublié de préciser. Merci je vais chercher dans ton sens. Le problème étant que j'aurai besoin de travailler sur un graphe quelconque(mais avec toute les propriétés sympathique qu'on voudrait lui mettre)il faudrait que l'esperance prenne aussi en compte la forme du graphe...

[Romain-des-Bois]

Bonjour,

il me semble qu'une marche aléatoire (sur un graphe par exemple) est un cas très particulier de chaine de Markov :

Si à l'instant je me trouve sur le sommet qui mène par des arêtes à sommets alors je me déplace sur un de ces sommets avec la loi uniforme :

où est la position sur le graphe à l'instant .

En travaillant avec une chaine de Markov quelconque (et en plus un graphe quelconque), je ne sais pas si tu peux dire grand chose...

Bon courage

[A voir en vidéo sur Futura]

[Garf]

L'expérience avec maple montre que pour des graphes de tailles raisonnables (qui ne font pas planter maple en fait...) on obtention quelquechose de type E=a.n.

Quelqu'un voit-il comment le montrer? et si possible comment calculer ou au moins approcher a en fonction de k?

Nah, ça ne marche pas. Je prends deux exemples pour montrer que ce temps dépend pas mal de la géométrie du graphe.


I-Graphe complet

Deux sommets distincts sont reliés par une unique arête. Par simplicité (même si je doute que cela change grand chose au résultat), on va aussi supposer que pour chaque sommet, il existe une unique arête le reliant à lui-même.

La marche aléatoire est donc identique à une suite de variable aléatoire i.i.d., tirées uniformément sur l'ensemble des sommets.

[exercice]
Soit .
L'espérance du temps minimal auquel on a visité sommets est :


[détails à rédiger, rien de méchant]
Asymptotiquement, le temps mis pour visiter sommets distincts, , est donc équivalent à , donc . Si , ce temps est équivalent à .

Dans ce cas, tout ce passe bien pour différent de .


II-Sous-ensembles de

Considérons l'ensemble , avec la structure de graphe naturelle, et une marche aléatoire partant de .
On ne se préoccupe pas de ce qui se passe quand la marche aléatoire arrive en : si elle le fait, elle a visité tous les sites. Basiquement, c'est donc une marche aléatoire sur réfléchie en . La loi du logarithme itéré donne un équivalent asymptotique du supremum courant de ce processus.

Pour , le temps à estimer est tel que et sont équivalent, ce qui donne un temps plutôt de l'ordre de (pas exactement du même ordre de grandeur, mais "pas loin")...


Bref.
Sans information sur la géométrie du graphe, on ne peut pas faire grand chose.

[invite4c324090]

Exacte Garf, sauf que le graphe n'est pas fixé, c'est la que ça se corse^^: je prend plein de graphes aleatoire, je fait plein de marche dessus et je calcule ma moyenne... je ne prend pas un seul graphe sur lequel je fais mes mesures...

[Garf]

Comment sont tirés ces graphes ?

[invite4ef352d8]

"je prend plein de graphes aleatoire" >>> il faut définir tres précisement qu'elle est la loi que tu met sur l'ensemble des graphes (ie comment tu tie tes graphs au hasard...)

[invite986312212]

surtout qu'il faut tirer un graphe connexe. Donc le truc classique des arêtes présentes ou non indépendamment les unes des autes ça doit pas trop le faire.

[invite4c324090]

En fait, maple à une fonction pour ça et j'avoue ne pas m'être demandé comment il faisait...
Essayez:
with(GraphTheory);with(RandomG raghs);
G:=RandomGraph("nbre de sommets","nbre d'arretes",connected);
Le seul defaut c'est qu'il ne génère pas d'arrête d'un sommet sur lui-même mais ça ne me gène pas vraiment...

ps: le pack graph theory y est à partir de maple 11 mais pas maple7. Je ne sais pas à partir de quel version il est disponible.