DM3 : Chaînes de Markov.

Maths Discrètes : DM 3

Énoncé

http://younesse.net/Maths-discretes/DM3/

Younesse Kaddar

EX 1

Pour une matrice $M∈ 𝕸_n(ℝ)$, on notera $𝜒_M$ son polynôme caractéristique.

1.

Soit $M∈𝒮_n(ℝ)$.

1. Soit $x∈ 𝕸_{n,1}(ℝ)\backslash \lbrace 0 \rbrace$ un vecteur propre de $M$ associé à une valeur propre $𝜆$ telle que $\vert 𝜆 \vert = 𝜌(M)$.

   \[𝜌(M) \vert\vert x \vert\vert = \vert\vert \underbrace{Mx}_{ = 𝜆 x} \vert\vert ≤ \vert\vert\vert M \vert\vert\vert \cdot \underbrace{\vert\vert x \vert\vert}_{≠0}\]

   donc

   \[𝜌(M) ≤ \vert\vert\vert M \vert\vert\vert\]

2. Comme $M$ est symétrique réelle : elle est diagonalisable dans une base orthonormée $(b_1, ⋯, b_n)$. On note $𝜆_1, ⋯, 𝜆_n$ ses valeurs propres réelles.

   Pour tout $x ≝ \sum\limits_{ i=1 }^n x_i b_i ∈ 𝕸_{n,1}(ℝ)\backslash \lbrace 0 \rbrace$ :

   \[\begin{align*} \vert\vert Mx \vert\vert^2 &= \vert\vert \sum\limits_{ i=1 }^n x_i M b_i \vert\vert^2 \\ &= \vert\vert \sum\limits_{ i=1 }^n x_i 𝜆_i b_i \vert\vert^2 \\ & = \sum\limits_{ 1≤i,j≤n } \underbrace{ 𝜆_i 𝜆_j }_{≤𝜌(M)^2} x_i x_j \underbrace{⟨b_i, b_j⟩}_{ = \substack{0 \text{ si } i≠j \\ 1 \text{ sinon }}} \\ & ≤ 𝜌(M)^2 \underbrace{\sum\limits_{ i=1 }^n x_i^2}_{= \vert\vert x \vert\vert^2} \\ \end{align*}\]

   donc : $∀ x ∈ 𝕸_{n,1}(ℝ)\backslash \lbrace 0 \rbrace$,

   \[\frac{\vert\vert Mx \vert\vert}{\vert\vert x \vert\vert} ≤ 𝜌(M)\]

   et

   \[\vert\vert\vert M \vert\vert\vert ≤ 𝜌(M)\]

On a donc montré que :

\[∀M∈𝒮_n(ℝ), \, \, 𝜌(M) = \vert\vert\vert M \vert\vert\vert\]

2.

a).

\[\begin{align*} H & ≝ \left\lbrace v ≝ \sum\limits_{ i=1 }^n \underbrace{v_i}_{ = ⟨v, e_i⟩} e_i ∈ ℝ^n ; \sum\limits_{ i=1 }^n v_i = 0 \right\rbrace \\ & = \left\lbrace v ∈ ℝ^n ; \sum\limits_{ i=1 }^n ⟨v, e_i⟩ = 0 \right\rbrace \\ & = \left\lbrace v ∈ ℝ^n ; \left\langle v, \sum\limits_{ i=1 }^n e_i \right\rangle = 0 \right\rbrace \\ \end{align*}\]

Et

\[H = \lbrace v ∈ ℝ^n ; ⟨v, \mathbf{1}⟩ = 0 \rbrace\]

b).

On note $u$ l’application linéaire canoniquement associée à $M$.

Par hypothèse, $M$ n’a qu’une seule valeur propre $𝜆_1$ de module $1$, laquelle est de multiplicité $1$. Or, $M$ est stochastique : $1$ est donc valeur propre de $M$ ( et $\mathbf{1}$ en est un vecteur propre associé).

Par suite :

\[𝜆_1 = 1\]

Comme $𝜆_1$ est de multiplicité $1$ :

\[E_{𝜆_1} ≝ {\rm Ker}(M - 𝜆_1 Id) = ⟨\mathbf{1}⟩\]

Par ailleurs, $H = ⟨\mathbf{1}⟩^{\bot}$ est stable par $M$

• en effet : $∀x, y ∈ 𝕸_{n,1}(ℝ)$,

  \[⟨Mx,y⟩ = \, ^{t}(Mx)y = \, ^{t}x(^{t}My) = ⟨x,\,^{t}My⟩ = ⟨x,My⟩\]

  d’où : si $x∈ H= ⟨\mathbf{1}⟩^{\bot}$,

  \[⟨Mx, \mathbf{1}⟩ = ⟨x, M\mathbf{1}⟩ = ⟨x, \mathbf{1}⟩ = 0\]

  et $Mx ∈⟨\mathbf{1}⟩^{\bot} = H$

Par suite : si on complète $(\mathbf{1})$ en une base orthonormale $(\mathbf{1}, b_2, ⋯, b_n)$, la matrice de $u$ dans la base $(\mathbf{1}, b_2, ⋯, b_n)$ est de la forme :

