[PROBA] Graph : problème loi géométrique

[DrCooper]

Bonjour,
Je bloque sur la compréhension d'un résultat sur un problème de probabilité et j'aurai aimé que quelqu'un m'éclair si possible

Je dispose de deux graphs de N noeuds chacun. Un graph de noeuds rouge et un graph de noeuds bleu. La probabilité qu'un lien se crée entre deux noeuds de même couleur est p (épreuve de Bernoulli) et la probabilité qu'un lien se crée entre deux noeuds de couleurs différentes c'est q (encore une épreuve de Bernoulli). On sait que p >> q. Attention : q =/= 1-p

Je pars d'un noeud rouge, je fais une marche aléatoire dans mon graph, je cherche à savoir au bout de combien de "saut" j'obtiens un lien avec un noeud bleu. On a donc une loi géométrique avec une succession d'épreuves de Bernoulli.

Je cherche donc à calculer 1 /P(bleu) pour avoir l'espérance. Question : Qu'est-ce que P(bleu) ? Visiblement ce n'est pas q. Et là je coince.

Merci pour votre aide

[GaBuZoMeu]

Pas super clair. Je dirais même complètement obscur pour moi.
Quel lien entre la marche aléatoire et les liens qui se créent avec une probabilité p ou q ???

Peux tu reformuler ton problème en faisant un effort de clarté ? Merci !

[lyceen95]

Voici comment je comprend tout ça. Pas sûr du tout que ce soit la bonne interprétation.
On a un nombre qui doit être assez grand. Disons N=100000 par exemple.
On a points rouges et points bleus.
A partir de chaque point rouge, il y a 'potentiellement' un arc qui part vers chacun des points bleus ( donc arcs possibles à partir de chaque point rouge). Mais chacun de ses arcs a une probabilité d'exister.
Idem, à partir de chaque point, il y a 'potentiellement' un arc qui part vers chacun des points de même couleur, donc potentiellement arcs. Mais chacun de ses arcs a une probabilité d'exister.

Donc il y a 'statistiquement' arcs entre 2 points de couleur différentes, et arcs entre 2 points rouges et arcs entre 2 points bleus.

On part d'un point rouge. Et on veut savoir au bout de combien de mouvements on se retrouve pour la première fois sur un point bleu. Et donc, on pourrait supprimer les arcs entre les points bleus, le problème resterait le même.
Si on note le nombre d'arcs parcourus avant d'arriver sur un point bleu pour la 1ère fois, on s'intéresse à la loi de distribution de .

On nous dit que est beaucoup plus grand que[tex] q[/tex ; bonne nouvelle ; si c'était l'inverse, la question aurait moins d'intérêt.

Voilà, j'imagine que c'est la question.

[DrCooper]

Salut,

Merci pour vos réponses. Je vais essayé d'être plus clair. Lycéen est pas loin du compte.
Le problème porte sur la théorie des graphs et la marche aléatoire. La marche aléatoire permet de "découvrir " un graph et d'en tirer ses caractéristiques. La problématique de cette stratégie est de savoir au bout de combien de temps on est capable d'avoir visité tout le graph et c'est là qu'intervient la fameuse méthode Monte Carlo.
l'exercice tourne autour de ces sujets là.

Un graph possède N noeuds N étant très très grand. Nous avons ici 2 graphs : un bleu et un rouge. La probabilité pour qu'il existe un lien entre deux noeuds de même couleur est p et celle pour qu'il existe un lien entre 2 noeuds de couleur différente est q. p étant bien plus grand que q on constate vite qu'il y a beaucoup plus de liens entre même couleur et que notre gros graph (combinaison du bleu et du rouge) présente une fragilité au niveau de ces liaisons inter couleur. Autrement dit c'est là qu'il faudrait attaquer dans le cas d'un réseau de serveurs informatiques par exemple.

Maintenant je déclenche un algorithme de marche aléatoire à partir d'un noeud rouge et je me balade de noeud en noeud. Combien de saut j'ai besoin pour arriver à un lien avec un noeud bleu ?

Lycéen je ne pense pas que la solution vienne du fait de compter les arcs. Je pense plutôt qu'il faut se dire qu'à un noeud rouge donné j'ai la possibilité de visiter N voisins rouge avec une proba p et N voisins bleu avec une proba q. et à chaque nouveau noeud j'ai de nouveau les mêmes choix. les tirages sont indépendants et pour moi c'est bien une loi géométrique.

[DrCooper]

En écrivant mon message j'ai l'impression que la solution m'a sauté aux yeux :

Je démarre ma marche aléatoire à un noeud rouge. A ce moment là je peux visiter (N -1) voisins rouge avec la proba p et (N-1) voisins bleu avec la proba q. donc la proba de visiter un voisin bleu c'est tout simplement :



==>

L'eperance étant l'inverse de cette chose là.

Parfois faut pas chercher trop loin. Qu'en pensez-vous ?

[lyceen95]

Oui , avec un tout petit correctif.
A partir d'un point rouge, il y a N voisins possibles bleu (et pas N-1)
Donc :


Mais c'est sensiblement la même chose car on suppose N très grand.