Application aux chaînes de Markov

Introduction Supposez qu’il y a un système physique ou mathématique qui a n états possibles et à n’importe quel moment, le système est dans un et seulement un de ses n états. Supposez aussi que durant une période d’observation donnée, disons la k^ième période, la probabilité que le système soit dans un état particulier dépend seulement de son statut à la période k-1. Un tel système s'appelle une chaîne de Markov ou processus de Markov. Clarifions cette définition avec l’exemple suivant.

Exemple Supposez qu’une agence de location de voitures a trois branches à Ottawa: la branche du centre-ville (marqué A), la branche de l’est (marqué B) et la branche à l’ouest (marqué C). L'agence a un groupe de conducteurs de livraison pour servir ces trois branches. Le statisticien de l'agence a observé les faits suivants:

1. Des appels à la branche du centre-ville, 30% sont livrés au centre-ville, 30% sont livrés dans l'Est, et 40% sont livrés dans l'ouest

2. Des appels à la branche de l’Est, 40% sont livrés au centre-ville, 40% sont livrés dans l'est, et 20% sont livrés dans l'ouest

3. Des appels à la branche de l’Ouest, 50% sont livrés au centre-ville, 30% sont livrés dans l'est, et 20% sont livrés dans l'ouest:

Après avoir effectué une livraison, un conducteur va à l'endroit le plus proche pour effectuer la prochaine livraison. De cette façon, l'endroit d'un conducteur actuel est déterminé seulement par son endroit précédent.

La matrice suivante modélise le problème :

Cette matrice s’appelle la matrice de transition du système. Dans notre exemple, un état est la location d’un conducteur particulier dans le système à un moment particulier. L’entrée s_ji de la matrice ci-dessus représente la probabilité de transition de l’état correspondant à i à l’état correspondant à j. (e.g., l’état correspondant à 2 est B)

Pour faciliter les choses, nous supposerons qu'il faut à chaque conducteur le même temps d'effectuer une livraison, disons 15 minutes, et arriver à son prochaine location. D’après les données du statisticien de l'agence, après 15 minutes, des voitures qui ont commencé dans A, 30% seront encore dans A, 30% seront en B, et 40% seront en C. Comme il y a seulement trois branches et que chaque conducteur doit être quelque part après chaque livraison, la probabilité qu'une voiture est dans un de ces trois endroits doit être un. C’est pourquoi la somme de chaque colonne dans la matrice de transition est 1, et comme nous traitons des probabilités, chaque entrée doit être 0 et 1, inclus. Le fait le plus important qui nous permet de traiter ce système comme une chaîne de Markov est que la prochaine location d’un conducteur de livraison dépend uniquement sur la location courante. Il est également vrai que notre matrice des probabilités ne change pas pendant le temps d’observation.

Commençons par une question simple. Si vous commencez dans le secteur C, quelle est la probabilité que vous serez dans le secteur B après 2 livraisons? Pensez à la façon dont vous pouvez arriver à B. Vous pouvez aller de C à C, puis de C à B. Vous pouvez aller de C à B, puis de B à B. Vous pouvez aller de C à A, puis de A à B. Soit P(CB) la probabilité d’aller de C aller à B après une livraison. Utilisons cette notation pour calculer la probabilité d’aller de C à B après deux livraisons. Vous rappelez-vous comment les probabilités fonctionnent? Si deux (ou plus) événements indépendants se produisent en même temps, nous multiplions leurs probabilités. Si deux (ou plus) événements distincts se produisent en même temps, nous ajoutons leurs probabilités.

La probabilité d’aller de C à B après deux livraisons est alors donnée par P(CA)P(AB) + P(CB)P(BB) + P(CC)P(CB). Numériquement cette probabilité est (.5)(.3) + (.3)(.4) + (.2)(.3) = .33. Cette réponse nous dit que si nous commençons au secteur C, il y une chance de 33% de terminer au secteur B après deux livraisons.