\[M' ≝ \begin{pmatrix} 1 & 0 & ⋯ & 0 \\ 0 & & & \\ \vdots & & Q & \\ 0 & & & \\ \end{pmatrix}\]

où $Q ∈ 𝕸_{n-1}(ℝ)$

et comme $(\mathbf{1}, b_2, ⋯, b_n)$ est orthonormale et $u$ symétrique, $M’∈𝒮_n(R)$, d’où

\[Q ∈ 𝒮_{n-1}(ℝ)\]

Enfin, en notant $P$ la matrice qui passe de la base $(\mathbf{1}, b_2, ⋯, b_n)$ à la base canonique :

\[M = P^{-1}M'P\]

et comme $P$ envoie une base orthonormée sur une base orthonormée : $P∈O_n(ℝ)$, et :

\[M = \, {}^tPM'P\]

En outre, comme $𝜒_Q = \frac{𝜒_M}{(X-1)}$ :

\[Sp(Q) = \lbrace 𝜆_2, ⋯, 𝜆_n \rbrace\]

et

\[𝜌(Q) = \vert 𝜆_2 \vert\]

par hypothèse sur les modules des valeurs propres de $M$.

On a donc montré que :

\[M = \, {}^t P \begin{pmatrix} 1 & 0 & ⋯ & 0 \\ 0 & & & \\ \vdots & & Q & \\ 0 & & & \\ \end{pmatrix}P\]

où

• $P∈O_n(ℝ)$
• $Q ∈ 𝒮_{n-1}(ℝ)$
• $𝜌(Q) = \vert 𝜆_2 \vert$

c).

Comme : $∀k∈ℕ$,

\[M^k = \, {}^t P \begin{pmatrix} 1 & 0 & ⋯ & 0 \\ 0 & & & \\ \vdots & & Q^k & \\ 0 & & & \\ \end{pmatrix}P\]

et $Q^k \xrightarrow[k \to +∞]{} 0$ (puique $𝜌(Q) = \vert 𝜆_2 \vert < \vert 𝜆_1 \vert = 1$),

il vient que la suite $(M^k)_{k∈ℕ}$ est convergente de limite

\[L ≝ \, {}^t P \begin{pmatrix} 1 & 0 & ⋯ & 0 \\ 0 & & & \\ \vdots & & 0 & \\ 0 & & & \\ \end{pmatrix}P\]

et, par suite, $L$ est de rang $1$.

Par ailleurs : pour tout $k∈ℕ$,

\[M^k-L= \, {}^t P \underbrace{\begin{pmatrix} 0 & 0 & ⋯ & 0 \\ 0 & & & \\ \vdots & & Q^k & \\ 0 & & & \\ \end{pmatrix}}_\text{notée $M'_k$} P\]

et

\[Sp(M^k-L) = \lbrace 0 \rbrace ∪ Sp(Q^k)\]

d’où

\[\begin{align*} 𝜌(M^k-L) & = 𝜌(Q^k) \\ & = 𝜌(Q)^k &&\text{(trigonalisation de $Q$)} \\ & = \vert 𝜆_2 \vert^k \end{align*}\]

et comme une puissance de matrices symétriques est symétrique : $\underbrace{M^k}{∈ 𝒮_n(ℝ)}-\underbrace{L}{∈ 𝒮_n(ℝ)} ∈ 𝒮_n(ℝ)$, et

\[\vert\vert\vert M^k-L \vert\vert\vert = 𝜌(M^k-L) = \vert 𝜆_2 \vert^k\]

par I.1).

On a donc montré que :

$(M^k)_{k∈ℕ}$ est convergente de limite $L$ de rang $1$, et $∀k∈ℕ$ :

\[\vert\vert\vert M^k-L \vert\vert\vert ≤ \vert 𝜆_2 \vert^k\]

d).

Comme :

• $𝒮_n(ℝ)$ est fermé (en tant que sous-espace vectoriel de $𝕸_n(ℝ)$)
• l’ensemble $S ⊆ 𝕸_n(ℝ)$ des matrices stochastiques est fermé
  • car une limite, pour la norme infinie, de suite de matrices stochastiques le reste (convergence coordonnée par coordonnée), par conservation des inégalités larges, et on conclut par équivalence des normes en dimension finie.

donc $S∩𝒮_n(ℝ)$ est fermé (en tant qu’intersection de fermés), et

\[L = \lim\limits_{k \to ∞} \underbrace{M^k}_{∈ S∩𝒮_n(ℝ)} ∈S∩𝒮_n(ℝ)\]

$L$ est donc stochastique et symétrique. Par la question qui précède :

\[L ≝ \, {}^t P \begin{pmatrix} 1 & 0 & ⋯ & 0 \\ 0 & & & \\ \vdots & & 0 & \\ 0 & & & \\ \end{pmatrix}P\]

3.

---

NB : Pour que $𝜆$ soit bien une loi de probabilité sur $S$, on comptera les boucles deux fois, dans la définition du degré d’un sommet.

---

Il est bien connu que la somme des degrés (où les boucles sont comptées deux fois) d’un graphe non orienté vaut deux fois son nombre d’arêtes (car lorsqu’on fait la somme des sommets, chaque arête est comptée deux fois).

C’est-à-dire :

\[\sum_s d_s = 2m\]

et

\[\sum_s 𝜆(s) = 1\]

: donc $𝜆$ est bien une loi de probabilité sur $S$

4.

On note $ℙ ≝ (p_{s,t})_{s,t∈S}$ la matrice de transition de la chaîne de Markov $𝒞$.

• $𝒞$ est irréductible car $G$ est connexe.

• De plus, comme $G$ est non orienté : $∀s,t ∈S$,

  \[p_{s,t} > 0 ⟺ p_{t,s} > 0\]

  Et par connexité de $G$ : pour tout sommet $s∈S$, il existe un sommet $t∈S$ tel que $p_{s,t}>0$ (et donc aussi $p_{t,s} > 0$, par ce qui précède).

  Il vient donc que : $∀s∈S$,

  \[[ℙ^2]_{s,s} = \sum\limits_{ t∈S } p_{s,t} p_{t,s} > 0\]

  et pour tout sommet $s∈S$ : il existe un cycle issu de $s$ de longueur inférieure à $2$, d’où la période de $𝒞$ divise $2$, et elle vaut donc $1$ ou $2$.

On a montré que :

$𝒞$ est une chaîne de Markov irréductible de période $1$ ou $2$.

5.

• Si le graphe est biparti, supposons, par l’absurde, que la période vaille $1$.

  Par la question précédente : pour tout sommet $s∈S$, il existe un cycle issu de $s$ de longueur inférieure à $2$. Comme la période vaut 1, il existe donc nécessairement un sommet admettant une boucle. Le graphe n’est donc pas biparti, puisque l’arête correspondante n’est pas adjacente à deux sommets appartenant à des ensembles disjoints.

• Réciproquement : montrons, par contraposée, que si $G$ n’est pas biparti, la période ne vaut pas $2$, c’est-à-dire $1$ (d’après la question précédente).

---

Lemme : Si tous les cycles d’un graphe connexe sont de longueur paire, alors le graphe est biparti.

En effet :

On considère un arbre couvrant enraciné du graphe, et on note $X$ (resp. $Y$) l’ensemble des sommets du graphes qui sont à une distance (nombre d’arêtes) paire (resp. impaire) de la racine.

Comme l’arbre est couvrant, $X$ et $Y$ partitionnent l’ensemble des sommets du graphe.

De plus, il ne peut y avoir d’arête du graphe adjacente à deux sommets appartenant à $X$ (ou à $Y$, mais disons $X$, sans perte de généralité) : car sinon, en notant $(s,t)$ (où $s, t∈X$) une telle arête, le chemin reliant $s$ à $t$ dans l’arbre couvrant (en passant par la racine) est de longueur paire par hypothèse, et en ajoutant l’arête $(s,t)$ à ce chemin, on obtient un cycle de longueur impaire, ce qui est absurde.

---

Supposons que $G$ n’est pas biparti. D’après la contraposée du lemme : il existe un cycle de longueur impaire.

D’après la question précédente, ce cycle est donc de longueur $1$, et la période de $𝒞$ vaut donc $1$.

On a montré que :

La période de $𝒞$ vaut $2$ si et seulement si $G$ est biparti.

6.

\[ℙ ≝ \left(\frac{\mathbb{1}_{(i,j)∈A}}{d_i}\right)_{i,j∈S}\]

où $\mathbb{1}_{(i,j)∈A} ≝ \begin{cases} 1 \text{ si } (i,j)∈A
0 \text{ sinon} \end{cases}$

On notera que $ℙ$ est bien irréductible (puisque $𝒞$ l’est) et stochastique, puisque : $∀i∈S$,

\[\sum_{j∈S} \frac{\mathbb{1}_{(i,j)∈A}}{d_i} = \frac{1}{d_i} \underbrace{\sum_{j∈S} \mathbb{1}_{(i,j)∈A}}_{≝ d_i} = 1\]

7.

$∀i, j∈S$,

\[\begin{align*} 𝜆(i) p_{i,j} & = \frac{d_i}{2m} \frac{\mathbb{1}_{(i,j)∈A}}{d_i} \\ & = \frac{d_j}{2m} \frac{\mathbb{1}_{(j,i)∈A}}{d_j} &&\text{(car $G$ est non orienté)}\\ & = 𝜆(j) p_{j,i} \end{align*}\]

Donc $∀j∈S$ :

\[[𝜆ℙ]_j = \sum_{i∈S} 𝜆(i) p_{i,j} = 𝜆(j) \underbrace{\sum_{i∈S} p_{j,i}}_{= 1} = 𝜆(j)\]

d’où :

\[𝜆ℙ = 𝜆\]

et $𝜆$ est une loi stationnaire pour $𝒞$.

8.

$ℙ$ est donc maintenant apériodique et symétrique, puisque : $∀i, j∈S$,

\[p_{i,j} = \frac{\mathbb{1}_{(i,j)∈A}}{d} = \frac{\mathbb{1}_{(j,i)∈A}}{d} = p_{j,i}\]

comme le graphe est non orienté.

De plus, d’après le cours : comme $ℙ$ est irréductible et apériodique, toutes ses valeurs propres sont de module inférieur à $1$, et $1$ est l’unique valeur propre de module $1$ ($\mathbf{1}$ en est un vecteur propre associé).

Les hypothèses de I.2) sont donc maintenant vérifiées.

Par ailleurs : comme $ℙ$ est irréductible et apériodique, il vient, d’après le cours, que la chaîne de Markov converge en loi vers un unique vecteur de loi stationnaire : d’après la question précédente, il s’agit donc de $𝜆$.

Or : le vecteur de loi stationnaire $𝜆$ est une loi uniforme sur $S$, puisque : $∀s∈S$,

\[𝜆(s) = \frac{d_s}{2m} = \frac{d_s}{\sum_{t∈S}d_t} = \frac{d}{\sum_{t∈S}d} = \frac{1}{\vert S \vert}\]

On a donc montré que

La chaîne de Markov converge en loi vers la loi uniforme sur $S$

De plus, par I.2)c) :

