Chaîne de Markov
229795
30995064
2008-06-25T13:16:31Z
81.194.18.30
/* Exemple: Doudou le hamster */ retablit les probabilites 1/2 a la place de 1/20 (1/20 correspond a la probabilite quand il a dormi, pas "quand il se reveille")
En [[mathématiques]], une '''chaîne de Markov''' est un [[processus stochastique]] possédant la [[propriété markovienne]]. Dans un tel processus, la prédiction du futur à partir du présent ne nécessite pas la connaissance du passé. Elles ont pris le nom de leur découvreur, [[Andrei Markov (mathématicien)|Andrei Markov]].
Une chaîne de Markov en temps discret est une séquence <math>X_1</math>, <math>X_2</math>, <math>X_3</math>, ... de [[variable aléatoire|variables aléatoires]]. L'ensemble de leurs valeurs possibles est appelé l’''espace d'états'', la valeur <math>X_n</math> étant l'état du processus au moment <math>n</math>.
Si la distribution de probabilité conditionnelle de <math>X_{n+1}</math> sur les états passés est une fonction de <math>X_n</math> seul, alors :
: <math> P(X_{n+1}=x\mid X_0, X_1, X_2, \ldots, X_n) = P(X_{n+1}=x\mid X_n). \, </math>
où <math>x</math> est un état quelconque du processus. L'identité ci-dessus identifie la '''probabilité markovienne'''.
[[Andrei Markov (mathématicien)|Andrei Markov]] a publié les premiers résultats de ces processus en [[1906]].
Une généralisation à un espace d'états infini dénombrable a été donnée par [[Andrey Nikolaevich Kolmogorov|Kolmogorov]] en [[1936]].
Les chaînes de Markov sont liées au [[mouvement brownien]] et à l'[[hypothèse ergodique]], deux sujets de [[physique statistique]] qui ont été très importants au début du XXe siècle.
== Propriétés des Chaînes de Markov ==
Une chaîne de Markov est caractérisée par la distribution conditionnelle
: <math> P(X_{n+1}\mid X_n)\, </math>
qui est aussi appelée ''probabilité de transition d'un pas'' du processus.
La probabilité de transition pour ''deux'', ''trois'' pas ou plus se déduit de la probabilité de transition d'un pas, et de la propriété de Markov:
: <math> P(X_{n+2}\mid X_n) = \int P(X_{n+2},X_{n+1}\mid X_n)\,\mathrm dX_{n+1}
= \int P(X_{n+2}\mid X_{n+1}) \, P(X_{n+1}\mid X_n) \, \mathrm dX_{n+1}</math>
De même,
: <math> P(X_{n+3}\mid X_n) = \int P(X_{n+3}\mid X_{n+2}) \int P(X_{n+2}\mid X_{n+1}) \, P(X_{n+1}\mid X_n) \, \mathrm dX_{n+1} \, \mathrm dX_{n+2}</math>
Ces formules se généralisent à un futur arbitrairement lointain <math>n+k</math> en multipliant les probabilités de transition et en intégrant <math>k-1</math> fois.
La [[loi de distribution marginale]] <math>P(X_n)</math> est la loi de distribution des états au temps <math>n</math>. La distribution initiale est <math>P(X_0)</math>. L'évolution du processus après un pas est décrite par
: <math> P(X_{n+1}) = \int P(X_{n+1}\mid X_n)\,P(X_n)\,\mathrm dX_n </math>
Ceci est une version de l'[[équation de Frobenius-Perron]].
Il peut exister une ou plusieurs distributions d'états <math>\pi</math> telles que
:<math> \pi(X) = \int P(X\mid Y)\,\pi(Y)\,\mathrm dY</math>
où <math>Y</math> est un nom arbitraire pour la variable d'intégration.
Une telle distribution <math>\pi</math> est appelée une ''distribution stationnaire''.
Une distribution stationnaire est une [[fonction propre]] de la loi de distribution conditionnelle, associée à la [[Valeur propre (synthèse)|valeur propre]] 1.
Certaines propriétés du processus déterminent s'il existe ou non une distribution stationnaire, et si elle est unique ou non.
* ''Irréductible'' : tout état est accessible à partir de n'importe quel autre état.
* ''Récurrent positif'' : pour chaque état, l'espérance de la durée avant le retour sur cet état est finie.
Quand l'espace des états d'une Chaîne de Markov n'est pas irréductible, il peut être [[partition (mathématiques)|partitionné]] en un ensemble de ''classes communicantes'' irréductibles. Le problème de la classification a son importance dans l'étude mathématique des chaînes de Markov et des [[processus stochastique]]s.
Si une chaîne de Markov est récurrente, alors il existe une distribution stationnaire.
Si une chaîne de Markov est récurrente et irréductible, alors :
* il existe une ''unique'' distribution stationnaire,
* et le processus construit en prenant la distribution stationnaire comme distribution initiale est [[hypothèse ergodique|ergodique]].
Donc, la moyenne d'une fonction <math>f</math> sur les instances de la chaîne de Markov est égale à sa moyenne selon sa distribution stationnaire,
:<math> \lim_{n\rightarrow\infty}\; \frac{1}{n} \; \sum_{k=0}^{n-1} f(X_k)
= \int f(X)\,\pi(X)\,\mathrm dX </math>
C'est vrai en particulier lorsque <math>f</math> est la fonction identité.
La moyenne de la valeur des instances est donc, sur le long terme, égale à l'espérance de la distribution stationnaire.
De plus, cette équivalence sur les moyennes s'applique aussi si <math>f</math> est la [[fonction indicatrice]] d'un sous-ensemble <math>A</math> de l'espace des états.
:<math> \lim_{n\rightarrow\infty}\; \frac{1}{n} \; \sum_{k=0}^{n-1} \chi_A(X_k)
= \int_A \pi(X)\,\mathrm dX = \mu_{\pi}(A) </math>
où <math>\mu_{\pi}</math> est la mesure induite par <math>\pi</math>.
Cela permet d'approximer la distribution stationnaire par un [[histogramme]] d'une séquence particulière.
== Chaînes de Markov à espace d'états discret ==
Si l'espace des états est ''fini'', alors la distribution de probabilité peut être représentée par une [[matrice stochastique]] appelée ''matrice de transition'', dont le <math>(i,j)</math><sup>ème</sup> élément vaut
:<math>P(X_{n+1}=j\mid X_n=i) \,</math>
Si l'espace des états est fini, alors les intégrales pour les probabilités de transition pour <math>k</math> pas deviennent des sommes, qui peuvent être calculées en élevant la matrice de transition à la puissance <math>k</math>.
Si <math>P</math> est la matrice de transition pour 1 pas, alors <math>P^k</math> est la matrice de transition pour <math>k</math> pas.
<math>P</math> étant la matrice de transition, une distribution stationnaire est un vecteur <math>\pi^*</math> qui vérifie l'équation
:<math> \pi^* P= \pi^*\,</math>.
Dans ce cas, la distribution stationnaire <math>\pi^*</math> est un [[Valeur propre (synthèse)|vecteur propre]] de la matrice de transition, associé à la [[Valeur propre (synthèse)|valeur propre]] 1.
Si la matrice de transition <math>P</math> est irréductible et apériodique, alors <math>P^k</math> converge vers une matrice dont chaque ligne est l'unique distribution stationnaire <math>\pi^*</math>, avec
:<math>\lim_{k\rightarrow\infty}\pi P^k=\pi^*</math>,
indépendamment de la distribution initiale <math>\pi</math>. Cela se prouve par le [[théorème de Perron-Frobenius]].
Une matrice de transition dont tous les éléments sont strictement positifs est irréductible et apériodique.
=== Classification des états ===
On dit que <math>i</math> et <math>j</math> communiquent si et seulement s'il existe <math>n_1</math> et <math>n_2</math> tel que <math>P(X_{n_1}=i\mid X_0=j) >0</math> et <math>P(X_{n_2}=j\mid X_0=i) >0</math>. C'est une [[relation d'équivalence]]. On appelle classe, toute classe pour cette relation.
Une classe est dite finale, si elle ne conduit à aucune autre, sinon, elle est dite transitoire.
Soit <math>N_{ij} = \{n/P(X_n=j\mid X_0=i)>0\}</math>. La période d'une classe est définie par <math>\mathrm{pgcd}(N_{ii})</math> (la valeur est la même quel que soit <math>i</math> à l'intérieur d'une même classe). Si la période vaut 1, la classe est dite apériodique.
== Notation ==
Dans les formules qui précèdent, l'élément (<math>i</math>, <math>j</math>) est la probabilité de la transition de <math>i</math> à <math>j</math>. La somme des éléments d'une ligne vaut toujours 1 et la distribution stationnaire est donnée par le vecteur propre gauche de la matrice de transition.
On rencontre parfois des matrices de transition dans lesquelles le terme (<math>i , j</math>) est la probabilité de transition de <math>j</math> vers <math>i</math>, auquel cas la matrice de transition est simplement la [[Matrice (mathématiques)#Définitions|transposée]] de celle décrite ici. La somme des éléments d'une colonne vaut alors 1. De plus, la distribution stationnaire du système est alors donnée par le vecteur propre droit de la matrice de transition, au lieu du vecteur propre gauche.
== Exemple: Doudou le hamster ==
Doudou le hamster paresseux ne connaît que 3 endroits dans sa cage: les copeaux où il dort, la mangeoire où il mange et la roue où il fait de l'exercice. Ses journées sont assez semblables les unes aux autres, et son activité se représente aisément par une chaîne de Markov. Toutes les minutes, il peut soit changer d'activité, soit continuer celle qu'il était en train de faire. L'appellation ''processus sans mémoire'' n'est pas du tout exagérée pour parler de Doudou.
* Quand il dort, il a 9 chances sur 10 de ne pas se réveiller la minute suivante.
* Quand il se réveille, il y a 1 chance sur 2 qu'il aille manger et 1 chance sur 2 qu'il parte faire de l'exercice.
* Le repas ne dure qu'une minute, après il fait autre chose.
* Après avoir mangé, il y a 3 chances sur 10 qu'il parte courir dans sa roue, mais surtout 7 chances sur 10 qu'il retourne dormir.
* Courir est fatigant ; il a donc 80 % de chance de retourner dormir au bout d'une minute. Sinon il continue en oubliant qu'il est déjà un peu fatigué.
=== Diagrammes ===
Les diagrammes peuvent montrer toutes les flèches, chacune représentant une probabilité de transition. Cependant, c'est plus lisible si:
* On ne dessine pas les flèches de probabilité zéro (transition impossible)
* On ne dessine pas les boucles ''(flèche d'un état vers lui-même)''. Cependant elles existent; leur probabilité est sous-entendue car on sait que la somme des probabilités des flèches partant de chaque état doit être égale à 1.
<gallery widths=300 heights=210>
Image:chaine de markov exemple sansboucles 001.png|exemple avec boucles implicites
Image:chaine de markov exemple avecboucles 001.png|exemple avec boucles dessinées
</gallery>
=== Matrice de transition ===
La matrice de transition de ce système est la suivante (les lignes et les colonnes correspondent dans l'ordre aux états ''dormir'', ''manger'', ''courir'') :
: <math> P =\begin{bmatrix}
0.9 & 0.05 & 0.05 \\
0.7 & 0 & 0.3 \\
0.8 & 0 & 0.2 \\
\end{bmatrix}</math>
=== Prévisions ===
Prenons l'hypothèse que Doudou dort lors de la première minute de l'étude.
: <math> \mathbf{x}^{(0)} = \begin{bmatrix}
1 & 0 & 0
\end{bmatrix} </math>
Au bout d'une minute, on peut prédire :
: <math>
\mathbf{x}^{(1)} = \mathbf{x}^{(0)} P =
\begin{bmatrix}
1 & 0 & 0
\end{bmatrix}
\begin{bmatrix}
0.9 & 0.05 & 0.05 \\
0.7 & 0 & 0.3 \\
0.8 & 0 & 0.2 \\
\end{bmatrix}
= \begin{bmatrix}
0.9 & 0.05 & 0.05
\end{bmatrix}
</math>
Ainsi, après une minute, on a 90 % de chances que Doudou dorme encore, 5 % qu'il mange et 5 % qu'il coure.
: <math>
\mathbf{x}^{(2)} = \mathbf{x}^{(1)} P = \mathbf{x}^{(0)} P^2 =
\begin{bmatrix}
1 & 0 & 0
\end{bmatrix}
\begin{bmatrix}
0.9 & 0.05 & 0.05 \\
0.7 & 0 & 0.3 \\
0.8 & 0 & 0.2 \\
\end{bmatrix}^2
= \begin{bmatrix}
0.885 & 0.045 & 0.07
\end{bmatrix}
</math>
Après 2 minutes, il y a 4,5 % de chances que le hamster mange.
De manière générale, pour <math>n</math> minutes
: <math>
\mathbf{x}^{(n)} = \mathbf{x}^{(n-1)} P
</math>
: <math>
\mathbf{x}^{(n)} = \mathbf{x}^{(0)} P^n
</math>
La théorie montre qu'au bout d'un certain temps, la loi de probabilité est indépendante de la loi initiale.
Notons la <math>q</math> :
: <math>
\mathbf{q} = \lim_{n \to \infty} \mathbf{x}^{(n)}
</math>
On obtient la convergence si et seulement si la chaîne est apériodique et irréductible. C'est le cas dans notre exemple, on peut donc écrire :
:<math>
\begin{align}
P & = \begin{bmatrix}
0.9 & 0.05 & 0.05 \\
0.7 & 0 & 0.3 \\
0.8 & 0 & 0.2 \\
\end{bmatrix}
\\
\mathbf{q} P & = \mathbf{q} \qquad \mbox{(} \mathbf{q} \mbox{ est la loi invariante par rapport a } P \mbox{.)}
\\
& = \mathbf{q} I
\\
\mathbf{q} (I - P) & = \mathbf{0}
\\
& = \mathbf{q} \left( \begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{bmatrix}
- \begin{bmatrix}
0.9 & 0.05 & 0.05 \\
0.7 & 0 & 0.3 \\
0.8 & 0 & 0.2 \\
\end{bmatrix} \right)
\\
& = \mathbf{q} \begin{bmatrix}
0.1 & -0.05 & -0.05 \\
-0.7 & 1 & -0.3 \\
-0.8 & 0 & 0.8 \\
\end{bmatrix}
\\
&= \begin{bmatrix}
q_1 & q_2 & q_3
\end{bmatrix}\begin{bmatrix}
0.1 & -0.05 & -0.05 \\
-0.7 & 1 & -0.3 \\
-0.8 & 0 & 0.8 \\
\end{bmatrix}
\\
&=
\begin{bmatrix}
0 & 0 & 0
\end{bmatrix}
\end{align}
</math>
Sachant que <math>q_1 + q_2 + q_3 = 1</math>, on obtient :
:<math>\begin{bmatrix}
q_1 & q_2 & q_3
\end{bmatrix}
= \begin{bmatrix}
0.884 & 0.0442 & 0.0718
\end{bmatrix}
</math>
Doudou passe 88,4 % de son temps à dormir !
== Illustration de l'impact du modèle ==
L'exemple qui suit a pour but de montrer l'importance de la modélisation du système. Une bonne modélisation permet de répondre à des questions complexes avec des calculs simples.
On étudie une civilisation (fictive) constituée de plusieurs classes sociales, et
dans laquelle les individus peuvent passer d'une classe à l'autre. Chaque étape représentera un an.
On considérera une lignée plutôt qu'un individu, pour éviter d'obtenir des citoyens bicentenaires.
Les différents statuts sociaux sont au nombre de 4 :
* Esclave
* Libre
* Citoyen
* Haut-fonctionnaire
Dans cette société :
Les esclaves peuvent rester esclaves ou bien devenir des hommes libres (en achetant leur liberté ou en étant
affranchis généreusement par leur maître).
Les hommes libres peuvent rester libres ou bien vendre leur liberté (pour payer leurs dettes, etc.) ou encore
devenir citoyens (là encore par mérite ou en achetant le titre de citoyen).
Les citoyens sont citoyens à vie et transmettent leur citoyenneté à leur lignée (On pourrait croire que le nombre de citoyens tend à augmenter et qu'au bout d'un certain temps, tous sont citoyens mais historiquement, dans les civilisations qui suivaient ce schéma, les citoyens sont décimés par les guerres et de nouveaux esclaves arrivent régulièrement de l'étranger).Ils peuvent aussi se porter candidats lors des élections annuelles afin de devenir hauts-fonctionnaires (magistrats). Au terme de leur mandat, ils peuvent être réélus ou
redevenir de simples citoyens.
Pour compliquer un peu l'exemple et montrer ainsi l'étendue des applications des chaînes de Markov,
nous considérerons que les fonctionnaires sont élus pour plusieurs années. Par conséquent,
l'avenir d'un individu fonctionnaire dépend du temps depuis lequel il est fonctionnaire.
Nous sommes donc dans le cas d'une chaîne de Markov non homogène. Heureusement,
nous pouvons aisément nous ramener à une chaîne homogène. En effet, il suffit de rajouter un état artificiel pour chaque année du mandat.
Au lieu d'avoir un état 4 : Fonctionnaire , nous aurons un état
* 4 : Fonctionnaire en début de mandat
* 5 : Fonctionnaire en seconde année de mandat
* etc.
Les probabilités reliant deux états artificiels consécutifs
(troisième et quatrième année par exemple) sont de valeur 1 car on considère que tout mandat commencé se termine (On pourrait modéliser le contraire en changeant la valeur de ces probabilités).
fixons la durée des mandats à deux ans, le contingent des fonctionnaires étant renouvelable par moitié chaque année. On a alors le graphe suivant :
[[Image:graphe2.jpeg|center|frame]]
Pour modéliser des élections qui ne seraient pas annuelles, il faudrait de même ajouter des états fictifs (année d'élection, un an depuis la dernière élection, etc).
La matrice '''<math>P</math>''' s'écrit alors :
:<math>
\mathbf{P}=\begin{bmatrix}
\frac{97}{98} & \frac{1}{98} & 0 & 0 & 0 \\
\frac{2}{73} & \frac{65}{73} & \frac{6}{73} & 0 & 0 \\
0 & 0 & \frac{12}{13} & \frac{1}{13} & 0 \\
0 & 0 & 0 & 0 & 1 \\
0 & 0 & \frac{7}{8} & \frac{1}{8} & 0
\end{bmatrix}
</math>
Comme cela est expliqué plus haut, <math> P^{n}</math> donne les probabilités de transition en <math>n</math> étapes. Donc <math> p^{n}_{ij}</math> est la probabilité d'être dans l'état <math>j</math> au bout de <math>n</math> années pour une lignée partie de la classe sociale <math>i</math>.
Pour savoir ce que devient un esclave au bout de <math>n</math> ans, il suffit donc d'écrire :
:<math>
\begin{bmatrix}1 & 0 & 0 & 0 & 0 \end{bmatrix} \times \mathbf P^{(n)} = \begin{bmatrix}
p_1^{(n)} \\
p_2^{(n)} \\
p_3^{(n)} \\
p_4^{(n)} \\
p_5^{(n)}
\end{bmatrix}
</math>
Où <math>p_i^{n}</math> est la probabilité d'être dans la classe sociale <math>i</math> au bout de <math>n</math> années sachant que la lignée étudiée est partie de l'état d'esclave.
Si on connaît les effectifs de chaque classe sociale à l'an 0, il suffit alors de calculer :
:<math>\frac1\mathrm{lign\acute ees} \times \begin{bmatrix}\rm esclaves&\rm libres &\rm citoyens &\rm \acute elus_1 &\rm \acute elus_2 \end{bmatrix} \times \mathbf P^{n} = Y</math>
On obtient ainsi la répartition de la population dans les différentes classes sociales (au bout de <math>n</math> années). En multipliant ce vecteur <math>Y</math> par l'effectif total de la population, on obtient les effectifs de chaque classe au bout de <math>n</math> années.
Posons-nous maintenant la question suivante :
Au bout de <math>n</math> années, combien de lignées auront déjà eu un haut fonctionnaire ayant terminé son mandat?
La réponse est différente du nombre de mandats effectués en <math>n</math> années car il y a possibilité d'être réélu.
Répondre à cette question semble difficile (encore faudrait-il que ce soit possible). En fait, il suffit de changer la modélisation du problème. Passons donc à une nouvelle modélisation pour répondre à cette question. (Par contre, elle ne permet pas de répondre aux questions précédentes d'où la présentation des 2 modèles).
Il suffit de modifier ainsi le graphe :
[[Image:graphe4.JPG|center|frame]]
On ajoute un sommet absorbant car une fois qu'une lignée a fini un mandat, on ne tient plus compte d'elle.
Si certains lecteurs font preuve d'esprit critique, ils diront peut-être que le modèle est faux car les lignées comportant un élu ne participent plus aux élections. Il n'en est rien. En effet, le nombre d'élus est proportionnel au nombre de citoyens. Ne pas réinjecter les anciens hauts-fonctionnaires parmi les candidats ne change donc en rien la probabilité pour un citoyen d'être élu car, la population des citoyens étant plus restreinte, le nombre de postes offerts l'est aussi. Ce modèle permet de répondre avec exactitude à la question posée.
On a donc une nouvelle matrice de transition :
:<math>
\mathbf{Q}=
\begin{bmatrix}
\frac{97}{98} & \frac{1}{98} & 0 & 0 & 0 & 0 \\
\frac{2}{73} & \frac{65}{73} & \frac{6}{73} & 0 & 0 & 0 \\
0 & 0 & \frac{12}{13} & \frac{1}{13} & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 1
\end{bmatrix}
</math>
En faisant les mêmes calculs qu'aux questions précédentes on obtient en dernière ligne du vecteur solution le pourcentage de lignées ayant accompli au moins un mandat ou bien l'effectif (si on multiplie par l'effectif total de la population).
Autrement dit, remodéliser le problème permet de répondre à la question qui semblait si compliquée par un simple calcul de puissances d'une matrice.
== Applications ==
*Les systèmes Markoviens sont très présents en [[Physique]] particulièrement en [[Physique statistique]]. Plus généralement l'hypothèse markovienne est souvent invoquée lorsque des probabilités sont utilisées pour modéliser l'état d'un système, en supposant toutefois que l'état futur du système peut être déduit du passé avec un historique assez faible
*Le célèbre article de [[1948]] de [[Claude Shannon]], ''A mathematical theory of communication'', qui fonde la [[théorie de l'information]], commence en introduisant la notion d'[[Entropie de Shannon|entropie]] à partir d'une modélisation Markovienne de la langue anglaise. Il montre ainsi le degré de prédictabilité de la langue anglaise, muni d'un simple modèle d'ordre 1. Bien que simples, de tels modèles permettent de bien représenter les propriétés statistiques des systèmes et de réaliser des prédictions efficaces sans décrire complètement la structure complète des systèmes.
*En [[Compression de données|compression]], la modélisation markovienne permet la réalisation de techniques de [[codage entropique]] très efficaces, comme le [[codage arithmétique]]. De très nombreux algorithmes en [[Reconnaissance des formes]] ou en [[intelligence artificielle]] comme par exemple l'[[algorithme de Viterbi]], utilisé dans la grande majorité des systèmes de téléphonie mobile pour la correction d'erreurs, font l'hypothèse d'un processus markovien sous-jacent.
*L'indice de popularité d'une page Web ([[PageRank]]) tel qu'il est utilisé par [[Google]] est défini par une chaîne de Markov. Il est défini par la probabilité d'être dans cette page à partir d'un état quelconque de la chaine de Markov représentant le Web. Si <math>N</math> est le nombre de pages Web connues, et une page <math>i</math> a <math>k_i</math> liens, alors sa probabilité de transition vers une page liée (vers laquelle elle pointe) est <math>p_i^l= \tfrac{1-q}{k_i}+\tfrac qN</math> et <math>p_i^{nl}=\tfrac qN</math> pour toutes les autres (pages non liées). Notons qu'on a bien <math>k_i p_i^l+(N-k_i) p_i^{nl}=1</math>. Le paramètre <math>q</math> vaut environ 0.15.
*Les chaînes de Markov sont un outil fondamental pour modéliser les processus en [[Théorie des files d'attente]] et en [[statistiques]].
*Les chaînes de Markov sont également utilisées en [[bioinformatique]] pour modéliser les relations entre symboles successifs d'une même séquence (de [[nucléotide]]s par exemple), en allant au delà du modèle polynomial. Les modèles markoviens cachés ont également diverses utilisations, telles que la segmentation (définition de frontières de régions au sein de séquences de [[gène]]s ou de [[protéine]]s dont les propriétés chimiques varient), l'[[alignement de séquences|alignement multiple]], la prédiction de fonction, ou la découverte de gènes (les modèles markoviens cachés sont plus « flexibles » que les définitions strictes de type ''[[codon]] start + multiples codons + codons stop'' et ils sont donc plus adaptés pour les [[eucaryote]]s (à cause de la présence d'introns dans le génome de ceux-ci) ou pour la découverte de pseudo-gènes).
== Voir aussi ==
* [[Matrice d'adjacence]]
* [[Processus de décision markovien|Problème de décision de Markov]] (MDP)
* [[Processus de décision markovien partiellement observable|Problème de décision de Markov partiellement observable]] (POMDP)
* [[Marche aléatoire]]
* [[Mouvement brownien]]
* [[Modèle des urnes d'Ehrenfest]]
* [[Modèle de Markov caché]]
* [[Chaîne de Markov à temps continu]]
* [[Chaîne de Markov à états infinis]]
== Liens externes ==
*{{en}} [http://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/Chapter11.pdf (pdf) Markov Chains chapter in American Mathematical Society's introductory probability book]
*{{en}} http://mason.gmu.edu/~scannon/MarkovChain/example
*{{fr}} http://wims.unice.fr/wims/fr_U2~proba~oefmarkov.fr.html ( exercices corrigés )
{{Portail|mathématiques|physique}}
[[Catégorie:Processus stochastique]]
[[Catégorie:Physique statistique]]
[[ar:سلسلة ماركوف]]
[[bg:Марковска верига]]
[[cs:Markovův řetězec]]
[[de:Markow-Kette]]
[[el:Αλυσίδα Μαρκόφ]]
[[en:Markov chain]]
[[es:Cadena de Markov]]
[[et:Markovi ahel]]
[[fa:فرایند مارکف]]
[[he:שרשרת מרקוב]]
[[hr:Markovljev lanac]]
[[hu:Markov-lánc]]
[[is:Markov-keðja]]
[[it:Processo markoviano]]
[[ja:マルコフ連鎖]]
[[ko:마르코프 연쇄]]
[[lt:Markovo grandinė]]
[[nl:Markov-keten]]
[[pl:Proces Markowa]]
[[pt:Cadeias de Markov]]
[[ro:Lanţ Markov]]
[[ru:Цепь Маркова]]
[[su:Ranté Markov]]
[[sv:Markovkedja]]
[[tr:Markov Zinciri]]
[[ur:مارکوو زنجیر]]
[[vi:Xích Markov]]
[[zh:马尔可夫链]]