Petit cours d'épidémiologie mathématique
Modèles en chaînes de Markov

Julien Arino

Department of Mathematics & Data Science Nexus
University of Manitoba*

Centre canadien de modélisation des maladies (CCDM/CCMM)
NSERC-PHAC EID Modelling Consortium (CANMOD, MfPH, OMNI/RÉUNIS)

* The University of Manitoba campuses are located on original lands of Anishinaabeg, Cree, Oji-Cree, Dakota and Dene peoples, and on the homeland of the Métis Nation.

Plan de ce cours

  • Chaînes de Markov en temps discret
  • Chaînes de Markov en temps continu

Chaînes de Markov en temps discret

  • Définition des CMTD
  • Comportement asymptotique des CMTD
  • CMTD régulières
  • CMTD absorbantes
  • Marches aléatoires

Définition des CMTD

Soit la probabilité que le système soit dans l'état , , lors de la répetition de l'expérience

Le système doit être dans l'un des états , , à la répétition, donc

Soit la probabilité que le système soit dans l'état , , à la répétition de l'expérience

Il y a façons d'être dans l'état à l'étape :

  • Étape dans l'état . Probabilité d'obtenir au pas est , et la probabilité de passer vers depuis est . Par le principe de multiplication,
  • Étape dans l'état , et étape dans l'état . Alors
  • ...
  • Probabilité d'être dans l'état à l'étape si on est dans l'état à l'étape est

Donc est la somme de toutes ces probabilités

Par conséquent,

En forme matricielle

où est un vecteur (ligne) de probabilité et est une -matrice de transition

Donc

Il est facile de vérifier que ceci donne la même expression que

Matrices stochastiques

La -matrice non-négative est stochastique (par ligne) si pour tout

Sot une matrice stochastique. Alors toutes les valeurs propres de sont t.q. , i.e., . De plus, est une valeur propre de

De façon un peu plus générale

Évolution de l'état régie par

où est une matrice stochastique, la matrice de transition, dont les éléments , où est une suite de variables aléatoires décrivant l'état

Si , une constante, la CMTD est homogène

On normalise souvent le temps de telle manière que

Remarque importante

Les CMTD vivent à la frontière du monde des probabilistes, qui aiment penser à comme un vecteur ligne, comme une matrice stochastique par ligne et écrivent l'évolution de la chaîne sous la forme

et des algébristes linéaires, qui préfèrent les vecteur colonnes et les matrices de transition colonne-stochastiques

Assurez-vous de la direction utilisée: votre source parle-t-elle de ou ?

Avantages des CMTD

En tant que personne qui enseigne la modélisation: la théorie des CMTD utilise beaucoup d'algèbre linéaire et matricielle et de théorie des graphes, elle est en général bien comprise et appréciée par les étudiants

Une très bonne référence sur le sujet est le livre de Kemeny & Snell

Comportement asymptotique des CMTD

Soit le vecteur ligne de distribution initiale des probabilités. Alors

En itérant, on obtient que pour tout

Par conséquent

si bien sur cette limite existe

Pour aller plus loin...

On a vu que

si cette limite existe

Un bon signe:

Soient deux matrices stochastiques de tailles compatibles, . Alors et sont stochastiques

Donc en tout cas, dans la limite est stochastique.. le comportement dépend alors de la nature de la chaîne

CMTD régulières

CMTD régulières pas très utiles en épidémiologie

  • Dans les modèles épidémiologiques, l'état est presque toujours absorbant, donc les chaînes ne sont pas régulières mais absorbantes
  • Cela vaut le coup de jeter un œil, toutefois

Chaîne de Markov régulière

Une chaîne de Markov régulière est une CMTD dans laquelle est positive pour un entier , i.e., a toutes ses entrées strictement positives

Une matrice non-négative est primitive si il existe un entier t.q. est positive

Une CMTD est régulière sa matrice de transition est primitive

Résultat important pour les chaînes régulières

Si est la matrice de transition d'une chaîne de Markov régulière, alors

  1. les puissances approchent une matrice stochastiques
  2. chaque ligne de est le même vecteur (ligne)
  3. les éléments de sont strictement positifs

Donc, si la chaîne de Markov est régulière

Vecteurs propres à gauche et à droite

Soit une -matrice, deux vecteurs colonnes, . Alors, si

est un vecteur propre (à droite) associé à la valeur propre , et si

alors est le vecteur propre à gauche associé à . À chaque valeur propre correspond un vecteur propre gauche et un vecteur propre droit (à un facteur multiplicatif près)

Le vecteur dans le résultat précédent est le vecteur propre à gauche associé à la valeur propre 1 de . (Le vecteur propre à droite correspondant à 1 est puisque )

En effet, si converge, alors à la limite, , mais puisqu'on a aussi (par la relation de récurrence) , il suit que est un point fixe du système. On écrit donc

et l'on résoud pour , ce qui revient à trouver un vecteur propre correspondant à la valeur propre 1

On peut aussi chercher comme le vecteur propre à droite associé à la valeur propre 1 de la matrice transposée . (Cela peut être utile numériquement si un algorithme ne renvoie que les valeurs propres à droite)

Pour rappel: si pour , alors pour tout , i.e., si est un vecteur propre associé à , alors tous ses multiples sont aussi des vecteurs propres associés à

L'expression obtenue pour pourrait ne pas être un vecteur stochastique. Il convient donc de vérifier que

Si ce n'est pas le cas, on considère

Une autre façon de vérifier la primitivité

Une matrice est primitive si le graphe de connection associé est fortement connexe (il y a un chemin entre tous les nœuds), et il y a au moins une entrée strictement positive sur la diagonale de

Cela se vérifie directement sur le graphe de transition
center

CMTD absorbantes