cette convergence est au moins géométrique.

9.

a).

Pour une permutation $𝜎$, échanger un élément $i∈⟦1,p⟧$ avec le premier consiste à composer $𝜎$ à droite par la transposition (si $i≠1$) ou l’identité (si $i=1$) : $(1,i)$

Donc le voisinage de $𝜎$ dans le graphe est l’ensemble des permutations $𝜎(1,i)$ pour $i∈⟦1,p⟧$ (pour $i=1$ : il s’agit de $𝜎$).

b).

On note $𝒞$ la chaîne de Markov considérée, $G$ son graphe associé, $ℙ$ sa matrice de transition.

Les hypothèses de I.8) sont vérifiées, puisque :

• $G$ est fini est non orienté, pusique si $𝜎(1,i) = 𝜎’$, alors $𝜎’(1,i) = 𝜎$

• le voisinage de chaque permutation $𝜎$ est de cardinal constant égal à $p$ : donc $d=p+1$ (la boucle est comptée deux fois), avec les notations précédentes, et $G$ est régulier.

• $G$ est connexe puisque $\lbrace (1,i) \rbrace_{i∈⟦1,p⟧}$ engendre $𝕾_p$ :

  • en effet : pour toute transposition $(i,j)$ (avec $i,j ∈⟦1,p⟧$) :

    \[(i,j) = (1,i)(1,j)(1,i)\]

    et les transpositions engendrent $𝕾_p$

  donc si $𝜎 ≝ (1,i_1) ⋯ (1, i_r)$ et $𝜎’ ≝ (1,j_1) ⋯ (1, j)$, le chemin

  \[𝜎 \overset{(1,i_r)}{⟶} ⋯ \overset{(1,i_1)}{⟶} id \overset{(1,j_1)}{⟶} ⋯ \overset{(1,j_s)}{⟶}𝜎'\]

  relie $𝜎$ à $𝜎’$

• pour chaque sommet, le graphe admet une boucle, donc il est apériodique

Il vient donc, d’après I.8), que

