Processus de Markov à temps continu

En théorie des probabilités, un processus de Markov à temps continu, ou chaîne de Markov à temps continu est une variante à temps continu du processus de Markov. Plus précisément, c'est un modèle mathématique à valeur dans un ensemble dénombrable, les états, dans lequel le temps passé dans chacun des états est une variable aléatoire réelle positive, suivant une loi exponentielle.

Cet objet est utilisé pour modéliser l'évolution de certains systèmes, comme les files d'attente.

Idée générale[modifier | modifier le code]

Une chaîne de Markov à temps continu (X_t)_t≥0 est un processus stochastique. Chaque X_t est une variable aléatoire qui indique dans quel état le système se trouve à l'instant t. Par exemple, il peut faire beau ou alors pleuvoir. Supposons qu'il fasse beau au début, autrement X₀ = beau. Le processus reste pendant un moment dans l'état beau. Par exemple X₀ = ... = X_0.001... = X_0.401... = X_0.499... = beau. Puis par exemple, le processus change d'état au temps 0.5, et va dans l'état pluie. Le temps d'attente dans l'état beau suit une loi exponentielle (voir fonctions de densité dans la figure de droite) d'un certain paramètre. Là dans l'exemple, le temps d'attente était de 0.5. Puis le processus reste un moment dans l'état pluie X_0.5 = ... = X_0.656... = pluie.

Définitions formelles[modifier | modifier le code]

Dans cette section, nous donnons d'abord les éléments qui permettent de caractériser une chaîne de Markov à temps continu. Puis nous donnerons plusieurs définitions équivalentes alternatives qui utilisent ces éléments pour définir le processus (X_t)_t≥0.

Caractérisation[modifier | modifier le code]

Une chaîne de Markov est caractérisée par :

un ensemble S fini ou dénombrable d'états ;
une distribution initiale sur l'ensemble des états ;
une matrice Q de taux de transition, aussi appelée générateur infinitésimal.

La matrice Q est de dimension |S|². Étant donnés deux états différents i ≠ j, les éléments q_ij de la matrice Q sont des réels positifs qui quantifient la vitesse de transition de l'état i vers l'état j. Les éléments q_ii sont choisis pour que les colonnes de chaque ligne somment à zéro, i.e.

q_{ii}=-\sum _{j\neq i}q_{ij}

.

Définitions équivalentes[modifier | modifier le code]

Il existe plusieurs façons équivalentes de définir le processus (X_t)_t≥0^[1].

Définition infinitésimale[modifier | modifier le code]

Soit X_t la variable aléatoire décrivant l'état du processus au temps t. Pour tous t et h positifs, conditionnellement à {X_t = i}, X_t + h est indépendant de (X_s : s≤ t) et, pour h tendant vers 0, on a pour tout états i et j,

\Pr(X(t+h)=j\mid X(t)=i)=\delta _{ij}+q_{ij}h+o(h),

où δ_ij vaut 1 si i=j et 0 sinon (il s'agit d'un delta de Kronecker), q_ij est l'élément à la ligne i et à la colonne j dans la matrice Q, et $o(h)$ désigne une fonction négligeable devant $h$ (voir notation de Landau).

Définition par les sauts[modifier | modifier le code]

Le processus peut rester dans un état un certain temps puis changer d'état : on parle de saut. Soit Y_n l'état du processus après son n-ième saut et S_n le temps passé dans l'état Y_n. Alors (Y_n)_n≥0 est une chaîne de Markov à temps discret et, conditionnellement à (Y₀, ..., Y_n), les temps d'attente (S₀, ..., S_n) sont des variables exponentielles indépendantes de paramètres respectifs $(-q_{Y_{0}Y_{0}},\ldots ,-q_{Y_{n}Y_{n}})$ .

Définition par les probabilités de transitions[modifier | modifier le code]

Pour tous les instant t₀, t₁, ... et pour tous les états i₀, i₁, ... correspondants, on a

\Pr(X_{t_{n+1}}=i_{n+1}|X_{t_{0}}=i_{0},X_{t_{1}}=i_{1},\ldots ,X_{t_{n}}=i_{n})=p_{i_{n}i_{n+1}}(t_{n+1}-t_{n}),

où p_ij est la fonction solution de l'équation de Kolmogorov (en) :

P'(t)=P(t)Q,

avec pour condition initiale P(0) = I, la matrice identité. La résolution de cette équation conduit alors à

P(t)=e^{tQ}.

Propriétés[modifier | modifier le code]

Irréductibilité[modifier | modifier le code]

