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"];}
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"];
}
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"];
}
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