la chaîne de Markov converge en loi vers la loi uniforme sur $𝕾_p$

c).

Ultimement, le mélange du jeu de cartes correspond à une permutation choisie de manière uniforme dans $𝕾_p$ :

il est donc “idéal”, dans le sens où aucune permutation de $𝕾_p$ n’est privilégiée ultimement, quelle que soit la permutation de départ.

10.

a).

On utilise toujours les notations précédentes.

Les états de $S$ sont maintenant des $n$-uplets de $\lbrace 0,1 \rbrace^n$ comportant exactement $m$ uns, $n-m$ zéros : les cases correspondant aux coordonnées des $n$-uplets, et une coordonnée valant $1$ indiquant la présence d’une particule, une coordonnée valant $0$ en indiquant l’absence.

---

Voisinage d’un sommet $e ≝ (𝜀_1, ⋯, 𝜀_n) ∈ S$ :

Pour tout $e ≝ (𝜀_1, ⋯, 𝜀_n) ∈ S$, où il existe $i_1, ⋯, i_m∈ ⟦1, n⟧$ tels que

\[\begin{cases} ∀k∈⟦1, m⟧, \, \, 𝜀_{i_k} = 1\\ ∀j∈⟦1, n⟧\backslash \lbrace i_1, ⋯, i_m \rbrace, \, \, 𝜀_{j} = 0 \end{cases}\]

et pour tout $e’ ≝ (𝜀’_1, ⋯, 𝜀’_n) ∈ S$ tel qu’il existe $j∈ ⟦1, n⟧\backslash \lbrace i_1, ⋯, i_m \rbrace$ tel que