Un état j est dit accessible à partir d'un autre état i (écrit i → j) s'il est possible d'obtenir j à partir de i. C'est-à-dire, si :

\exists {t}\geq 0{\text{, }}\operatorname {Pr} _{i}(X(t)=j)>0.

On dit d'un état i qu'il communique avec un état j (écrit i ↔ j) si i → j et j → i. Un ensemble d'états C est une classe communicante si chaque paire d'états dans C communiquent entre eux, et si aucun état dans C ne communique avec un état non-présent dans C. Puisque la communication est une relation d'équivalence, l'espace d'états S peut être partitionné en un ensemble de classes communicantes. Un processus de Markov à temps continu est irréductible si l'espace S entier est une classe communicante unique.

Pour tout $i$ et $j$ dans une même classe communicante C, on peut montrer (en utilisant des propriétés de sous-additivité) que la limite

\lim _{t\to +\infty }{\frac {\log p_{i,j}(t)}{t}}

existe et ne dépend ni de $i$ ni de $j$ ; on la note $\lambda (C)$ .

Démonstration

On a $p_{i,i}(s+t)\geq p_{i,i}(s)p_{i,i}(t)$ . Posons $\phi _{i}(t)=-\log p_{i,i}(t)$ . Alors $\phi _{i}(t)\geq 0$ et $\phi _{i}(s+t)\leq \phi _{i}(s)+\phi _{i}(t)$ . Cette sous-additivité entraîne que la limite

\lambda _{i}=\lim _{t\to +\infty }{\frac {\phi _{i}(t)}{t}}=\inf _{t\geq 0}{\frac {\phi _{i}(t)}{t}}

existe avec $\lambda _{i}\geq 0$ . Donc $\phi _{i}(t)\geq \lambda _{i}t$ et $p_{i,i}(t)\leq e^{-\lambda _{i}t}$ . Par ailleurs,

p_{i,j}(a)p_{j,j}(t)p_{j,i}(b)\leq p_{i,i}(t+a+b)\leq e^{-\lambda _{i}(t+a+b)}.

Donc $p_{j,j}(t)\leq Ke^{-\lambda _{i}t}$ et $\lambda _{j}\geq \lambda _{i}$ . En inversant les rôles de $i$ et $j$ , on trouve que $\lambda _{i}=\lambda _{j}=\lambda$ . Enfin,

{\frac {\log p_{i,j}(a)}{t}}+{\frac {\log p_{j,j}(t-a)}{t}}\leq {\frac {\log p_{i,j}(t)}{t}}\leq {\frac {\log p_{j,j}(t+a)}{t}}-{\frac {\log p_{j,i}(a)}{t}}.

Le membre de gauche tend vers $-\lambda$ . Le membre de droite aussi. Donc $(\log p_{i,j}(t))/t$ tend vers $-\lambda$ .

Par exemple, dans une chaîne où l'état 0 est absorbant, où les états {1,2,...} forment une classe communicante et où le système est absorbé par l'état 0 presque sûrement, la limite donne le taux d'absorption de la chaîne, parfois appelé paramètre de Kingman.

Autre exemple. Considérons la marche aléatoire sur l'ensemble des entiers relatifs $\{...,-2,-1,0,1,2,...\}$ dont le générateur est donné par $Q_{i,i}=-1$ , $Q_{i,i+1}=p$ $(0<p<1)$ , $Q_{i,i-1}=q=1-p$ et $Q_{i,j}=0$ pour les autres indices. La matrice $Q$ est une matrice de Toeplitz tridiagonale. Alors

\lim _{t\to +\infty }{\frac {\log p_{i,j}(t)}{t}}=2{\sqrt {pq}}-1.

On remarque que la limite est strictement négative si $p\neq 1/2$ et nulle si $p=1/2$ .

Démonstration

