TD8 : Chaînes de Markov

EX 1

1.

digraph {
    1 -> 3[label="1/2"];
    1 -> 1[label="1/2"];
    2 -> 2[label="2/3"];
    2 -> 1[label="1/3"];
    3 -> 2[label="1/4"];
    3 -> 3[label="1/4"];
    3 -> 5[label="1/4"];
    3 -> 4[label="1/4"];
    4 -> 4[label="1/5"];
    4 -> 5[label="4/5"];}
S= \lbrace 1, 2, 3, 4, 5 \rbrace

2.

  • $1, 2, 3, 4$ : transients
  • $5$ : récurrent

3.

Elle vaut ℙ^4[1,5]=921/3200

Dans Sage :

P = matrix(QQ, [[1/2,0,1/2,0,0],[1/3,2/3,0,0,0],[0,1/4,1/4,1/4,1/4],[0,0,0,3/4,1/4], [0,0,0,1/5,4/5]])
P^4

retourne

[     41/288    199/1152      53/384    829/3200    921/3200]
[      23/81    737/2592     199/864      71/720      37/360]
[   199/1728    875/6912    169/2304    941/3000 17819/48000]
[          0           0           0 15849/32000 16151/32000]
[          0           0           0 16151/40000 23849/40000]



EX 2

1.

$q=1-p$

digraph {
        𝜀 -> P[label="p"];
        𝜀 -> F[label="q"];
        P -> PP[label="p^2"];
        P -> PF[label="pq"];
        P -> FP[label="pq"];
        F -> PP[label="p^2"];
        F -> PF[label="pq"];
        F -> FP[label="pq"];
        P -> FF[label="q^2"];
        F -> FF[label="q^2"];
        FF -> 𝜀[label="1"];
        PF -> PF[label="1"];
        FP -> FP[label="1"];
        PP -> PP[label="1"];       
	}

Dans cette question : $p=q=1/2$


P(\text{avoir un } k∈⟦1,6⟧) = \frac 1 8 + \frac 1 4 \frac 1 8 + \frac{1}{4^2} \frac 1 8 + ⋯ \\ = \frac 1 8 \sum_{k≥0} \frac{1}{4^k} \\ = \frac 1 8 \frac{1}{1-1/4} \\ = \frac 1 6

On note $X$ la v.a comptant le nombre de de jets de pièce pour une simulation, $Y$ celle qui compte le nombre de “tours” qu’on fait dans l’automate.

E(X) = \sum\limits_{k≥1} 3k P(\text{"faire $k$ tours"}) \\ = \sum\limits_{k≥1} 3k P(Y=k) \\

Or, par exemple :

P(Y=2) = P(\text{au 2e et 3e lancer, on fait FF}) = \frac 1 4

On remarque que

Y \leadsto 𝒢(3/4)

Donc

E(Y) = \frac{1}{3/4} = \frac 4 3

et

E(X) = 3 E(Y) = 4

2.

digraph {
        𝜀 -> P[label="p"];
        𝜀 -> F[label="q"];
        P -> PP[label="p^2"];
        P -> PF[label="pq"];
        P -> FP[label="pq"];
        F -> PP[label="p^2"];
        F -> PF[label="pq"];
        F -> FP[label="pq"];
        P -> FF[label="q^2"];
        F -> FF[label="q^2"];
        FF -> 𝜀[label="1"];
        PF -> PF[label="1"];
        FP -> FP[label="1"];
        PP -> 𝜀[label="1"];       
	}
P(\text{finir par FP ou PF }) = pq \sum_{k≥0} (p^2+q^2)^k \\ = pq \frac{1}{1-(p^2+q^2)} \\ = \frac 1 2

EX 3

Les sommets de notre graphe sont des états de l’automate cellulaire, i.e l’automate cellulaire où chaque pixel est coloré.

On remarque que :

  • les états monochromes sont récurrents.
  • pour tout état polychrome, il existe un algorithme pour le rendre monochrome (il suffit de colorer les pixels un par un, ligne par ligne, de gauche à droite), qui correspond à un chemin de probabilité non nulle dans le graphe de notre processus stochastique de cet état vers un état mononchrome récurrent.

    • cela montre que tous les états polychromes sont transients : car sinon, un état polychrome non transient serait (puisqu’on est coincé dans sa cfc) dans la même cfc qu’un état ploychrome (par la remarque précédente), ce qui impliquerait qu’il existerait réciproquement un chemin de cet état monochrome vers l’état polychrome de départ : absurde.

Donc par le théorème

Th : Soit $𝒞$ une cdM, $R⊆S$ , $R$ l’ensemble des états récurrents de $𝒞$.

Alors \lim_{n⟶+∞} P(X_n ∈R)=1

du cours ($R$ étant l’ensemble des états monochromes), le résultat est acquis.

EX 4

P(D_1(0,1)) = P(D_1(1,0)) = \frac 1 2

1.

X_n = X_0 + \sum_{i=1}^n D_i

Le graphe associé est un quadrillage dont chaque sommet est associé à un point de $ℤ/nℤ × ℤ/nℤ$.

$ℙ$ est la matrice dont tous les coeff. valent $\frac 1 2$.

Deux choses l’une :

  • $P(X_{n+1} =s \vert X_n = s_n, ⋯, X_0 = s_0) = P(X_{n+1}=s \vert X_n =s)$
  • $∀n, ∀p, P(X_{n+1} =s \vert X_n = s_n) = P(X_{p+1}=s \vert X_p =s)$

2.

La chaîne de Markov est irrédutible : tous les sommets sont dans la même cfc.

3.

Elle n’est apériodique que si $n=1$ : en effet, les cycles qui partent d’un sommet et y reviennent sont tous de longueur $n$ (on ne peut que monter ou aller à droite).