\[\begin{cases} 𝜀'_i ≝ 𝜀_j = 0 ∧ 𝜀'_j ≝ 𝜀_i = 1 \\ ∀k∈⟦1, n⟧\backslash \lbrace i, j \rbrace, \, \, 𝜀'_{k} = 𝜀_k \end{cases}\]

• où

  • $i ≝ j-\min \Big\lbrace k∈⟦1,n⟧ \mid (j-k) \mod n ∈ \lbrace i_1, ⋯, i_m \rbrace\Big\rbrace$

    ou

  • $i ≝ j+\min \Big\lbrace k∈⟦1,n⟧ \mid (j+k) \mod n ∈ \lbrace i_1, ⋯, i_m \rbrace\Big\rbrace$

alors

\[\begin{cases} (e, e')∈A \\ p_{e,e'} = \frac{1}{2n} \end{cases}\]

• En effet, pour de tels $e, e’∈S$ :

  si la case $j∈⟦1, n⟧\backslash \lbrace i_1, ⋯, i_m \rbrace$ est choisie (de façon uniforme, donc avec une probabilité égale à $\frac{1}{n}$) : comme elle est vide, la case peut se remplir de manière équiprobable (donc avec une probabilité égale à $\frac 1 2 \frac{1}{n}$) :

  • soit par la particule d’avant la plus proche : celle dans la case $i ≝ j-\min \Big\lbrace k∈⟦1,n⟧ \mid (j-k) \mod n ∈ \lbrace i_1, ⋯, i_m \rbrace\Big\rbrace$

  • soit par la particule d’après la plus proche : celle dans la case $i ≝ j+\min \Big\lbrace k∈⟦1,n⟧ \mid (j+k) \mod n ∈ \lbrace i_1, ⋯, i_m \rbrace\Big\rbrace$

  Toutes les autres cases, d’indice $k∈⟦1, n⟧\backslash \lbrace i, j \rbrace$, restant inchangées.

---

De plus, si une case choisie de façon uniforme est pleine (cela se produit avec une probabilité égale à $\frac{m}{n}$), l’état global du système reste inchangé, ce qui se traduit par :

\[∀e∈S, \begin{cases} (e, e)∈A \\ p_{e,e} = \frac{m}{n} \end{cases}\]

---

Réciproquement : on obtient toutes les arêtes de l’une des deux manières précédentes, par construction.

Par exemple, pour se fixer les idées, avec $n≝6$, $m ≝ 3$, $e ≝ (0, 1, 0, 1 , 1, 0)$ :

  graph {
    graph [autosize=false, size="10.,7.9"];
    a[label="(0, 1, 0, 1 , 1, 0)"];
    subgraph cluster_1 {
      label="# j = 1      /      ' i ∈ {5, 2}";
      a1d[label="(#1, '0, 0, 1 , 1, 0)"];
      a1g[label="(#1, 1, 0, 1, '0, 0)"];
    }

    subgraph cluster_2 {
      label="# j = 3      /      ' i ∈ {2, 4}";
      a3g[label="(0, '0, #1, 1, 1, 0)"];
      a3d[label="(0, 1, #1, '0, 1, 0)"];
    }

    subgraph cluster_3 {
      label="# j = 5      /      ' i ∈ {5, 2}";
      a4g[label="(0, 1, 0, 1, '0, #1)"];
      a4d[label="(0, '0, 0, 1 , 1, #1)"];
    }

    a -- a[label="m/n"];
    a -- a1g[label="1/(2n)", color=red];
    a -- a1d[label="1/(2n)", color=red];
    a -- a3g[label="1/(2n)", color=blue];
    a -- a3d[label="1/(2n)", color=blue];
    a -- a4g[label="1/(2n)", color=green];
    a -- a4d[label="1/(2n)", color=green];
  }

b).

Les hypothèses de I.8) sont vérifiées, puisque :

• $G$ est fini est non orienté, car rien n’empêche une particule de faire le déplacement inverse de celui qu’elle vient de faire (puisque qu’elle a laissé la case d’où elle vient vide), et ce avec la même probabilité $\frac{1}{2n}$.

• le voisinage de chaque permutation $𝜎$ est de cardinal constant égal à $1 + 2(n-m)$ : donc $d=2(n-m+1)$ (la boulce est comptée deux fois), avec les notations précédentes, et $G$ est régulier.

• $G$ est connexe puisque, pour construire un chemin de $e ≝ (𝜀_1, ⋯, 𝜀_n)$ à $e’ ≝ (𝜀’_1, ⋯, 𝜀’_n)∈ S$, l’algorithme glouton naïf qui consiste à remplir la première case de $e$ ou $e’$ qui est vide dans ce sommet, mais pleine dans l’autre sommet, par la particule d’après la plus proche, est trivialement correct, et termine. En effet, en notant $k$ l’indice de la première case qui est vide dans un sommet mais pleine dans l’autre, l’invariant “à la fin de l’étape $i$ (de l’algorithme), les $(k-1)+i$ premières cases de $e$ et $e’$ sont dans le même état” est toujours vérifié (on le montre par une récurrence immédiate).

• pour chaque sommet, le graphe admet une boucle, donc il est apériodique

Il vient donc, d’après I.8), que

la chaîne de Markov converge en loi vers la loi uniforme sur $S$.

Or, $S$ est l’ensemble des $n$-uplet de $\lbrace 0,1 \rbrace^n$ comportant exactement $m$ uns, $n-m$ zéros :

\[\vert S \vert \overset{\text{donc}}{ = } \binom{n}{m}\]

et

la limite lorsque $k$ tend vers $+∞$ de la probabilité qu’une case particulière soit occupée par une particule après $k$ étapes vaut

\[\frac{1}{\vert S \vert} = \frac{1}{\binom{n}{m}}\]

EX 2

1.

Montrons que $L ≝ \lbrace s ∈ S, ∆(s) = 0\rbrace$ est exactement l’ensemble des états récurrents de $G$.

---

Tout élément de $s∈L$ est récurrent.

En effet :