Essayons ceci pour une autre paire. Si nous commençons au secteur B, quelle est la probabilité d'être en B après 2 livraisons? (Essayez ceci avant que vous lisiez plus loin!) La probabilité d’aller du secteur B au secteur B dans deux livraisons est P(BA)P(AB) + P(BB)P(BB) + P(BC)P(CB) = (4)(.3)+(.4)(.4) + (2)(.3) = 34. Maintenant qu'il n'était pas aussi mauvais de savoir où terminer après 2 livraisons, comment savoir où serons nous après 5 livraisons? La réponse à cette question demande beaucoup de calcul. Il doit y a une manière plus facile. Regardez soigneusement d'où ces nombres viennent. Tombent-ils dans des lignes ou des colonnes? Comme vous pourriez deviner, ils sont le résultat d’une multiplication matricielle. Aller de C à B dans 2 livraisons est identique à prendre que le produit scalaire de la ligne 2 et colonne 3 de la matrice T. Aller de B à B dans 2 livraisons est identique à prendre que le produit scalaire de la ligne 2 et colonne 2 de la matrice T. Si vous multipliez T par elle-même, vous obtiendrez les mêmes réponses qui vous avez obtenu pour ces deux questions et le reste de la matrice de probabilité après les 2 livraisons.

Notez que la somme des éléments dans chaque colonne est toujours 1 et chaque élément est entre 0 et 1, inclus. Puisque nous représentons notre problème avec une chaîne de Markov, c'est essentiel. Cette matrice indique les probabilités d'aller de l'endroit i à l'endroit j dans exactement 2 livraisons.

Maintenant que nous avons cette matrice, il devrait être plus facile de trouver où nous serons après 3 livraisons. Soit p(AB) la probabilité d’aller de A à B dans 2 livraisons. Trouvons la probabilité d’aller de C à B dans 3 livraisons. Cette probabilité est p(CA)P(AB) + p(CB)P(BB) + p(CC)P(CB) = (37)(.3) + (33)(.4) + (3)(.3) = 333. D'où viennent ces nombres? Cette probabilité est le produit scalaire de la ligne 2 du T² et de la colonne 3 de T. Par conséquent, si nous multiplions le T² par T, nous obtiendrons la matrice de probabilité pour les 3 livraisons :

À ce point, vous savez probablement comment trouver la matrice des probabilités pour 4, 5 livraisons ou plus. Notez que les éléments sur chaque colonne s'ajoutent toujours à 1. Par conséquent, il est important que vous n’arrondissiez pas vos réponses. Gardez autant de positions décimales que possibles pour maintenir l'exactitude.

Que vous notez-vous au sujet de ces matrices à mesure nous tenons compte de plus en plus des livraisons? Les nombres dans chaque ligne semblent converger à un nombre particulier. Pensez à ce que ceci nous indique au sujet de nos probabilités à long terme. Ceci nous indique qu’après un grand nombre de livraisons, il n'importe plus à quel secteur nous étions quand nous avons commencé. À la fin de la semaine, nous avons une chance de 38,88% d'être au secteur A, une chance de 33.33% d'être au secteur B, et une chance de 27,7% d'être dans le secteur C. Cette convergence se produira avec la plupart des matrices de transition que nous considérons.

Remarque Si toutes les entrées de la matrice de transition sont entre 0 et 1 EXCLUSIVEMENT, alors la convergence est garantie d’avoir lieu. La convergence peut avoir lieu quand 0 et 1 sont dans la matrice de transition, mais la convergence n'est plus garantie. Pour un exemple, considérer la matrice

.

Pensez à la situation que cette matrice représente afin de comprendre pourquoi A^k oscille pendant que k augmente.

Parfois, on vous donne un vecteur des distributions initiales pour décrire combien ou quelle partie des objets sont dans chaque état au début. En utilisant ce vecteur, vous pouvez découvrir combien ou quelles parties des objets sont dans chaque état à n'importe quelle heure postérieure. Si les composantes du vecteur initial de distribution sont des nombres décimaux, ceci indique quelle fraction de tout le nombre d'objets sont dans chaque état au début. Il contient seulement des nombres entre 0 et 1, inclus, et la somme des éléments dans chaque colonne est 1. Alternativement, le vecteur des distributions initiales peut contenir le nombre réel d'objets ou de personnes dans chaque état au début. Dans ce cas-ci, tous les éléments seront non négatifs et les éléments dans chaque ligne s'ajouteront à tout le nombre d'objets ou de personnes dans le système entier. Pour notre exemple, le vecteur des distributions initiales peut vous indiquer quelle fraction des conducteurs commence originalement dans chaque secteur. Si nous commençons par une distribution uniforme, nous aurons 1/3 de nos voitures de livraison dans chaque secteur. Ainsi, le vecteur