EX 5

1.

La proba vaut $\frac{N-i+1}{N}$

2.

N_i \leadsto 𝒢(1 - \frac{i-1}{N})

3.

E(N_i) = \frac{N}{N-i+1}

4.

N = \sum_i N_i

E(N) = \sum_{i=1}^N E(N_i) = N \sum_{i=1}^N \frac{1}{i} \sim N \ln N

5.

digraph {
        rankdir=LR;
        kplus[label="k+1"];
        rarekplus[label="k+1 rare"];
        Nmoins[label="N-1"];
        rareNmoins[label="N-1 rare"];
        ⋯2[label="⋯"];
        ⋯3[label="⋯"];
        ⋯4[label="⋯"];
		0 -> 1[label="1-𝜀"];
        0 -> rare1[label="𝜀"];
        1 -> 1[label="(1-𝜀)/(N-1)"];
        1 -> 2[label="1-(1-𝜀)/(N-1)-𝜀"];
        2 -> 2[label="2(1-𝜀)/(N-1)"];
        2 -> 3[label="1-2(1-𝜀)/(N-1)-𝜀"];
        3 -> 3[label="3(1-𝜀)/(N-1)"];
        3 -> ⋯;
        ⋯ -> k;
        k -> k[label="k(1-𝜀)/(N-1)"];
        k -> kplus[label="1-k(1-𝜀)/(N-1)-𝜀"];
        kplus -> ⋯2;
        ⋯2 -> Nmoins;
        Nmoins -> N[label="𝜀"];
        Nmoins -> Nmoins[label="1-𝜀"];
        rare1 -> rare1[label="𝜀"];
        rare1 -> rare2[label="1-𝜀"];
        rare2 -> rare2[label="1/(N-1)+𝜀"];
        rare2 -> rare3[label="1-1/(N-1)-𝜀"];
        rare3 -> rare3[label="2/(N-1)+𝜀"];
        rare3 -> ⋯3;
        ⋯3 -> rarek;
        rarek -> rarek[label="(k-1)/(N-1)+𝜀"];
        rarek -> rarekplus[label="1-(k-1)/(N-1)-𝜀"];
        rarekplus -> ⋯4;
        ⋯4 -> rareNmoins;
        rareNmoins -> N[label="(N-𝜀)/(N-1)"];
        rareNmoins -> rareNmoins[label="1-(N-𝜀)/(N-1)"];
        1 -> rare2[label="𝜀"];
        2 -> rare3[label="𝜀"];
        k -> rarek[label="𝜀"];
        kplus -> rarekplus[label="𝜀"];
	}

6.

$N_𝜀$ : la variable aléatoire comptant le nombre de boîtes achetées sachant qu’on a $𝜀$.

Calculer $P(B=k)$, puis : croissance de la proba.

EX 9.

1.

On suppose la matrice bistochastique.

$ℙ(p_{i,j})$

et

  • $∀i, \sum_j p_{i,j} = 1$
  • $∀j, \sum_i p_{i,j} = 1$

2.

$𝒞$ est irréductible et apériodique.

\lim_{k⟶+∞} ℙ^k = \begin{pmatrix} 𝜇 \\ \vdots \\ 𝜇 \end{pmatrix}

Comme $ℙ$ est bistochastique, par transposition : toutes les colonnes de $\lim_{k⟶+∞} ℙ^k$ sont aussi égales.

Donc

\lim_{k⟶+∞} ℙ^k = \begin{pmatrix} 1/s & ⋯ & 1/s \\ \vdots & \ddots & \vdots \\ 1/s & ⋯ & 1/s \end{pmatrix}

EX 10

1.

Pour $N=10$.

  digraph {
    0 -> 1[label="1/6"];
    0 -> 2[label="1/6"];
    0 -> 3[label="1/6"];
    0 -> 4[label="1/6"];
    0 -> 5[label="1/6"];
    0 -> 6[label="1/6"];    
    1 -> 1[label="1/6"];
    1 -> 2[label="1/6"];
    1 -> 3[label="1/6"];
    1 -> 4[label="1/6"];
    1 -> 5[label="1/6"];
    1 -> 6[label="1/6"];    
    1 -> 7[label="1/6"];
  }
ℙ = \begin{pmatrix} 0 & 1/6 & 1/6 & 1/6 & 1/6 & 1/6 & 1/6 & 0 & 0 & 0 & ⋯ & 0\\ 0 & 0 & 1/6 & 1/6 & 1/6 & 1/6 & 1/6 & 1/6 & 0 & 0 & ⋯ & 0\\ 0 & 0 & 0 & 1/6 & 1/6 & 1/6 & 1/6 & 1/6 & 1/6 & 0 & ⋯ & 0\\ 0 & 0 & 0 & 0 & 1/6 & 1/6 & 1/6 & 1/6 & 1/6 & 1/6 & ⋯ & 0\\ 0 & 0 & 0 & 0 & 0 & & & & \vdots & & & \\ & & & & & & & & \vdots & & & \\ 0 & 0 & 0 & 0 & 0 & ⋯ & 1/6 & 1/6 & 1/6 & 1/6 & 1/6 & 1/6 \\ & & & & & & & & \vdots & & & \\ 1/6 & 1/6 & 1/6 & 1/6 & 1/6 & 1/6 & 0 & 0 & ⋯ & 0\\ \end{pmatrix}

La matrice est bistochastique :

  • ça se voit sur la matrice
  • ça se voit aussi sur le graphe : la somme des probas des arêtes entrantes vaut 1.

Avec ça, on peut simuler une loi uniforme avec un dé.

Chaîne irréducible apériodique et bistochastique ⟶ permet de simuler, à l’infini, une loi uniforme.

Leave a comment