• Pour tout $s’∈S$ tel que $s⟶s’$,

  \[0=∆(s)≥∆(s')\overset{\text{donc}}{=} 0\]

  et $s’∈L$

  Donc la composante fortement connexe à laquelle appartient $s$ est finale.

• Par récurrence sur $∆(s’)$ : pour tout $s’∈S$, il existe chemin de $s’$ à un élément de $L$.

  • Initialisation : Pour $∆(s’) = 0$, c’est immédiat.

  • Hérédité : Si $∆(s’) > 0$ : il existe un chemin fini $s ⟶ s_1 ⋯ ⟶ s_p$ tel que $∆(s) > ∆(s_p)$, et le résultat est acquis en appliquant l’hypothèse de récurrence à $s_p$ et en concaténant les chemins.

Tout élément récurrent $s$ appartient à $L$.

En effet :

Par l’absurde, si ce n’était pas le cas : $∆(s) > 0$, et comme on l’a montré précédemment, il existe un chemin de $s$ à un élément $s’∈L$. Or, la composant fortement connexe à laquelle appartient $s$ est finale (pusique $s$ est récurrent), donc $s$ et $s’$ sont dans la même composante connexe. Par conséquent, il existe un chemin fini $s’ ⟶ s_1 ⋯ ⟶ s_p ⟶ s$, et

\[0 = ∆(s') ≥ ∆(s_1) ≥ ⋯ ≥ ∆(s_p) ≥ ∆(s) > 0\]

ce qui est absurde.

---

Il vient donc, d’après le cours, que :

\[\lim_{k→+∞} P(X_k ∈L) = 1\]

2.

a).

Pour tout état $s∈S$, on note $∆(s)$ le nombre de jetons de $s$ moins un.

Montrons que les trois hypothèse faites sur $∆$ dans l’énoncé sont vérifiées :

i). $∆$ prend la valeur $0$

En effet : il y a au départ un nombre impair de jetons, disons $2k+1$, et à chaque étape, le nombre de jetons peut, avec des probabilités strictement positives :

• soit rester le même
• soit diminuer de 2

La probabilité qu’il diminue $k$ fois consécutivement de 2, reste donc strictement positive, et mène à un état légitime, en lequel $∆$ s’annule.

ii). $∀s, t ∈ S$, s’il y a une transition de $s$ vers $t$, alors $∆(t) ≤ ∆(s)$

En effet : comme rappelé précédemment, le nombre de jetons ne peut que diminuer à chaque étape.

iii). $∀s ∈ S$, si $∆(s) > 0$, il existe un chemin fini $s ⟶ s_1 ⋯ ⟶ s_p$ tel que $∆(s_p) < ∆(s)$

En effet : s’il y a au moins deux jetons, en faisant se déplacer un jeton (toujours le même) dans le sens des aiguilles d’une montre, il finira par en percuter un autre en moins de $N-1$ étapes, et $∆$ diminuera alors strictement (puisque les deux jetons s’étant percutés disparaîtront).

---

Donc en appliquant II.1), on en déduit que

cet algorithme est auto-stabilisant.

b).

On procède de la même manière que précédemment, avec la même fonction $∆$, puisqu’à l’issue d’une étape, le nombre de jetons :

• soit reste inchangé
• soit diminue de 1 (fusion de deux jetons)

Toutes les preuves sont identiques, puisqu’il y a une probabilité non nulle à chaque étape que le nombre de jetons diminue strictement.

Cet algorithme est aussi auto-stabilisant.

EX 3

On utilisera les notations des exercices précédents.

1.

Un état du jeu est défini par la distance (en nombre de personne intermédiaires) séparant les deux joueurs courants :

\[S = ⟦0, N⟧\]

• $0$ est clairement absorbant

  • il suffit que les deux joueurs courants obtiennent tout le temps des $6$ (ou tout le temps des $1$) pour atteindre $0$, et comme le jeu s’arrête alors : on reste dès lors dans cet état.

• $N$ correspond à une situation où les deux joueurs courants sont diamétralement opposés : si $n > 1$ :

  • \[P(X_n = N-2 \mid X_{n−1} = N) = 2 \times \frac 1 6 \frac 1 6 = \frac{1}{18}\]

    (un joueur a tiré un $6$ et l’autre un $1$)

  • \[P(X_n = N-1 \mid X_{n−1} = N) = 2 \times \frac 2 6 \cdot \frac 4 6 = \frac{4}{9}\]

    (le premier joueur a tiré un $6$ ou un $1$, le second ni un $1$, ni un $6$ (et idem pour le deuxième joueur))

  • \[P(X_n = N \mid X_{n−1} = N) = \frac 4 6 \cdot \frac 4 6 + 2 \times \frac 1 6 \frac 1 6 = \frac{1}{2}\]

    (les deux joueurs ont tiré un chiffre entre $2$ et $5$, ou les deux ont tiré un $1$, ou les deux ont tiré un $6$)

• Pour $N-1$, si $n > 1$ :

  • \[P(X_n = N-3 \mid X_{n−1} = N-1) = \frac 1 6 \cdot \frac 1 6 = \frac{1}{36}\]

    (si le premier joueur est désaxé vers la droite (resp. gauche) par rapport au deuxième joueur : le joueur 1 tire un $1$ (resp. $6$), le joueur 2 un $6$ (resp. $1$))

  • \[P(X_n = N-2 \mid X_{n−1} = N-1) = 2 \times \frac 1 6 \cdot \frac 4 6 = \frac{2}{9}\]

    (si le premier joueur est désaxé vers la droite (resp. gauche) par rapport au deuxième joueur : le joueur a tiré un $1$ (resp. un $6$), le second ni un $1$, ni un $6$ (et idem pour le deuxième joueur))

  • \[P(X_n = N-1 \mid X_{n−1} = N-1) = \frac 4 6 \cdot \frac 4 6 + 2 \times \frac 1 6 + \frac 1 6 \cdot \frac 1 6 = \frac{19}{36}\]

    (les deux joueurs ont tiré un chiffre entre $2$ et $5$, ou les deux ont tiré un $6$, ou les deux ont tiré un $1$, OU : si le premier joueur est désaxé vers la droite (resp. gauche) par rapport au deuxième joueur : le joueur 1 tire un $6$ (resp. $1$), le joueur 2 un $1$ (resp. $6$))

  • \[P(X_n = N \mid X_{n−1} = N-1) = 2 \times \frac 1 6 \cdot \frac 4 6 = \frac{2}{9}\]

    (si le premier joueur est désaxé vers la droite (resp. gauche) par rapport au deuxième joueur : le joueur a tiré un $6$ (resp. un $1$), le second ni un $1$, ni un $6$ (et idem pour le deuxième joueur))