États absorbants, chaînes absorbantes

Un état dans une chaîne de Markov est absorbant si, lorsqu'il a lieu à la expérience, il se répète pour toute itération future de l'expérience. En d'autres termes, est absorbant si et pour

Une chaîne de Markov est absorbante si elle a au moins un état absorbant, et qu'il est possible d'aller de n'importe quel état vers un état absorbant (en un nombre fini de pas)

Dans une chaîne de Markov absorbante, un état qui n'est pas absorbant est dit transient

Quelques questions sur les chaînes absorbantes

Supposons que l'on ait une chaîne absorbante, e.g.,

center

  1. Le processus atteint-il toujours un état absorbant ?
  2. Quel est le temps moyen que le processus passe dans un état transient, s'il est initié dans un état transient ?
  3. Quel est le temps moyen avant que le processus entre dans un état absorbant ?
  4. Quelle est la probabilité d'être absorbé dans un état absorbant donné, s'il y en a plus d'un, quand le processus est initié dans un état transient donné ?

Atteindre un état absorbant (question 1)

Dans une chaîne de Markov absorbante, la probabilité d'atteindre un état absorbant est 1

Forme standard de la matrice de transition

La matrice de transition d'une chaîne absorbante avec états absorbants et états transients peut s'écrire sous la forme

États absorbants États transients
États absorbants
États transients

l'identité de taille , , ,

La matrice est inversible. Soit

  • la matrice fondamentale de la chaîne de Markov
  • la somme des éléments sur la ligne de

Réponses aux autres questions que nous posions:

  1. est le nombre moyen de fois que le processus est dans le état transient si il est initié dans le état transient
  2. est le nombre moyen de pas avant que le processus entre dans un état absorbant s'il est initié dans le état transient
  3. est la probabilité d'être absorbé dans le état absorbant si le processus est initié dans le état transient

Marches aléatoires

Marche aléatoire v1.0 (cas régulier)

  • Chaîne (ligne) d'états
  • Quand dans l'état , , probabilité 1/2 d'aller à gauche (vers ) et 1/2 d'aller à droite (vers )
  • Dans l'état , probabilité 1 d'aller en
  • Dans l'état , probabilité 1 d'aller en

center

Matrice de transition pour v1.0

On montre relativement facilement que est primitive, donc on a une CMTD régulière

On doit résoudre , i.e.,

Exprimons tout en fonction de :

Donc on obtient

On a

Puisque

pour avoir un vecteur de probabilité, il nous faut prendre

Donc

Supposons par exemple une condition initiale avec , i.e., la marche débute dans l'état 1. Alors

donc

Marche aléatoire v2.0 (cas absorbant)

  • Chaîne (ligne) d'états
  • Quand dans l'état , , probabilité 1/2 d'aller à gauche (vers ) et 1/2 d'aller à droite (vers )
  • Dans l'état , probabilité 1 d'aller en
  • Dans l'état , probabilité 1 d'aller en

center

Matrice de transition v2.0

Écrivons en forme standard

Les états absorbants sont et , on les écrit en premier, puis les autres états
1 0 0 0 0 0 0
0 1 0 0 0 0 0
1/2 0 0 1/2 0 0 0
0 0 1/2 0 1/2 0 0
0 0 0 0 0 0 1/2
0 1/2 0 0 0 1/2 0

On trouve donc

où une -matrice, une -matrice et une -matrice

et

Ceci est une matrice de Toeplitz tridiagonale symmétrique

(symmétrique: évident; tridiagonale: il y a 3 bandes diagonales; Toeplitz: chaque bande diagonale est constante)

On peut donc inverser explicitement.. pour illustrer, voici comment on s'y prendrait

Inverser une matrice tridiagonale symétrique

Gérard Meurant (1992): si

alors on a le résultat sur le transparent suivant

Inverse d'une matrice tridiagonale symétrique

L'inverse d'une matrice tridiagonale symétrique est donnée par

Ici, et

Écrivons et

On a , et le terme général prend la forme

En inspectant quelques termes de la suite, on développe le sentiment que

Une petite récurrence devrait confirmer ça. Hypothèse de récurrent (en changeant les indices pour impair):

est vrai. Supposons vrai. Alors

Donc est vrai

En fait, on peut aller plus loin, en exprimant

en termes de pair ou impair. Si est pair

tandis que si est impair

Mais cette dernière expression donne

donc cette formule vaut pour tous les

Pour les 's, on a et

Donc et

L'expression

est également utile

En résumé
1

Dans , on trouve les termes suivants

On a, ,

Chaînes de Markov en temps continu

Les CMTC en 2 mots

CMTC sont similaires aux CMTD à part dans leur façon de gérer le temps entre évènements (transitions)

CMTD: transitions (ou absence de transitions) ont lieu chaque

CMTC:

CMTC sont globalement équivalentes aux EDO

EDO vers CMTC : on considère des choses différentes

Poids Transition Effet
, nouvelle infection d'un susceptible
, guérison d'un infectieux

Plusieurs façons de formuler les CMTC

Une chaîne de Markov en temps continu peut être formulée en termes de

  • probabilités infinitésimales de transition
  • processus de branchement
  • temps jusqu'au prochain évènement

Ici, le temps est dans

Considérons un processus de naissance et mort. Pour petit,

avec quand

Équations de Kolmogorov avancées

Supposons connu . Alors

Calculons et prennons , ce qui donne

Ceci constitue les équations de Kolmogorov avancées associées à la CMTC

Forme vectorielle

Écrivons le système précédent sous la forme

avec

matrice génératrice. Bien sur

Lien entre CMTD et CMTC pour petit

CMTD:

avec matrice de transition . Supposons , on obtient les équations avancées de Kolmogorov pour la CMTC

où