La fonction positions(n) renvoie la liste des positions de l’étape {0} à l’étape {n}.
from random import *
def positions(n):
pos = 1
listpos = [1]
for k in range(n):
if pos > 1: pos -= 1
else: pos = randint(2,4)
listpos.append(pos)
return listpos
On écrit ensuite une fonction trace(n) représentant la liste de ces positions :
import matplotlib.pyplot as plt
def trace(n):
listpos = positionsn)
plt.clf()
plt.plot(listpos,'o-')
plt.show()
Voici les tracés pour {n=10}, {n=50} et {n=100}:


On peut conjecturer que pour {n} « assez grand » : {\begin{array}{l}\mathbb{P}(X_n=4)\le \mathbb{P}(X_n=3)\\[6pts]\qquad\le \mathbb{P}(X_n=2)\le \mathbb{P}(X_n=1)\end{array}}On écrit frequences(d,n) donnant les fréquences pour {n} dates à partir de la date {d}.
def frequences(d,n):
listpos = positions(d+n-1)[d::]
freqs = [0]*4
for k in range(n):
freqs[listpos[k]-1] += 1
return [freqs[k]/n for k in range(4)]
Voici quelques résultats obtenus avec cette fonction
>>> frequences(0,1000)
[0.324, 0.323, 0.231, 0.122]
>>> frequences(0,10000)
[0.3353, 0.3352, 0.2211, 0.1084]
>>> frequences(1000,10000)
[0.3351, 0.3352, 0.2219, 0.1078]
On peut donc raisonnablement penser que: {\begin{array}{l}\displaystyle\lim_{n\to+\infty}\mathbb{P}(X_n=1)=\displaystyle\lim_{n\to+\infty}\mathbb{P}(X_n=2)=\dfrac{1}{3}\\\\\displaystyle\lim_{n\to+\infty}\mathbb{P}(X_n=3)=\dfrac{2}{9},\quad\displaystyle\lim_{n\to+\infty}\mathbb{P}(X_n=4)=\dfrac{1}{9}\end{array}}
On diagonalise {A}. On trouve :
{\begin{array}{rl}\chi_{A}(\lambda)&=\dfrac{1}{81}\begin{vmatrix}3\lambda&-3&0&0\\ -1&3\lambda&-3&0\\ -1&0&3\lambda&-3\\ -1&0&0&3\lambda\end{vmatrix}\\\\&=\lambda^4+\dfrac{1}{27}\begin{vmatrix}-1&-3&0\\-1&3\lambda&-3\\-1&0&3\lambda\end{vmatrix}\\\\&=\lambda^4+\dfrac{1}{27}(-9\lambda^2-9-9\lambda)\\\\&=\lambda^4-\dfrac{1}{3}(\lambda^2+\lambda+1)\end{array}}
NB: on peut trouver {\chi_{A}} plus vite, car c’est le déterminant d’une matrice-compagnon.
On ne trouve pas mieux que la factorisation : {\chi_{A}(\lambda)=\dfrac{1}{3}(\lambda-1)(3\lambda^3+3\lambda^2+2\lambda+1)}Le fait que {\lambda=1} soit valeur propre n’est pas étonnant ({A} est stochastique).
La matrice {A-I_3=\dfrac{1}{3}\begin{pmatrix}-3&3&0&0\\ 1&-3&3&0\\ 1&0&-3&3\\ 1&0&0&-3 \end{pmatrix}} est de rang {3}, donc {E_A(1)} est une droite.
Un vecteur directeur de {E_A(1)} est {\varepsilon_1=(3,3,2,1)}.
On finit la diagonalisation de {A} avec Python :
>>> A = np.array([[0,3,0,0],[1,0,3,0] [1,0,0,3],[1,0,0,0]])/3
>>> [a,b,c,d] = np.linalg.eigvals(A);
>>> np.round([a,b,c,d],5)
array([ 1.+0.j, -0.71806+0.j, -0.14097+0.66659j, -0.14097-0.66659j])
>>> np.abs([a,b,c,d]);
array([1., 0.71805717, 0.68133369, 0.68133369])
Il y a donc quatre valeurs propres distinctes :{\begin{array}{l}a=1,\quad b\approx -0.71806\\\\c\approx -0.14097+i\,0.66659,\quad d=\overline{c}\end{array}}Les valeurs propres {\lambda_2,\lambda_3,\lambda_4} vérifient {\left|\lambda_i\right|\lt 1} (habituel pour une matrice stochastique). Voici le calcul en Python d’une matrice de diagonalisation (l’ordre des valeurs propres reste le même) :
>>> P = np.linalg.eig(A)[1]; P
array([[ 0.62554324+0.j , 0.75285378+0.j , 0.65750284+0.j , 0.65750284-0.j ],
[ 0.62554324+0.j , -0.54059205+0.j , -0.09268911+0.43828503j , -0.09268911-0.43828503j],
[ 0.41702883+0.j , 0.13722474+0.j , -0.49825765-0.12357132j , -0.49825765+0.12357132j],
[ 0.20851441+0.j , -0.34948647+0.j , -0.06655608-0.3147137j , -0.06655608+0.3147137j ]])
On vérifie que {P} est une matrice de passage vers une réduite diagonale {D} de {A}.
>>> D = np.linalg.inv(P).dot(A).dot(P); np.round(D,5)
array([[ 1. -0.j , 0. + 0.j , 0. -0.j , 0. + 0.j ],
[ 0. -0.j , -0.71806 + 0.j , -0. -0.j , -0. + 0.j ],
[ 0. +0.j , 0. - 0.j , -0.14097 + 0.66659j , 0. +0.j ],
[ 0. -0.j , 0. - 0.j , 0. +0.j , -0.14097 - 0.66659j]])
Ainsi {A=PDP^{-1}} donc {A^n=PD^nP^{-1}}.
De plus {D^n=\begin{pmatrix}1&0&0&0\\0&b^n&0&0\\0&0&c^n&0\\ 0&0&0&d^n\end{pmatrix}}.
Donc {D^n} tend vers {\Delta=\begin{pmatrix}1&0&0&0\\0&0&0&0\\0&0&0&0\\ 0&0&0&0\end{pmatrix}}.
Posons {B=\displaystyle\lim_{n\to+\infty}A^n=P\Delta P^{-1}}.
On forme {\Delta} et on calcule {B} avec Python :
>>> Delta = np.diag([1,0,0,0])
>>> B = P.dot(Delta).dot(np.linalg.inv(P))
>>> np.real(B) # éliminer les parties imaginaires (nulles de toutes façons)
array([[0.33333333, 0.33333333, 0.33333333, 0.33333333],
[0.33333333, 0.33333333, 0.33333333, 0.33333333],
[0.22222222, 0.22222222, 0.22222222, 0.22222222],
[0.11111111, 0.11111111, 0.11111111, 0.11111111]])
Ainsi {B=\displaystyle\lim_{n\to+\infty}A^n=\Big(\varepsilon_1\mid\varepsilon_1\mid\varepsilon_1\mid\varepsilon_1\Bigr)}.
Pour tout {n\in\mathbb{N}^*}, on a {U_{n}=AU_{n-1}}.
On en déduit l’égalité : {U_n=A^nU_0}.
Ainsi {\displaystyle\lim_{n\to+\infty}U_n=BU_0=B\begin{pmatrix}1\\0\\0\\0\end{pmatrix}=\dfrac{1}{9}\begin{pmatrix}3\\3\\2\\1\end{pmatrix}}.
Pour justifier de façon théorique les résultats numériques précédents, on peut avancer les explications suivantes :
-
La suite {n\mapsto A^n} converge vers {B=P\Delta P^{-1}} qui est rang {1} (comme {\Delta}).
-
On a {\Delta^2=\Delta} donc {B^2=B}.
{B} est une matrice de projection sur une droite.
-
On a {A\varepsilon_1=\varepsilon_1}, donc {A^n\varepsilon_1=\varepsilon_1}.
À la limite, on trouve : {B\varepsilon_1=\varepsilon_1}.
Les colonnes de la matrice de projection {B} sont donc colinéaires à {\varepsilon_1}.
Mais {A} est stochastique (suivant les colonnes).
Cela reste vrai pour les {A^n} donc pour {B}.
Les colonnes de {B} sont donc égales à {\varepsilon_1}.