• Pour $1$, si $n > 1$ :

  • \[P(X_n = 0 \mid X_{n−1} = 1) = 2 \times \frac 1 6 \cdot \frac 4 6 = \frac{2}{9}\]

    (si le premier joueur a le deuxième à sa droite (resp. gauche) : le joueur 1 a tiré un $1$ (resp. un $6$), le second ni un $1$, ni un $6$ (et idem pour le deuxième joueur))

  • \[P(X_n = 1 \mid X_{n−1} = 1) = \frac 4 6 \cdot \frac 4 6 + 2 \times \frac 1 6 + \frac 1 6 \cdot \frac 1 6 = \frac{19}{36}\]

    (les deux joueurs ont tiré un chiffre entre $2$ et $5$, ou les deux ont tiré un $6$, ou les deux ont tiré un $1$, OU : si le premier joueur a le second à sa droite (resp. gauche) : le joueur 1 tire un $1$ (resp. $6$), le joueur 2 un $6$ (resp. $1$))

  • \[P(X_n = 2 \mid X_{n−1} = 1) = 2 \times \frac 1 6 \cdot \frac 4 6 = \frac{2}{9}\]

    (si le premier joueur a le deuxième à sa droite (resp. gauche) : le joueur a tiré un $6$ (resp. un $1$), le second ni un $1$, ni un $6$ (et idem pour le deuxième joueur))

  • \[P(X_n = 3 \mid X_{n−1} = 1) = \frac 1 6 \cdot \frac 1 6 = \frac{1}{36}\]

    (si le premier a le deuxième à sa droite (resp. gauche) : le joueur 1 tire un $6$ (resp. $1$), le joueur 2 un $1$ (resp. $6$))

• Pour tout $k∈⟦2,N-2⟧$, si $n > 1$, et sachant que par “le joueur 1 a le joueur 2 à sa droite (resp. sa gauche)”, on entend “le plus court chemin allant du joueur 1 vers le joueur 2 est à la droite du joueur 1” :

  • \[P(X_n = k-2 \mid X_{n−1} = k) = \frac 1 6 \cdot \frac 1 6 = \frac{1}{36}\]

    (si le premier joueur a le second à sa droite (resp. gauche) : le joueur 1 tire un $1$ (resp. $6$), le joueur 2 un $6$ (resp. $1$))

  • \[P(X_n = k-1 \mid X_{n−1} = k) = 2 \times \frac 1 6 \cdot \frac 4 6 = \frac{2}{9}\]

    (si le premier joueur a le deuxième à sa droite (resp. gauche) : le joueur 1 a tiré un $1$ (resp. un $6$), le second ni un $1$, ni un $6$ (et idem pour le deuxième joueur))

  • \[P(X_n = k \mid X_{n−1} = k) = \frac 4 6 \cdot \frac 4 6 + 2 \times \frac 1 6 = \frac{1}{2}\]

    (les deux joueurs ont tiré un chiffre entre $2$ et $5$, ou les deux ont tiré un $6$, ou les deux ont tiré un $1$)

  • \[P(X_n = k+1 \mid X_{n−1} = k) = 2 \times \frac 1 6 \cdot \frac 4 6 = \frac{2}{9}\]

    (si le premier joueur a le deuxième à sa droite (resp. gauche) : le joueur 1 a tiré un $6$ (resp. un $1$), le second ni un $1$, ni un $6$ (et idem pour le deuxième joueur))

  • \[P(X_n = k+2 \mid X_{n−1} = k) = \frac 1 6 \cdot \frac 1 6 = \frac{1}{36}\]

    (si le premier a le deuxième à sa droite (resp. gauche) : le joueur 1 tire un $6$ (resp. $1$), le joueur 2 un $1$ (resp. $6$))

\[ℙ = \begin{pmatrix} 1 & 0 & & & ⋯ & & & & & & & 0\\ 2/9 & 19/36 & 2/9 & 1/36 & 0 & ⋯ & & & & & & 0\\ 1/36 & 2/9 & 1/2 & 2/9 & 1/36 & 0 & ⋯ & & & & & 0\\ 0 & 1/36 & 2/9 & 1/2 & 2/9 & 1/36 & 0 & ⋯ & & & & 0\\ 0 & 0 & 1/36 & 2/9 & 1/2 & 2/9 & 1/36 & 0 & ⋯ & & & 0 \\ 0 & ⋯ & 0 & \ddots & \ddots & \ddots & \ddots & \ddots & 0 & ⋯ & & 0 \\ 0 & & ⋯ & 0 & \ddots & \ddots & \ddots & \ddots & \ddots & 0 & ⋯ & 0 \\ 0 & & & ⋯ & 0 & \ddots & \ddots & \ddots & \ddots & \ddots & ⋯ & 0 \\ 0 & & & & ⋯ & 0 & \ddots & \ddots & \ddots & \ddots & \ddots & 0 \\ 0 & & & & & ⋯ & 0 & 1/36 & 2/9 & 1/2 & 2/9 & 1/36 \\ 0 & & & & & & ⋯ & 0 & 1/36 & 2/9 & 19/36 & 2/9 \\ 0 & & & & & & & ⋯ & 0 & 1/18 & 4/9 & 1/2 \\ \end{pmatrix}\]