est le vecteur de des distributions initiales. Après une livraison, la distribution sera 40% des livraisons totales dans la région A, 33.33% dans la B, et 26.6% dans la région C. On trouve ceci en multipliant la matrice de distributions initiales par la matrice de transition. Ceci donne le vecteur:

A la fin de la semaine, les fractions convergent vers quelques nombres particuliers de sorte que le secteur à partir duquel nous partons n'est plus important. Après beaucoup de livraisons, nous obtiendrons le même côté droit peu importe quelle distribution initiale on commence avec. Par exemple,

Notez que le côté droit est identique à un des lignes de notre matrice de transition après beaucoup de livraisons. C’est exactement ce que nous avons deviné parce que nous avons dit que 38,8% des conducteurs seront dans le secteur A après beaucoup de livraisons indépendamment de quel pourcentage des conducteurs était dans le secteur A dans la distribution initiale. Vérifiez ceci avec plusieurs distributions initiales pour se convaincre de la vérité de cet argument.

Si la distribution initiale indique le nombre réel de personnes dans le système, l’équation suivante représente notre système après une livraison:

Avez-vous noté que nous avons maintenant un nombre rationnel de personnes dans les secteurs A et C après une livraison? Nous savons que ceci ne peut pas se produire, mais nous donne une bonne idée d'approximativement combien de personnes de livraison sont dans chaque secteur. Après beaucoup de livraisons, le côté droit de cette égalité sera également très proche d'un vecteur particulier. Par exemple,

Le vecteur particulier vers lequel le produit converge est le nombre total de personnes dans le système (54 dans ce cas-ci) multiplié par n'importe quelle colonne de la matrice A^k vers laquelle la matrice converge à mesure que k augmente,

Essayez quelques exemples pour se convaincre que le vecteur indiquant le nombre de personnes dans chaque secteur après que beaucoup de livraisons ne changent pas si les gens sont déplacés d'un état à l'autre dans la distribution initiale. Notez en outre que le nombre de personnes dans le système entier ne change jamais. Peuplez se déplacent d'un endroit à l'autre, mais le système ne perd jamais ou gagne des personnes.

J'espère que l'exemple ci-dessus vous a donné une bonne idée au sujet du processus des chaînes de Markov. Voici maintenant les concepts généraux :

Définitions Pour une chaîne de Markov avec n états, le vecteur d'état est un vecteur colonne dont la ième composante représente la probabilité que le système est dans l'état i à ce temps. Notez que la somme de toutes les entrées d'un vecteur d'état est 1. Par exemple, les vecteurs X₀ et X₁ dans l'exemple ci-dessus sont des vecteurs d'état. Si le p_ij est la probabilité de transition de l’état j à l'état i, alors la matrice T=[ p_ij] s'appelle la matrice de transition de la chaîne de Markov.

Le théorème suivant donne la relation entre deux vecteurs d’état consécutifs:

Si X_n+1 et X_n sont deux vecteurs d’état consécutifs d’une chaîne de Markov avec une matrice de transition T, alors X_n+1=T X_n

Pour une chaîne de Markov, nous sommes habituellement intéressés par le comportement à long terme d'un vecteur général d'état X_n. En d'autres termes, nous voudrions trouver la limite du X_n lorsque n→∞. Il se peut que cette limite n'existe pas, par exemple soit

alors

Clairement le vecteur X_n oscille entre les vecteurs (0, 1) et (1, 0) et donc n'approche pas un vecteur fixe

La question est alors: Qu’est ce qui fait qu’un vecteur X_n approche un vecteur limite lorsque n→∞. Le prochain théorème donnera une réponse. D'abord une définition:

Définition Une matrice de transition T s'appelle régulière toutes les entrées de la matrice T^r sont positives pour un certain nombre entier r (0 n'est pas considéré positif). Par exemple, la matrice

est régulière car

.

Un processus de chaîne de Markov s'appelle régulier si sa matrice de transition est régulière.

Nous énonçons maintenant le théorème principal dans la théorie de chaînes de Markov:

1. Si T est une matrice régulière de transition, alors si n tend vers l'infini, Tⁿ→S où S est une matrice de la forme [v, v,…,v] avec v est un vecteur constant.

