MARKOV [PDF]

Zitiervorschau

1. Dans les âges sombres, Harvard, Dartmouth et Yale n'admettaient que des étudiants de sexe masculin. Supposons qu'à ce moment-là, 80 pour cent des fils d'hommes de Harvard sont allés à Harvard et le reste est allé à Yale, 40 pour cent des fils d'hommes de Yale sont allés à Yale, et le reste s'est réparti également entre Harvard et Dartmouth; et des fils des hommes de Dartmouth, 70 pour cent sont allés à Dartmouth, 20 pour cent à Harvard et 10 pour cent à Yale. (i) (ii)

Trouvez la probabilité que le petit-fils d'un homme de Harvard soit allé à Harvard. Modifiez ce qui précède en supposant que le fils d'un homme de Harvard allait toujours à Harvard. Encore une fois, trouvez la probabilité que le petit-fils d'un homme de Harvard soit allé à Harvard.

Solution. Nous formons d'abord une chaîne de Markov avec l'espace d'états S = {H, D, Y} et la matrice de probabilité de transition suivante:

P

.

Notez que les colonnes et les lignes sont ordonnées: d'abord H, puis D, puis Y. Rappel: la ijème entrée de la matrice Pn donne la probabilité que la chaîne de Markov commençant à l'état i soit dans l'état j après n étapes. Ainsi, la probabilité que le petit-fils d'un homme de Harvard soit allé à Harvard est l'élément supérieur gauche de la matrice

P

.

Il est égal à 0,7 = 0,82 + 0,2 × 0,3 et, bien entendu, il n'est pas nécessaire de calculer tous les éléments de P2 pour répondre à cette question. Si tous les fils d'hommes de Harvard allaient à Harvard, cela donnerait la matrice suivante pour la nouvelle chaîne de Markov avec le même ensemble d'états:

P L'élément supérieur gauche de P2 est 1, ce qui n'est pas surprenant, car les descendants des hommes de Harvard n'entrent que dans cette institution.

2. Envisagez une expérience d'accouplement de lapins. On observe l'évolution d'un particulier gène qui apparaît sous deux types, G ou g. Un lapin a une paire de gènes, soit GG (dominant), Gg (hybride - l'ordre n'est pas pertinent, donc gG est le même que Gg) ou gg (récessif). En accouplant deux lapins, la progéniture hérite d'un gène de chacun de ses parents avec une probabilité égale. Ainsi, si nous accouplons une dominante (GG) avec un hybride (Gg), la progéniture est dominante avec une probabilité 1/2 ou hybride avec une probabilité 1/2. Commencez avec un lapin de caractère donné (GG, Gg ou gg) et accouplez-le avec un hybride. La progéniture produite est à nouveau accouplée avec un hybride, et le processus est répété sur plusieurs générations, toujours en s'accouplant avec un hybride. (i) Notez les probabilités de transition de la chaîne de Markov ainsi définie. (ii) Supposons que nous commençons avec un lapin hybride. Soit µn la distribution de probabilité du caractère du lapin de la n-ième génération. En d'autres termes, µn (GG), µn (Gg), µn (gg) sont les probabilités que le lapin de n-ième génération soit GG, Gg ou gg, respectivement. Calculez µ1, µ2, µ3. Pouvez-vous faire la même chose pour µn pour le n général? Solution. (i) L'ensemble des états est S = {GG, Gg, gg} avec les probabilités de transition suivantes:

Nous pouvons réécrire la matrice de transition sous la forme suivante:

P (iii)

.

Les éléments de la deuxième ligne de la matrice Pn nous donneront les probabilités pour un hybride de donner des espèces dominantes, hybrides ou récessives en (n - 1) ème génération dans cette expérience, respectivement (lire cette ligne de gauche à droite ). Nous trouvons d'abord

P

P

P

