Questions du sujet
1. Justifier que, pour tout entier naturel $k$, $p_1^{(k)} + \cdots + p_n^{(k)} = 1$.
2. Montrer que, pour tout tout entier naturel $k$, $P^{(k+1)} = P^{(k)}T$.
3. En déduire, pour tout entier naturel $k$, une expression de $P^{(k)}$ en fonction de $T$, $k$ et $P^{(0)}$.
4. On suppose que la suite de vecteurs $(P^{(k)})_{k\in\mathbb{N}}$ converge vers un vecteur $P = (p_1, \ldots, p_n)$. Montrer que $P T = P$, que pour tout $i \in \llbracket 1, n\rrbracket$, $p_i \geq 0$ et que $p_1 + \cdots + p_n = 1$.
5. Exprimer la matrice de transition $T$ en fonction de $J_4$ et $I_4$.}
6. Démontrer qu’il existe une matrice $Q \in \mathcal{O}_4(\mathbb{R})$ telle que
\[
T = \frac{1}{3} Q
\begin{pmatrix}
-1 & 0 & 0 & 0 \\
0 & -1 & 0 & 0 \\
0 & 0 & -1 & 0 \\
0 & 0 & 0 & 3
\end{pmatrix}
Q^\top.
\]
7. Montrer que la suite de matrices $(T^k)_{k\in\mathbb{N}}$ converge et identifier géométriquement l’endomorphisme canoniquement associé à la matrice limite.
8. Montrer que, quel que soit le vecteur ligne $P^{(0)} = (p_1^{(0)}, p_2^{(0)}, p_3^{(0)}, p_4^{(0)})$, où pour $1 \leq i \leq 4$, $p_i^{(0)}$ est la probabilité que le point soit au départ sur le sommet $i$, la suite $(P^{(k)})_{k\in\mathbb{N}}$ converge vers le vecteur ligne $(1/4, 1/4, 1/4, 1/4)$.
9. Donner la matrice de transition $T$ de ce graphe et calculer $(1, 1, 1, 1, 1, 1, 1, 1)T$.
10. Montrer que, si le point se trouve sur un sommet de la partie $S_1$ à une étape donnée, il se trouvera sur un sommet de la partie $S_2$ à l’étape suivante et que, s’il se trouve sur un sommet de $S_2$ à une étape donnée, il se trouvera sur un sommet de $S_1$ à l’étape suivante.}
11. La suite de vecteurs $(P^{(k)})_{k\in\mathbb{N}}$ est-elle convergente ?
12. Soit $M \in M_n(\mathbb{R})$, dont tous les coefficients sont positifs ou nuls. Montrer que $M$ est une matrice stochastique si et seulement si
\[
M\begin{pmatrix}
1 \\
\vdots \\
1
\end{pmatrix}
=
\begin{pmatrix}
1 \\
\vdots \\
1
\end{pmatrix}.
\]
13. Montrer que la matrice de transition d’un graphe (définie dans la partie I) est une matrice stochastique et que, pour tout entier naturel $k$, le vecteur $P^{(k)}$, lui aussi défini dans la partie I, est une distribution de probabilité.
14. Montrer que $XM$ est une distribution de probabilité.
15. Montrer que $MN$ est une matrice stochastique.}
16. Montrer que $\alpha M + (1-\alpha)N$ est une matrice stochastique.
17. Soit $h \in \{1, \ldots, n\}$ tel que $|u_h| = \max_{1 \leq i \leq n}|u_i|$. Montrer que $|\lambda – m_{h,h}| \leq 1 – m_{h,h}$. En déduire que $|\lambda| \leq 1$.
18. Soit $\delta = \min_{1 \leq i \leq n} m_{i,i}$. Montrer que $|\lambda-\delta| \leq 1-\delta$. Donner une interprétation géométrique de ce résultat et montrer que, si tous les termes diagonaux de $M$ sont strictement positifs, alors $1$ est la seule valeur propre de $M$ de module $1$.
19. Démontrer que $\dim(\ker(M-I_n)) = 1$.\\
Si $(u_1,\ldots,u_n)$ désigne les composantes (réelles) dans la base canonique d’un vecteur de $\ker(M-I_n)$, on pourra utiliser $\min_{1\leq i \leq n}u_i$.
20. En déduire qu’il existe au plus une distribution de probabilité $X$ invariante par $M$, c’est-à-dire vérifiant $XM = X$.}
21. Démontrer les inégalités $\alpha_j^{(k)} \leq \alpha_j^{(k+1)} \leq \beta_j^{(k+1)} \leq \beta_j^{(k)}$.
22. Démontrer qu’il existe un couple $(i_0, j_0) \in \llbracket 1,n\rrbracket^2$ tel que $\alpha_j^{(k+1)} – \alpha_j^{(k)} \geq m_{i_0,j_0}(\beta_j^{(k)} – \alpha_j^{(k)})$.
23. Démontrer qu’il existe un couple $(i_1, j_1) \in \llbracket 1,n\rrbracket^2$ tel que $\beta_j^{(k)} – \beta_j^{(k+1)} \geq m_{i_1, j_1}(\beta_j^{(k)} – \alpha_j^{(k)})$.
24. En déduire que $\beta_j^{(k+1)} – \alpha_j^{(k+1)} \leq (1-2\epsilon)(\beta_j^{(k)} – \alpha_j^{(k)})$.
25. Démontrer que la suite $(M^k)$ converge vers une matrice stochastique $B = \begin{pmatrix}
b_1 & \cdots & b_n \\
b_1 & \cdots & b_n \\
b_1 & \cdots & b_n
\end{pmatrix}$ dont toutes les lignes sont égales. On note $P^{\infty}$ la ligne $(b_1, \ldots, b_n)$.}
26. Démontrer que, $\forall i \in \llbracket 1, n\rrbracket$, $b_i > 0$.
27. Démontrer que la suite $(P^{(k)})_{k\in\mathbb{N}} = (P^{(0)}M^k)_{k\in\mathbb{N}}$ converge vers $P^\infty$, quelle que soit la distribution de probabilité initiale $P^{(0)}$.
28. Démontrer que $P^\infty$ est l’unique distribution de probabilité $P$ invariante par $M$, c’est-à-dire vérifiant $PM = P$.
29. Vérifier que la matrice de transition associée à ce modèle de navigation est la matrice $A = (a_{i,j})_{1 \leq i,j \leq n}$ avec
\[
\begin{cases}
a_{i,i} = 1 & \text{si la page $i$ ne pointe vers aucune autre page} \\
a_{i,i} = 0 & \text{sinon} \\
a_{i,j} = 0 & \text{si $i \not\rightarrow j$} \\
a_{i,j} = 1/\lambda_i & \text{si $i\rightarrow j$ pour $i \neq j$}
\end{cases}
\]
30. Montrer que $B$ est une matrice stochastique dont tous les coefficients sont strictement positifs.}
31. Dans le modèle de navigation admettant $B$ pour matrice de transition, donner la probabilité de quitter une page ne contenant aucun lien vers une autre page.
32. Démontrer que la suite $(Q^{(k)})_{k\in\mathbb{N}}$ converge et que sa limite $Q^\infty$ vérifie les conditions (i) et (ii) décrites dans l’introduction de cette partie. Elle fournit donc des pertinences pour les $n$ pages du web. On exprimera la pertinence de chaque page $j$ en fonction de celles des pages qui pointent vers elle en distinguant les pages qui pointent vers une autre page et les autres.
33. Écrire une fonction Python \texttt{puissance1(B, k)} qui prend en argument une matrice carrée $B$ et un entier naturel $k$ et renvoie la matrice $B^k$ calculée en utilisant l’algorithme naïf.
34. Écrire une fonction Python \texttt{puissance2(B, k)} qui prend en argument une matrice carrée $B$ et un entier naturel $k$ et renvoie la matrice $B^k$ calculée à partir de l’algorithme d’exponentiation rapide.
35. On suppose que $k \geq 2$ et on note $p$ l’unique entier tel que $2^p \leq k < 2^{p+1}$. Pour chacun des appels \texttt{puissance1(B, k)} et \texttt{puissance2(B, k)}, calculer le nombre d’appels à la fonction \texttt{np.dot}, dans le pire et dans le meilleur des cas.}