Le système se déplace d'un pas vers la droite avec une probabilité $p$ et d'un pas vers la gauche avec une probabilité $q$ au bout d'un temps distribué exponentiellement de moyenne 1. Au bout d'un temps $t$ , il y aura eu $j$ sauts avec une probabilité $e^{-t}t^{j}/j!$ (c'est un processus de Poisson). Le système se sera finalement déplacé de $k$ pas vers la droite ( $k\geq 0$ ) s'il a effectué $k+r$ pas vers la droite et $r$ pas vers la gauche (donc un total de $k+2r$ pas). Donc

p_{i,i+k}(t)=\sum _{r=0}^{+\infty }e^{-t}{\frac {t^{k+2r}}{(k+2r)!}}{k+2r \choose r}q^{r}p^{k+r}

si $k\geq 0$ . On remarque que

p_{i,i+k}(t)=e^{-t}(p/q)^{k/2}\sum _{r=0}^{+\infty }{\frac {({\sqrt {pq}}t)^{k+2r}}{r!(k+r)!}}=e^{-t}(p/q)^{k/2}I_{k}(2t{\sqrt {pq}}),

où $I_{k}(\cdot )$ est la fonction de Bessel modifiée de première espèce. De même,

p_{i,i-k}(t)=\sum _{r=0}^{+\infty }e^{-t}{\frac {t^{k+2r}}{(k+2r)!}}{k+2r \choose r}p^{r}q^{k+r}=e^{-t}(p/q)^{-k/2}I_{k}(2t{\sqrt {pq}})

si $k<0$ . Finalement,

p_{i,j}(t)=e^{-t}(p/q)^{(j-i)/2}I_{|j-i|}(2t{\sqrt {pq}}).

Comme $I_{n}(x)\sim e^{x}/{\sqrt {2\pi x}}$ quand $x\to +\infty$ , on a donc

\lim _{t\to +\infty }{\frac {\log p_{i,j}(t)}{t}}=2{\sqrt {pq}}-1.

Applications[modifier | modifier le code]

Théorie des files d'attente[modifier | modifier le code]

Un domaine d'application des processus de Markov à temps continu est la théorie des files d'attente. Par exemple une file M/M/1 (selon la notation de Kendall) est un modèle où un processeur doit traiter des requêtes, qui s'accumulent (dans l'ordre) dans une file d'attente. Les requêtes arrivent suivant une loi exponentielle de taux $\lambda$ et le processeur les traite avec une loi exponentielle de taux $\mu$ . La chaîne sous-jacente est la suivante :

Et la matrice (générateur infinitésimal) de taux est :

Q={\begin{pmatrix}-\lambda &\lambda \\\mu &-(\mu +\lambda )&\lambda \\&\mu &-(\mu +\lambda )&\lambda \\&&\mu &-(\mu +\lambda )&\lambda &\\&&&&\ddots \end{pmatrix}}

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Continuous-time Markov chain » (voir la liste des auteurs).

↑ (Norris 1997, Théorème 2.8.2)

Bibliographie[modifier | modifier le code]

P. Désesquelles : Les processus de Markov en biologie, sociologie, géologie, chimie, physique et applications industrielles. Ellipses, 2016.
E. Pardoux : Processus de Markov et applications. Dunod, 2007.
B. Sericola : Chaînes de Markov - Théorie, algorithmes et applications. Lavoisier, 2013.
(en) J. R. Norris, Markov Chains, Cambridge University Press, 1997
J.F.C. Kingman : The exponential decay of Markov transition probabilities. Proc. London Math. Soc. (1963) 337-358.

Lien externe[modifier | modifier le code]

Chapitre « Processus de Poisson » du cours de maîtrise « Modèles stochastiques » (2002) de Dominique Bakry sur le sujet, plus orienté vers la théorie de la mesure.

Portail des probabilités et de la statistique

[1] (Norris 1997, Théorème 2.8.2)

[1]

v · m Théorie des files d'attente
Nœuds de file d'attente uniques	D/M/1 queue (en) M/D/1 queue (en) M/D/c queue (en) file M/M/1 Burke's theorem (en) M/M/c queue (en) M/M/∞ queue (en) M/G/1 queue (en) Formule de Pollaczek-Khinchine Matrix analytic method (en) M/G/k queue (en) G/M/1 queue (en) G/G/1 queue (en) Kingman's formula (en) Lindley equation (en) Fork–join queue (en) Bulk queue (en)
Processus d'arrivée	Processus de Poisson Markovian arrival process (en) Rational arrival process (en)
File de réseau	Jackson network (en) Traffic equations (en) Gordon–Newell theorem (en) Mean value analysis (en) Buzen's algorithm (en) Kelly network (en) G-network (en) BCMP network (en)
Politique de services	First in, first out Last in, first out Processor sharing (en) Shortest job first Shortest remaining time
Concepts clés	Processus de Markov à temps continu Notation de Kendall Théorie des files d'attente Product-form solution (en) Balance equation (en) Quasireversibility (en) Flow-equivalent server method (en) Arrival theorem (en) Decomposition method (queueing theory) (en) Beneš method (en)
Limite des théorèmes	Fluid limit (en) Mean field theory Heavy traffic approximation (en) Reflected Brownian motion (en)
Extensions	Fluid queue (en) Layered queueing network (en) Polling system (en) Adversarial queueing network (en) Loss network (en)