de sorte que µi (GG) = 0,25, µi (Gg) = 0,5, µi (gg) = 0,25, i = 1,2,3. En fait, les probabilités sont les mêmes pour n'importe quel i ∈ N.Si vous avez obtenu ce résultat avant 1858 lorsque Gregor Mendel a commencé à élever des pois de jardin dans son jardin monastique et a analysé la progéniture de ces accouplements, vous seriez probablement très célèbre car il ressemble vraiment à une loi! C'est ce que Mendel a découvert en croisant des mono-hybrides. Dans un cadre plus général, cette loi est connue sous le nom de loi de Hardy-Weinberg. Comme exercice, montrez que

Essayer! 3 Une certaine machine à calculer n'utilise que les chiffres 0 et 1. Elle est censée transmettre l'un de ces chiffres en plusieurs étapes. Cependant, à chaque étape, il y a une probabilité p que le chiffre qui entre dans cette étape soit changé à sa sortie et une probabilité q = 1 - p que ce ne soit pas le cas. Formez une chaîne de Markov pour représenter le processus de transmission en prenant comme états les chiffres 0 et 1. Quelle est la matrice des probabilités de transition? Maintenant, dessinez un arbre et attribuez des probabilités en supposant que le processus commence à l'état 0 et passe par deux étapes de transmission. Quelle est la probabilité que la machine, après deux étapes, produise le chiffre 0 (c'est-à-dire le chiffre correct)? Solution. En prenant comme états les chiffres 0 et 1, nous identifions la chaîne de Markov suivante (en spécifiant les états et les probabilités de transition):

où p + q = 1. Ainsi, la matrice de transition est la suivante: P. Il est clair que la probabilité que la machine produise 0 si elle commence par 0 est p2 + q2. 4 Supposons que la profession d’un homme puisse être qualifiée de professionnel, d’ouvrier qualifié ou d’ouvrier non qualifié. Supposons que, parmi les fils d'hommes professionnels, 80 pour cent sont des professionnels, 10 pour cent sont des ouvriers qualifiés et 10 pour cent sont des ouvriers non qualifiés. Dans le cas des fils d'ouvriers qualifiés, 60 pour cent sont des

ouvriers qualifiés, 20 pour cent sont des professionnels et 20 pour cent sont non qualifiés. Enfin, dans le cas des ouvriers non qualifiés, 50 pour cent des fils sont des ouvriers non qualifiés et 25 pour cent chacun appartiennent aux deux autres catégories. Supposons que chaque homme a au moins un fils et forme une chaîne de Markov en suivant la profession d'un fils choisi au hasard d'une famille donnée sur plusieurs générations. Mettre en place la matrice des probabilités de transition. Trouvez la probabilité qu'un petit-fils d'un ouvrier non qualifié choisi au hasard soit un homme de métier. Solution. La chaîne de Markov dans cet exercice a les états d'ensemble suivants S = {professionnel, qualifié, non qualifié} avec les probabilités de transition suivantes: Professionnel qualifié non qualifié Professionnel .8 .1 .1 Qualifié .2 .6 .2 Non qualifié .25 .25 .5 de sorte que la matrice de transition pour cette chaîne soit

P avec

P et donc la probabilité qu'un petit-fils choisi au hasard d'un ouvrier non qualifié soit un professionnel est de 0,375. 5 J'ai 4 parapluies, certains à la maison, certains au bureau. Je continue de me déplacer entre la maison et le bureau. Je prends un parapluie avec moi seulement s'il pleut. S'il ne pleut pas, je laisse le parapluie derrière moi (à la maison ou au bureau). Il peut arriver que tous les parapluies soient au même endroit, je suis à l'autre, il commence à pleuvoir et doit partir, alors je me mouille. 1. Si la probabilité de pluie est p, quelle est la probabilité que je me mouille? 2. Les estimations actuelles montrent que p = 0,6 à Édimbourg. Combien de parapluies doisje avoir pour que, si je suis la stratégie ci-dessus, la probabilité que je me mouille soit inférieure à 0,1? Solution. Pour résoudre le problème, considérons une chaîne de Markov prenant des valeurs dans l'ensemble S = {i: i = 0,1,2,3,4}, où i représente le nombre de parapluies à l'endroit où je suis actuellement (domicile ou Bureau). Si i = 1 et qu'il pleut alors je prends le parapluie, je passe à l'autre endroit, où il y a déjà 3 parapluies, et, y compris celui que j'apporte, j'ai 4 parapluies suivants. Ainsi,