2. Si T est une matrice régulière de transition d'un processus de chaîne de Markov, et si X est n'importe quel vecteur d'état, alors si n tend vers l'infini, TⁿX→p où p est un vecteur fixe de probabilité (la somme de ses entrées est 1), avec des entrées toutes positives.

Considérez une chaîne de Markov avec une matrice régulière de transition T, et soit S la limite de Tⁿ lorsque n approche l'infini, alors TⁿX→SX=p, et le système tend vers un vecteur d'état fixe p appelé le vecteur équilibre du système. Maintenant puisque Tⁿ⁺¹=TTⁿ et que Tⁿ⁺¹ et Tⁿ approchent S, nous avons S=TS. Notez que n'importe quelle colonne de cette équation matricielle donne Tp=p. Alors, le vecteur équilibre d'une chaîne de Markov régulière avec une matrice de transition T est l’unique vecteur de probabilité p satisfaisant Tp=p.

Y a-t-il une manière de calculer le vecteur équilibre d'une chaîne de Markov régulière sans employer vraiment la notion de la limite? Bien, si vous regardez de nouveau l'équation Tp=p, pouvez-vous dire que représente le vecteur p pour la matrice T? si vous ne connaissez pas la réponse, ça sera peut être une bonne idée de vous de la définition d’un vecteur propre et d’une valeur propre d'une matrice carrée:

Étant Donnée une matrice carrée A, nous disons que le nombre λ est une valeur propre de A s’il existe un vecteur non nul X satisfaisant: AX=λX. Dans ce cas-ci, nous disons que X est un vecteur propre de A correspondant à la valeur propre λ.

Il est clair maintenant qu<un vecteur d’équilibre d'une chaîne de Markov régulière est un vecteur propre pour la matrice de transition correspondant à la valeur propre 1.

Rappelez-vous que les valeurs propres d'une matrice A sont les solutions de l'équation

det(A-λI)=0 où I est la matrice identité de la même taille que A. Si λ est une valeur propre de A, alors un vecteur propre correspond à λ est une solution du système homogène (A-λI)X=0. Par conséquence, il y a une infinité de vecteurs propres correspondant à une certaine valeur propre.

Exemple Si vous avez vécu à Ottawa pendant quelque temps, vous deviez certainement remarquer que la météo est un souci principal de la population. Une étude non officielle de la météo dans la ville au début du printemps montre les observations suivantes:

1. Il est presque impossible d'avoir deux beaux jours consécutifs

2. Si nous avons un beau jour, on a la même probabilité d’avoir de la neige ou de la pluie le jour suivant

3. Si nous avons la neige ou de la pluie, alors nous avons une chance égale pour avoir la même chose le jour suivant

4. S'il y a un changement de neige ou de pluie, seulement la moitié du temps est ce changement à un beau jour

1) Écrire la matrice de transition qui modélise ce système.

2) S’il fait beau aujourd’hui, quelle est la probabilité qu’il fait beau dans une semaine?

3) Trouver le comportement de la météo à long terme.

Solution 1) Comme la météo du demain dépend seulement d’aujourd’Hui, c’est un processus de Markov. La matrice de transition de ce système est

où les lettres B, P, N représentent Beau, Pluie et Neige respectivement

2) S’il fait beau aujourd’Hui, alors le vecteur d’état initial est :

Après sept jours (une semaine), le vecteur d’état sera

Alors, il y a une chance de 20% d’avoir un beau jour dans une semaine.

3) Remarquez d'abord que nous traitons une chaîne de Markov régulière puisque la matrice de transition est régulière, ainsi nous sommes sûrs que le vecteur équilibré existe. Pour le trouver résolvons le système homogène (T-I)X=0 qui a la matrice suivante de coefficients:

La forme échelonnée réduite de cette matrice est

.

Et la solution générale du système (T-I)X=0 est :

Quelle solution devons-nous choisir ? Rappelez-vous qu'un vecteur équilibre est en particulier un vecteur de probabilité ; c'est-à-dire la somme de ses composantes est 1 : 0.5t+t+t=1 donne t=0.4. Ainsi, le vecteur équilibre est

À long terme, il y a une probabilité de 20% d’avoir un beau jour, 40% d’avoir de la pluie et 40% d’avoir de la neige.