Maths Expertes · Math@mine · Exercices
On considère la matrice d’adjacence d’un graphe à 4 sommets :
\(M = \begin{pmatrix}0&1&0&1\\0&0&1&0\\1&0&0&1\\0&1&0&0\end{pmatrix}\)
a. Arcs : \(1\to2\), \(1\to4\), \(2\to3\), \(3\to1\), \(3\to4\), \(4\to2\).
b. Depuis \(s_1\) : \(1\to2\to3\to1\), \(1\to4\to2\to3\), on peut atteindre tous les sommets. Depuis \(s_3\) également.
c. \(M^2 = M\cdot M\). Ligne 1, colonne 3 : \(m_{1,1}m_{1,3}+m_{1,2}m_{2,3}+m_{1,3}m_{3,3}+m_{1,4}m_{4,3} = 0+1\cdot1+0+0 = 1\). Un seul chemin de longueur 2 de \(s_1\) vers \(s_3\) : \(1\to2\to3\).
d. On calcule \((M^3)_{3,2}\). \(M^3 = M^2 \cdot M\). On a \((M^2)_{3,\cdot} = (\text{ligne 3 de }M^2)\). Ligne 3 de \(M^2\) : \((M^2)_{3j}=\sum_k M_{3k}M_{kj}\). \(M_{3,\cdot}=(1,0,0,1)\), donc \((M^2)_{3,j} = M_{1j}+M_{4j}\). \((M^2)_{3,\cdot} = (0+0, 1+1, 0+0, 1+0) = (0,2,0,1)\). Puis \((M^3)_{3,2} = \sum_k (M^2)_{3k}M_{k2} = 0\cdot M_{1,2}+2\cdot M_{2,2}+0+1\cdot M_{4,2} = 2\cdot0+1\cdot1 = 1\). Oui, il existe un chemin de longueur 3 de \(s_3\) vers \(s_2\).
Un rat se déplace dans un labyrinthe à 3 salles. Depuis la salle A, il va en B avec probabilité 2/3 et reste en A avec probabilité 1/3. Depuis B, il va en A ou C avec probabilité 1/2 chacune. Depuis C, il va toujours en B.
b. \(T = \begin{pmatrix}1/3 & 2/3 & 0 \\ 1/2 & 0 & 1/2 \\ 0 & 1 & 0\end{pmatrix}\) (ordre A, B, C).
c. Ligne A : \(1/3 + 2/3 = 1\). Ligne B : \(1/2 + 1/2 = 1\). Ligne C : \(1 = 1\). ✓
d. \(\pi_0 = (1, 0, 0)\). \(\pi_1 = \pi_0 T = (1/3, 2/3, 0)\). \(\pi_2 = \pi_1 T = (1/3\cdot1/3 + 2/3\cdot1/2,\ 1/3\cdot2/3 + 0,\ 2/3\cdot1/2) = (1/9+1/3,\ 2/9,\ 1/3) = (4/9,\ 2/9,\ 3/9)\).
Probabilité d’être en B après 2 déplacements : \(2/9\).
Une chaîne de Markov à 2 états (0 et 1) a pour matrice de transition \(T = \begin{pmatrix}0{,}6 & 0{,}4 \\ 0{,}2 & 0{,}8\end{pmatrix}\).
a. \(\pi_1 = (1,0)\cdot T = (0{,}6, 0{,}4)\). \(\pi_2 = (0{,}6, 0{,}4)\cdot T = (0{,}6\cdot0{,}6+0{,}4\cdot0{,}2,\ 0{,}6\cdot0{,}4+0{,}4\cdot0{,}8) = (0{,}44, 0{,}56)\).
b. \(\pi_1 = (0{,}5,0{,}5)\cdot T = (0{,}4, 0{,}6)\). \(\pi_2 = (0{,}4,0{,}6)\cdot T = (0{,}36, 0{,}64)\).
c. On résout \(\pi T = \pi\) : \(0{,}6\pi_0^* + 0{,}2\pi_1^* = \pi_0^*\), soit \(-0{,}4\pi_0^* + 0{,}2\pi_1^* = 0\), donc \(\pi_1^* = 2\pi_0^*\). Avec \(\pi_0^*+\pi_1^*=1\) : \(3\pi_0^*=1\), \(\pi^* = (1/3, 2/3)\).
d. Les deux suites convergent vers \((1/3, 2/3) \approx (0{,}333, 0{,}667)\), quelle que soit la condition initiale.
Chaque semaine, un consommateur achète la marque A ou B. S’il achète A, il rachète A la semaine suivante avec probabilité 0,9 et passe à B avec probabilité 0,1. S’il achète B, il passe à A avec probabilité 0,3 et reste à B avec probabilité 0,7.
a. \(T = \begin{pmatrix}0{,}9 & 0{,}1 \\ 0{,}3 & 0{,}7\end{pmatrix}\).
b. Système : \(0{,}9\pi_A + 0{,}3\pi_B = \pi_A\) ⟹ \(-0{,}1\pi_A + 0{,}3\pi_B = 0\) ⟹ \(\pi_B = \pi_A/3\). Avec \(\pi_A+\pi_B=1\) : \(\pi_A = 3/4\), \(\pi_B = 1/4\).
c. À long terme : A capture 75 % du marché, B 25 %.
d. \(\pi_0 = (0{,}6, 0{,}4)\). \(\pi_1 = (0{,}66, 0{,}34)\). \(\pi_2 = (0{,}696, 0{,}304)\). \(\pi_3 = (0{,}7176, 0{,}2824)\). La distribution se rapproche de \((0{,}75, 0{,}25)\).
Un patient peut être dans l’état Sain (S), Malade (M) ou Rétabli (R). La matrice de transition hebdomadaire est :
\(T = \begin{pmatrix}0{,}8 & 0{,}1 & 0{,}1 \\ 0{,}0 & 0{,}5 & 0{,}5 \\ 0{,}2 & 0{,}0 & 0{,}8\end{pmatrix}\) (ordre S, M, R)
a. \(T_{1,2}=0{,}1\) : un patient sain tombe malade avec proba 0,1 par semaine. \(T_{2,3}=0{,}5\) : un patient malade guérit avec proba 0,5. \(T_{3,1}=0{,}2\) : un patient rétabli retombe sain (en bonne santé durable) avec proba 0,2… etc.
b. Sommes des lignes : \(0{,}8+0{,}1+0{,}1=1\), \(0+0{,}5+0{,}5=1\), \(0{,}2+0+0{,}8=1\). ✓
c. \(\pi_0=(1,0,0)\). \(\pi_1=(0{,}8, 0{,}1, 0{,}1)\). \(\pi_2 = \pi_1 T\) : \(\pi_2(S) = 0{,}8\cdot0{,}8+0{,}1\cdot0+0{,}1\cdot0{,}2 = 0{,}66\). \(\pi_2(M) = 0{,}8\cdot0{,}1+0{,}1\cdot0{,}5+0 = 0{,}13\). \(\pi_2(R) = 0{,}8\cdot0{,}1+0{,}1\cdot0{,}5+0{,}1\cdot0{,}8 = 0{,}21\). Soit \(\pi_2 = (0{,}66,\ 0{,}13,\ 0{,}21)\).
d. On résout \(\pi T = \pi\) avec \(\pi_S+\pi_M+\pi_R=1\). Système : \(0{,}8\pi_S+0\cdot\pi_M+0{,}2\pi_R=\pi_S\) → \(-0{,}2\pi_S+0{,}2\pi_R=0\) → \(\pi_R=\pi_S\). Et \(0{,}1\pi_S+0{,}5\pi_M=\pi_M\) → \(0{,}1\pi_S=0{,}5\pi_M\) → \(\pi_M=\pi_S/5\). Avec \(\pi_S+\pi_S/5+\pi_S=1\) : \(\pi_S(2+1/5)=1\), \(\pi_S=5/11\), \(\pi_M=1/11\), \(\pi_R=5/11\).
On considère le graphe en anneau à 4 sommets : \(1\leftrightarrow2\leftrightarrow3\leftrightarrow4\leftrightarrow1\). Un marcheur aléatoire passe à l’un des deux voisins avec probabilité 1/2 chacune.
a. \(T = \frac{1}{2}\begin{pmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\end{pmatrix}\).
b. Depuis 1, après 1 pas on est en 2 ou 4 (pas en 1). Après 2 pas, on peut revenir en 1. Donc \(\mathbb{P}(X_1=1)=0\) mais \(\mathbb{P}(X_2=1)=1/2\). La chaîne est périodique de période 2.
c. Par symétrie, \(\pi = (1/4, 1/4, 1/4, 1/4)\). Vérification : \(\pi T = (1/4\cdot1/2+1/4\cdot1/2, \ldots) = (1/4, \ldots)\). ✓ C’est intuitif : le graphe est symétrique, tous les sommets sont équivalents.
d. Irréductible : on peut aller de tout sommet à tout autre (en 1 ou 2 pas). Non apériodique : la chaîne est de période 2 (on alterne entre sommets pairs et impairs). Le théorème de convergence ne s’applique pas directement ; la distribution ne converge pas mais oscille.
Un joueur commence avec \(k\) jetons (\(0 \le k \le 3\)). À chaque tour, il gagne 1 jeton avec probabilité \(p = 0{,}4\) et en perd 1 avec probabilité \(q = 0{,}6\). Le jeu s’arrête s’il atteint 0 (ruiné) ou 3 (objectif).
Les états sont \(\{0, 1, 2, 3\}\) avec 0 et 3 absorbants.
a. \(T = \begin{pmatrix}1&0&0&0\\0{,}6&0&0{,}4&0\\0&0{,}6&0&0{,}4\\0&0&0&1\end{pmatrix}\) (états 0,1,2,3).
b. On note \(\pi_n = (\pi_n(0), \pi_n(1), \pi_n(2), \pi_n(3))\) (vecteur ligne) et \(\pi_{n+1} = \pi_n T\). Initialement : \(\pi_0 = (0, 0, 1, 0)\).
\(\pi_1\) : depuis l'état 2, on va en 1 avec prob. 0,6 ou en 3 avec prob. 0,4. Donc \(\pi_1 = (0\,;\,0{,}6\,;\,0\,;\,0{,}4)\). Vérification : somme = 1 ✓.
\(\pi_2 = \pi_1 T\). Coordonnée par coordonnée :
Soit \(\pi_2 = (0{,}36\,;\,0\,;\,0{,}24\,;\,0{,}4)\). Somme = 1 ✓.
\(\pi_3 = \pi_2 T\) :
Soit \(\boxed{\pi_3 = (0{,}36\,;\,0{,}144\,;\,0\,;\,0{,}496)}\). Vérification : \(0{,}36 + 0{,}144 + 0 + 0{,}496 = 1\) ✓.
Au bout de 3 tours, le joueur est ruiné dans 36 % des cas, a atteint son objectif dans 49,6 % des cas, et le jeu continue avec 1 jeton dans 14,4 % des cas.
c. À long terme, le joueur est absorbé en 0 (ruine) ou en 3 (objectif). La probabilité de ruine en partant de \(k\) jetons est donnée par la formule classique de la marche de Gambler (\(p \neq q\)) : \(\Pr(\text{ruine} \mid k) = \dfrac{r^N - r^k}{r^N - 1}\) avec \(r = q/p\) et \(N = 3\).
Ici \(r = 0{,}6/0{,}4 = 1{,}5\) : \(r^3 = 3{,}375\), \(r^2 = 2{,}25\). Pour \(k = 2\) :
\(\Pr(\text{ruine} \mid 2) = \dfrac{3{,}375 - 2{,}25}{3{,}375 - 1} = \dfrac{1{,}125}{2{,}375} = \dfrac{9}{19} \approx 47{,}4\,\%.\)
Surprise : bien que \(p < 1/2\) (chaque pas est défavorable), partir avec 2 jetons sur 3 donne \(\Pr(\text{succès}) \approx 52{,}6\,\%\), légèrement supérieur à \(\Pr(\text{ruine})\) — l'avantage initial compense la défavorabilité du pas. Pour \(k=1\) en revanche, la ruine vaut \(\Pr(\text{ruine} \mid 1) = (3{,}375 - 1{,}5)/2{,}375 \approx 78{,}9\,\%\), conforme à l'intuition.