p1,4 = p, car p est la probabilité de pluie. Si i = 1 mais qu'il ne pleut pas alors je ne prends pas le parapluie, je vais à l'autre endroit et je trouve 3 parapluies. Ainsi, p1,3 = 1 − p ≡ q. En continuant de la même manière, je forme une chaîne de Markov avec le schéma suivant: 1

q 0

1

q

p p

2

4

3 p

p

q q

Mais cela n'a pas l'air très joli. Alors, nous allons le redessiner:

0

4

1

3

2

Trouvons la distribution stationnaire. En assimilant les flux, nous avons: π(2) = π(3) = π(1) = π(4) π(0) = π(4)q. Egalemrnt

En exprimant toutes les probabilités en termes de π (4) et en insérant dans cette dernière équation, on trouve π(4)q + 4π(4) = 1, Ou

Je me mouille à chaque fois que je me trouve dans l'état 0 et qu'il pleut. La chance que je sois en état 0 est π (0). La chance qu'il pleuve est p. D'où

Avec p = 0,6, soit q = 0,4, on a

P (HUMIDE) ≈ 0,0545, moins de 6%. C'est bien. Si je veux que la chance soit inférieure à 1%, alors, clairement, j'ai besoin de plus de parapluies. Alors, supposons que j'ai besoin de N parapluies. Configurez la chaîne de Markov comme ci-dessus. Il est clair que

En insérant) nous trouvons

π( N )=

1 = π( N − 1)= ··· = π(1) q+ N ,

π(0)=

q q+ N,

et donc

pq P(WET) =

. q+N

Nous voulons P (WET) = 1/100, ou q + N> 100pq, ou N> 100pq - q = 100 × 0,4 × 0,6 - 0,4 = 23,6. Donc, pour réduire le risque d’être mouillé de 6% à moins de 1%, j’ai besoin de 24 parapluies au lieu de 4. C’est trop. Je préfère me mouiller. 6. Supposons que ξ0, ξ1, ξ2, ... sont des variables aléatoires indépendantes avec une fonction de probabilité commune f (k) = P (ξ0 = k) où k appartient, par exemple, aux nombres entiers. Soit S = {1, ..., N}. Soit X0 une autre variable aléatoire, indépendante de la suite (ξn), prenant des valeurs dans S et soit f: S × Z → S une certaine fonction. Définissez de nouvelles variables aléatoires X1, X2, ... par Xn + 1 = f (Xn, ξn), n = 0,1,2 ... (i) Montrer que les Xn forment une chaîne de Markov. (ii) Trouvez ses probabilités de transition. Solution. (i) Fixez un temps n ≥ 1. Supposons que vous sachiez que Xn = x. Le but est de montrer que PAST = (X0, ..., Xn − 1) est indépendant de FUTURE = (Xn + 1, Xn + 2, ...). Les variables du PAST sont des fonctions de X0, ξ1, ..., ξn − 2. Les variables du FUTUR sont des fonctions de x, ξn, ξn + 1, ... Mais X0, ξ1, ..., ξn − 2 sont indépendants de ξn, ξn + 1, .... Par conséquent, le PASSÉ et le FUTUR sont indépendants.

(ii) P(Xn+1 = y|Xn = x) = P(f(Xn,ξn) = y|Xn = x) = P(f(x,ξn) = y|Xn = x) = P(f(x,ξn) = y) = P(f(x,ξ0) = y) = P(ξ0 ∈ Ax,y), Où Ax,y := {ξ : f(x,ξ) = y}. 7. Discutez des propriétés topologiques des graphiques des chaînes de Markov suivantes:

Solution. Dessinez le diagramme de transition pour chaque cas. (a) Irréductible? OUI car il existe un chemin entre chaque état et n'importe quel autre état. Apériodique? OUI car les temps n pour lesquels 0 sont 1,2,3,4,5, ... et leur pgcd est 1. (b) Irréductible? OUI car il existe un chemin entre chaque état et n'importe quel autre état. Apériodique? OUI car les temps n pour lesquels 0 sont 1,2,3,4,5, ... et leur pgcd est 1. (c) Irréductible? NON car à partir de l'état 2, il reste à 2 pour toujours. Cependant, on peut vérifier que tous les états ont la période 1, simplement parce que pi, i> 0 pour tout i = 1,2,3. (d) Irréductible? OUI car il existe un chemin entre chaque état et n'importe quel autre état. Apériodique? NON car les temps n pour lesquels 0 sont 2,4,6, ... et leur pgcd est 2. (e) Irréductible? OUI car il existe un chemin entre chaque état et n'importe quel autre état. Apériodique? OUI car les temps n pour lesquels 0 sont 1,2,3,4,5, ... et leur pgcd est 1. 8. Considérez la tournée du chevalier sur un échiquier: un chevalier sélectionne l'une des positions suivantes au hasard, indépendamment du passé. (i) Pourquoi ce processus est-il une chaîne de Markov? (ii) Qu'est-ce que l'espace d'états? (iii) Est-il irréductible? Est-ce apériodique? (iv) Trouvez la distribution stationnaire. Donnez-en une interprétation: qu'est-ce que cela signifie, physiquement? (v) Quels sont les états les plus probables à l'état d'équilibre? Quels sont les moins probables? Solution. (i) Une partie du problème consiste à le mettre en place correctement en termes mathématiques. Quand on dit que le «chevalier sélectionne une des positions suivantes au hasard indépendamment du passé» on veut dire que la prochaine position Xn + 1 est

fonction de la position courante Xn et d'un choix aléatoire ξn d'un voisin. Le problème se présente donc sous la même forme que celui ci-dessus. Donc (Xn) est une chaîne de Markov. (ii) L'espace d'état est l'ensemble des carrés de l'échiquier. Il y a 8 × 8 = 64 carrés. Nous pouvons les étiqueter par une paire d'entiers. Par conséquent, l'espace d'états est S = {(i1,i2) : 1 ≤ i1 ≤ 8, 1 ≤ i2 ≤ 8} = {1,2,3,4,5,6,7,8} × {1,2,3,4,5,6,7,8}. (iii) La meilleure façon de voir s'il est irréductible est de prendre un chevalier et de le déplacer sur un échiquier. Vous réaliserez en effet que vous pouvez trouver un chemin qui mène le chevalier de n'importe quelle case à n'importe quelle autre case. Par conséquent, chaque état communique avec tous les autres états, c'est-à-dire qu'il est irréductible. Pour voir quelle est la période, recherchez la période pour un état spécifique, par exemple à partir de (1,1). Vous pouvez voir que, si vous démarrez le chevalier à partir de (1,1), vous ne pouvez le ramener à (1,1) qu'en nombre pair d'étapes. La période est donc 2. La réponse est donc que la chaîne n'est pas apériodique. (iv) Vous n'avez aucune chance de résoudre un ensemble de 64 équations avec 64 inconnues, sauf si vous faites une supposition éclairée. Premièrement, il y a beaucoup de symétrie. Ainsi, les carrés (états) symétriques par rapport au centre de l'échiquier doivent avoir la probabilité sous la distribution stationnaire. Ainsi, par exemple, les états (1,1), (8,1), (1,8), (8,8) ont la même probabilité. Etc. Deuxièmement, vous devez comprendre que (1,1) doit être moins probable qu'un carré plus proche du centre, par ex. (4,4). La raison en est que (1,1) a moins d'états suivants (exactement 2) que (4,4) (qui a 8 états suivants). Supposons donc que si x = (i1, i2), alors π (x) est proportionnel au nombre N (x) des états suivants possibles du carré x: π (x) = CN (x). Mais il faut MONTRER que ce choix est correct. Disons que y est un VOISIN de x si y est un état suivant possible de x (s'il est possible de déplacer le chevalier de x vers y en une seule étape). Il faut donc montrer qu'un tel π satisfait les équations d'équilibre: π(x) = Xπ(y)py,x. y∈S

