Annuler
connectez vous
probabilités en post-bac
- Un best-of d'exos de probabilités (après le bac)
- Équations différentielles : un Cours complet avec des exemples
- Généralités sur les matrices, applications linéaires, changement de base, rang d'une matrice - supérieur
- Ensemble et application Partie II
- Espaces vectoriels et Applications linéaires - supérieur
- Décomposition des matrices en blocs, exponentielle de matrices - supérieur
Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Maths sup ProbabilitésTopics traitant de probabilités [tout]Lister tous les topics de mathématiques
Niveau Maths sup
graphe et chaines de markov
Posté par athesa
Voilà l'autre jour on a recu un dm ne comportant que 2 questions. Et je continue à le lire sans y comprendre grand chose. On nous donne une inégalité à trouver avec 3 constantes et franchement j'arrive pas à voir ou commencer ni que faire d'ailleurs vu qu'on vient a peine de commencer le chapitre.
Il faut montrer que si Nk est le nombre de chemins de longueur k reliant le sommet 1 à lui même dans le graphe, alors on a
6k(1+C/3k)
Nk6k(1+C,/3k)
quelqu'un aurait une piste?
bon apres la 2e question est trouver alpha mais j'imagine qu'il faut avoir compris comment faire la 1 avant de trouver sinon c'est pas possible
Bonjour,
Le nombre de chemin de longueur k entre le sommet 1 et lui-même est donné par la matrice puissance où
est la matrice associée au graphe.
La matrice A est alors:
Je précise, c'est le coefficient (coefficient de la première ligne et première colonne de
) qui donne le nombre de chemins de longueur k entre le sommet 1 et lui-même.
Après quelques essais machine, je trouve:
Ceci dit, a-t-on une idée de ce que représentent les constantes ,
et
?
non il nous a juste mis que c'était des réels.
mais Ak c'est la matrice A a la puissance k? qu'est ce qu'elle représente?
Parce que ce coeff a1,1 dans la matrice A il représente bien le chemin qui va de 1 vers 1 mais seuelemnt en passant par lui meme.
Mais tous ces chemins de longueur k ca peut etre aussi genre de 1 vers 2 qui va vers 4 et qui retourne sur 1?
est le coefficient de la matrice
associée au graphe, mais
est le coefficient de
.
effectivement (coefficient 1ère ligne et 1ère colonne de
) donne le nombre de chemins qui partent de 1 et arrivent à 1 quels que soient les sommets visités entre les deux.
donc en gros maintenant faut que j'essaie d'encadrer a1,1k
ce qui est quand même bizarre c'est qu'il faut trouver 3 constantes dans une meme inégalité...
Je suis d'accord avec toi, c'est surtout le \alpha qui est pénible: je ne vois pas trop son statut.
Pour les nombres 3 et 6 des inégalités, je dirai qu'ils viennent respectivement du nombre de sommets adjacents au sommet 1 et du nombre de chemins qui partent de 1 (ou qui arrivent en 1).