2.

D’après le cours, comme la chaîne de Markov est absorbante, d’unique état absorbant $0$ :

\[\lim_{n→+∞} P(X_n = 0) = 1\]

et la partie s’arrête presque sûrement.

3.

Comme la chaîne de Markov est absorbante, d’état absorbant $0$, d’après le dernier théorème du cours :

$(E(T_i))_{i≠0}$ est l’unique solution du système linéaire

\[X = \mathbf{1} + QX\]

d’inconnue $X∈ 𝕸_{n,1}(ℝ)$, où :

\[Q ≝ \begin{pmatrix} 19/36 & 2/9 & 1/36 & 0 & ⋯ & & & & & & 0\\ 2/9 & 1/2 & 2/9 & 1/36 & 0 & ⋯ & & & & & 0\\ 1/36 & 2/9 & 1/2 & 2/9 & 1/36 & 0 & ⋯ & & & & 0\\ 0 & 1/36 & 2/9 & 1/2 & 2/9 & 1/36 & 0 & ⋯ & & & 0 \\ 0 & ⋯ & \ddots & \ddots & \ddots & \ddots & \ddots & 0 & ⋯ & & 0 \\ 0 & ⋯ & 0 & \ddots & \ddots & \ddots & \ddots & \ddots & 0 & ⋯ & 0 \\ 0 & & ⋯ & 0 & \ddots & \ddots & \ddots & \ddots & \ddots & ⋯ & 0 \\ 0 & & & ⋯ & 0 & \ddots & \ddots & \ddots & \ddots & \ddots & 0 \\ 0 & & & & ⋯ & 0 & 1/36 & 2/9 & 1/2 & 2/9 & 1/36 \\ 0 & & & & & ⋯ & 0 & 1/36 & 2/9 & 19/36 & 2/9 \\ 0 & & & & & & ⋯ & 0 & 1/18 & 4/9 & 1/2 \\ \end{pmatrix}\]

Avec Sage :

N=25

def coeff_Q(i,j):
    if i==1 or i==N-1:
        if j==i:
            return 19/36
    if i==N:
        if j==N-2:
            return 1/18
        elif j==N-1:
            return 4/9            
    if j==i-2 or j==i+2:
        return 1/36
    elif j==i-1 or j==i+1:
        return 2/9
    elif j==i:
        return 1/2
    else:
        return 0

Q = matrix(QQ, N, N, lambda i,j: coeff_Q(i+1,j+1))

(matrix.identity(N)-Q).solve_right(vector([1 for _ in range(N)])).n()

retourne

(90.3558653543692, 159.153077165047, 226.825093703903, 291.307716504657,
352.809471958264, 411.309294621438, 466.809312536095, 519.309310726347,
568.809310909169, 615.309310890700, 658.809310892566, 699.309310892378,
736.809310892397, 771.309310892395, 802.809310892395, 831.309310892395,
856.809310892395, 879.309310892395, 898.809310892395, 915.309310892395,
928.809310892395, 939.309310892395, 946.809310892395, 951.309310892395,
952.809310892395)

Donc le temps moyen d’une partie (on part de l’état $N$) vaut environ $952.809310892395$ ($\frac{3753196417875825}{3939084531364}$ pour être précis)

---

On peut le vérifier expérimentalement avec un petit script python :

from random import randint

def A_la_chasse(N):
    DeuxN = 2*N
    joueur1, joueur2 = 0, N-1
    compteur = 0

    def mouvement(nombre):
        if nombre == 1:
            return 1
        elif nombre == 6:
            return -1
        else:
            return 0

    while joueur1 != joueur2:
        mouv1, mouv2 = mouvement(randint(1,6)), mouvement(randint(1,6))
        if mouv1:
            joueur1=(joueur1+mouv1)%DeuxN
        if mouv2:
            joueur2=(joueur2+mouv2)%DeuxN
        compteur+=1

    return compteur


def Esperance(n,N):
    return sum(A_la_chasse(N) for _ in range(n))/n

⟶

>>> Esperance(100000,25)
953.86499

Ou en C (pour plus de vitesse) :

#include <time.h>
#include <stdlib.h>
#include <stdio.h>


int mouvement(int nombre){
    if (nombre == 1){
        return 1;
    }
    else if (nombre == 6)
    {
        return -1;
    }
    else
    {
        return 0;
    }
}


int A_la_chasse (int N) {

    int DeuxN = 2*N;
    int joueur1 = 0;
    int joueur2 = N-1;
    int compteur = 0;
    int mouv1, mouv2;

    while (joueur1 != joueur2)
    {
        mouv1 = mouvement(rand()%6+1);
        mouv2 = mouvement(rand()%6+1);

        if (mouv1)
            joueur1=(joueur1+mouv1)%DeuxN;
        if (mouv2)
            joueur2=(joueur2+mouv2)%DeuxN;

        compteur++;
    }
    return compteur;
}

double Esperance(int n, int N)
{
    unsigned long int sum = 0;

    srand((unsigned)time(NULL));

    for (int i = 0; i < n; i++)
    {
        sum += A_la_chasse(N);
    }

    return sum/n;
}

int main(){

    printf("%f \n", Esperance(1000000, 25));

    return 0;
}