De manière équivalente, en annulant C des deux côtés, on se demande si N(x) = XN(y)py,x y∈S

qui est vrai. Mais la somme de droite est nulle sauf si x est un VOISIN de y: N(x) =

X

N(y)py,x y∈S: x voisin de y

Mais la règle du mouvement est de choisir l'un des voisins avec une probabilité égale: ,

si x est un voisin de y

y,x

0, autrement.

Ce qui signifie que l'équation précédente devient

N(x)

XX

=

1

y∈S: x neighbour ofneighbour of y

X

=

1,

y∈S: y neighbour of x

où dans la dernière égalité nous avons utilisé le fait évident que x est un voisin de y si et seulement si y est un voisin de x (symétrie de la relation) et donc la dernière somme est égale, en effet, N (x). Donc, notre supposition est correcte! Par conséquent, tout ce que nous avons à faire est de compter les voisins de chaque carré x. Nous y voilà:

2 3

4 4 4 4 3 2

3 4 6 6 6

6 4

3

4 6 8 8 8 8

6 4

4 6 8 8 8 8

6 4

4 6

8 8 8 8

6 4

4 6 8 8 8 8

6 4

3 4 6 6 6 6 4 3 2 3 4 4 4 4 3 2 Signification de π. Si nous commençons par 2 × 4 + 3 × 8 + 4 × 20 + 6 × 16 + 8 × 16 = 336. So C = 1/336, and π(1,1) = 2/336, π(1,2) = 3/336, π(1,3) = 4/336, ..., π(4,4) = 8/336, ..., etc. Signification de π. Si nous commençons par P (X0 = x) = π (x),

alors, pour tous les instants n ≥ 1, x ∈ S, P (Xn = x) = π (x), x ∈ S. (v) Les coins du coin sont les moins probables: 2/336. Les 16 intermédiaires sont les plus probables: 8/336. 9. Considérons une chaîne de Markov avec deux états 1,2. Supposons que p1,2 = a, p2,1 = b. Pour quelles valeurs de a et b obtenons-nous une chaîne de Markov absorbante? Solution. L'un d'eux (ou les deux) doit être égal à zéro. Parce que, s'ils sont tous les deux positifs, la chaîne continuera à se déplacer entre 1 et 2 pour toujours. 10. Smith est en prison et a 3 dollars; il peut sortir sous caution s'il a 8 dollars. Un garde accepte de faire une série de paris avec lui. Si Smith parie un dollar, il gagne un dollar avec une probabilité de 0,4 et perd un dollar avec une probabilité de 0,6. Trouvez la probabilité qu'il gagne 8 dollars avant de perdre tout son argent si (a) il mise 1 dollar à chaque fois (stratégie timide). (b) il mise, à chaque fois, autant que possible mais pas plus que nécessaire pour porter sa fortune à 8 dollars (stratégie audacieuse). (c) Quelle stratégie donne à Smith les meilleures chances de sortir de prison? Solution. (a) La chaîne de Markov (Xn, n = 0,1, ...) représentant l’évolution de la monnaie de Smith a un diagramme 0.6

0.6

2

1

0 0.4

0.4

0.6

0.6

0.6

0.6

3

4

5

6

0.4

0.4

0.4

0.4

0.6

7

0.6

8 0.4

0.4

Soit ϕ (i) la probabilité que la chaîne atteigne l'état 8 avant d'atteindre l'état 0, à partir de l'état i. En d'autres termes, si Sj est le premier n ≥ 0 tel que Xn = j, ϕ (i) = Pi (S8