\documentclass[10pt]{article}
\usepackage[french]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[version=4]{mhchem}
\usepackage{stmaryrd}
\usepackage{bbold}

\begin{document}
\section*{OPTION ECONOMIQUE}
\section*{MATHEMATIQUES II}
Mercredi 7 mai 2008, de 14 h à 18 h

La présentation, la lisibilité, l'orthographe, la qualité de la rédaction, la clarté et la précision des raisonnements entreront pour une part importante dans l'appréciation des copies.\\
Les candidats sont invités à encadrer dans la mesure du possible les résultats de leurs calculs.\\
Ils ne doivent faire usage d'aucun document ; l'utilisation de toute calculatrice et de tout matériel électronique est interdite. Seule l'utilisation d'une règle graduée est autorisée.\\
Si au cours de l'épreuve un candidat repère ce qui lui semble être une erreur d'énoncé, il le signalera sur sa copie et poursuivra sa composition en expliquant les raisons des initiatives qu'il sera amené à prendre.

Tout au long du sujet \(N\) désigne un entier naturel supérieur ou égal à 2 .\\
Notations :

\begin{itemize}
  \item Pour \(x \in \mathbb{R}\), on note \(|x|\) la valeur absolue de \(x\).
  \item Pour tout vecteur \(V=\left(\begin{array}{c}v_{1} \\ \cdot \\ \cdot \\ v_{N}\end{array}\right) \in \mathcal{M}_{N, 1}(\mathbb{R})\), on note \(|V|=\left(\begin{array}{c}\left|v_{1}\right| \\ \cdot \\ \cdot \\ \left|v_{N}\right|\end{array}\right) \in \mathcal{M}_{N, 1}(\mathbb{R})\)\\
et \(\|V\|_{1}=\sum_{j=1}^{N}\left|v_{j}\right|\).
  \item On notera \(I_{N}\) la matrice identitée de \(\mathcal{M}_{N}(\mathbb{R})\).
  \item Pour \(A \in \mathcal{M}_{N}(\mathbb{R})\), on note \({ }^{t} A\) la matrice transposée de \(A\).
\end{itemize}

Résultat admis :

\begin{itemize}
  \item Pour \((A, B) \in \mathcal{M}_{N}(\mathbb{R})^{2}\), on a \({ }^{t}(A B)={ }^{t} B^{t} A\).
\end{itemize}

\section*{Définitions :}
\begin{itemize}
  \item Une matrice est dite positive si tous ses coefficients sont des nombres réels positifs ou nuls; elle est dite strictement positive si tous ses coefficients sont des nombres réels strictement positifs.
  \item Un vecteur colonne \(V \in \mathcal{M}_{N, 1}(\mathbb{R})\) est dit de probabilité si \(V\) est positif et si \(\|V\|_{1}=1\).
  \item Une matrice \(Q=(Q(i, j))_{1 \leq i \leq N, 1 \leq j \leq N} \in \mathcal{M}_{N}(\mathbb{R})\) est dite stochastique si elle est positive et si \(\sum_{i=1}^{N} Q(i, j)=1\) pour tout \(1 \leq j \leq N\).
  \item Un vecteur \(V \in \mathcal{M}_{N, 1}(\mathbb{R})\) est dit invariant par \(Q \in \mathcal{M}_{N}(\mathbb{R})\) si \(Q V=V\).
  \item Soit \(Q \in \mathcal{M}_{N}(\mathbb{R})\). La suite de matrice \(\left(Q^{n}\right)_{n \geq 0}\) est convergente vers la matrice \(Q_{\infty}\) si pour tout \((i, j) \in\{1, \ldots, N\}^{2},\left(Q^{n}(i, j)\right)_{n \geq 0}\) converge vers \(Q_{\infty}(i, j)\).
\end{itemize}

\section*{Préliminaires}
Soit \(V=\left(\begin{array}{c}v_{1} \\ \cdot \\ \cdot \\ v_{N}\end{array}\right) \in \mathcal{M}_{N, 1}(\mathbb{R})\) tel que

\[
\left|\sum_{j=1}^{N} v_{j}\right|=\sum_{j=1}^{N}\left|v_{j}\right|
\]

P1. Montrer que, pour tout \(x\) réel, \(|x|-x \geq 0\).\\
P2. Etude du cas \(N=3\). On supposera donc, dans cette question P2 uniquement, \(N=3\).\\
P2.a Montrer que

\[
\left(\left|v_{1}\right|+\left|v_{2}\right|+\left|v_{3}\right|\right)^{2}-\left(v_{1}+v_{2}+v_{3}\right)^{2}=2\left(\left|v_{1} v_{2}\right|-v_{1} v_{2}\right)+2\left(\left|v_{1} v_{3}\right|-v_{1} v_{3}\right)+2\left(\left|v_{2} v_{3}\right|-v_{2} v_{3}\right) .
\]

P2.b Montrer à l'aide de (E), que si \(\left|v_{j} v_{j^{\prime}}\right|>0\) pour \(\left(j, j^{\prime}\right) \in\{1,2,3\}^{2}\) tel que \(j \neq j^{\prime}\), alors \(v_{j}\) et \(v_{j^{\prime}}\) ont même signe.

P2.c Conclure que \(V=|V|\) ou \(V=-|V|\).\\
P3. Montrer que \(V=|V|\) ou \(V=-|V|\) dans le cas général où \(N\) est un entier quelconque vérifiant \(N \geq 2\).

\section*{Partie I Google et PageRank}
En 1998, Sergey Brin et Larry Page, co-fondateurs de Google, ont introduit la notion de PageRank. Le PageRank est un indice mesurant la notoriété de chacune des pages Web référencées dans Google. Bien que les outils de calcul de cet indice soient maintenus secrets, le principe mathématique sur lequel repose ce calcul est public et peut-être résumé comme suit.

On numérote de 1 à \(N\) les pages Web référencées dans Google (on pense que \(N=10^{9}\) est un bon ordre de grandeur). On dira qu'une page \(j \in\{1, \ldots, N\}\) pointe vers une autre page \(i \in\{1, \ldots, N\}\) s'il existe un lien dans la page \(j\) permettant de rejoindre la page \(i\) en cliquant dessus.

Pour tout \(j \in\{1, \ldots, N\}\), on note \(d_{j}\) le nombre de pages vers lesquelles la \(j^{\text {ème }}\) page pointe. Lorsque \(d_{j}=0\) pour chaque couple de pages \((i, j)\) posons \(A(i, j)=0\) si \(i \neq j\) et \(A(j, j)=1\). Lorsque \(d_{j}>0\), posons soit \(A(i, j)=1 / d_{j}\) si \(j\) pointe vers \(i\) soit \(A(i, j)=0\) sinon. Si \(\rho \in[0,1[\), on définit la matrice de Google \(G=(G(i, j))_{1 \leq i \leq N, 1 \leq j \leq N}\) par

\[
G(i, j)=\rho A(i, j)+\frac{(1-\rho)}{N}, \text { pour tout } 1 \leq i \leq N \text { et } 1 \leq j \leq N
\]

Pour tout \(j \in\{1, \ldots, N\}\), le PageRank d'une page \(j\) est un nombre réel positif ou nul noté \(p(j)\). Les \(p(j), 1 \leq j \leq N\) sont par ailleurs définis par le système d'équations

\[
\sum_{j=1}^{N} p(j)=1 \text { et } \sum_{j=1}^{N} G(i, j) p(j)=p(i) \text { pour tout } 1 \leq i \leq N .
\]

A la question "que mesure exactement pour une page \(j \in\{1, \ldots, N\}\) donnée ce fameux PageRank \(p(j)\) ?", leurs concepteurs assurent qu'il s'agit de la "chance" qu'un surfeur se retrouve sur la page \(j\) en question. Le but de ce sujet est de lever un coin du voile entourant le mystère du PageRank en justifiant d'une part de l'existence et de l'unicité de la solution du système ( S ) et en fournissant d'autre part une interprétation probabiliste de ce système permettant de donner un sens mathématique aux affirmations de Brin et Page.

\section*{A. Etude de la matrice G de Google}
On démontre dans cette section quelques propriétés simples de la matrice \(G\) de Google.\\
I.A. 1 Montrer que \(G \in \mathcal{M}_{N}(\mathbb{R})\) est une matrice strictement positive.\\
I.A. 2 Soit \(j \in\{1, \ldots, N\}\) tel que \(d_{j}=0\), montrer que \(\sum_{i=1}^{N} G(i, j)=1\).\\
I.A. 3 Soit \(j \in\{1, \ldots, N\}\) tel que \(d_{j}>0\). En écrivant que

\[
\sum_{i=1}^{N} G(i, j)=\sum_{\substack{i \in\{1, \ldots, N\} \\ j \text { pointe vers } i}} G(i, j)+\sum_{\substack{i \in\{1, \ldots, N\} \\ j \text { ne pointe pas vers } i}} G(i, j)
\]

montrer que \(\sum_{i=1}^{N} G(i, j)=1\).\\
I.A. 4 Que peut-on en déduire pour \(G\) ?\\
I.A. 5 Montrer que le vecteur \(\left(\begin{array}{c}p(1) \\ \cdot \\ \cdot \\ p(N)\end{array}\right) \in \mathcal{M}_{N, 1}(\mathbb{R})\) défini en (S), en admettant qu'il existe, est invariant par \(G\).

\section*{B. Modèle du surfeur sur le Web}
Dans toute cette partie ( \(\Omega, \mathcal{F}, P\) ) désigne un espace probabilisé et toutes les variables aléatoires utilisées sont toutes définies sur cet espace. On rappelle que l'on numérote de 1 à \(N\) les \(N\) pages Web référencées dans Google. On considère un internaute surfant sur le Web en utilisant Google, on\\
note \(X_{0}\) la première page visitée et \(X_{n}\) la page sur laquelle il se retrouve au bout de \(n\) opérations (soit de clic sur un lien dans une page soit d'abandon au profit d'une autre adresse). Pour tout \(n \in \mathbb{N}\), \(X_{n}\) est à valeurs dans \(\{1,2, \ldots, N\}\) et on admettra que la suite de variables aléatoires \(\left(X_{n}\right)_{n \geq 0}\) vérifie pour tout entier \(n \geq 1\) et tout \(\left(x_{n-1}, x_{n}\right) \in\{1,2, \ldots, N\}^{2}\)

\[
P_{\left\{X_{n-1}=x_{n-1}\right\}}\left(X_{n}=x_{n}\right)=P\left(X_{n}=x_{n} \mid X_{n-1}=x_{n-1}\right)=G\left(x_{n}, x_{n-1}\right)
\]

où \(G\) est la matrice de Google. On considère \(n\) un entier naturel strictement positif.\\
I.B. 1 On note \(V_{n}\) le vecteur de \(\mathcal{M}_{N, 1}(\mathbb{R})\) dont pour tout \(i \in\{1,2, \ldots, N\}\), la \(i^{\text {ème }}\) composante est définie par \(\left(v_{n}\right)_{i}=P\left(X_{n}=i\right)\). Vérifier que \(V_{n}\) est bien un vecteur de probabilité.\\
I.B. 2 Exprimer pour tout \((i, j) \in\{1,2, \ldots, N\}^{2} P\left(\left\{X_{n}=i\right\} \cap\left\{X_{n-1}=j\right\}\right)\) à l'aide de \(G\) et \(V_{n-1}\).\\
I.B. 3 En déduire que \(V_{n}=G V_{n-1}\).\\
I.B. 4 Montrer que pour tout \(k\) entier naturel \(V_{k}=G^{k} V_{0}\).

\section*{Partie II Matrices stochastiques}
Le but de cette deuxième partie est de prouver l'existence et l'unicité d'un vecteur de probabilité invariant pour une matrice stochastique strictement positive.

\section*{A. Etude d'un exemple}
On considère une matrice \(Q \in \mathcal{M}_{2}(\mathbb{R})\) stochastique et strictement positive. \(Q\) peut se mettre sous la forme

\[
Q=\left(\begin{array}{cc}
1-q & q^{\prime} \\
q & 1-q^{\prime}
\end{array}\right)
\]

avec \(q \in] 0,1\left[\right.\) et \(\left.q^{\prime} \in\right] 0,1[\).\\
II.A. 1 Déterminer l'ensemble des vecteurs \(V \in \mathcal{M}_{2,1}(\mathbb{R})\) vérifiant \(Q V=V\).\\
II.A. 2 Montrer qu'il existe un unique vecteur de probabilité \(V_{\infty} \in \mathcal{M}_{2,1}(\mathbb{R})\) invariant par \(Q\) et le calculer.\\
II.A. 3 Prouver que pour tout entier \(n \geq 1\)

\[
Q^{n}=\frac{1}{q+q^{\prime}}\left(\begin{array}{cc}
q^{\prime} & q^{\prime} \\
q & q
\end{array}\right)+\frac{\left(1-q-q^{\prime}\right)^{n}}{q+q^{\prime}}\left(\begin{array}{cc}
q & -q^{\prime} \\
-q & q^{\prime}
\end{array}\right)
\]

II.A. 4 En déduire que \(\left(Q^{n}\right)_{n \geq 1}\) converge lorsque \(n\) tend vers l'infini vers une matrice dont les deux vecteurs colonnes sont égaux à \(V_{\infty}\).

On cherchera à généraliser ce résultat dans la partie III.

\section*{B. Existence d'un vecteur de probabilité invariant}
Dans cette section II.B, \(Q \in \mathcal{M}_{N}(\mathbb{R})\) est une matrice stochastique.\\
II.B. 1 On note \(U\) le vecteur élément de \(\mathcal{M}_{N, 1}(\mathbb{R})\) dont toutes les composantes valent 1 . Calculer \({ }^{t} Q U\).\\
II.B. 2 Montrer que si \(Q-I_{N}\) est inversible, alors \({ }^{t} Q-I_{N}\) est aussi inversible.\\
II.B. 3 Déduire des deux questions précédentes que 1 est valeur propre de \(Q\).

Soit \(\lambda\) une valeur propre réelle de \(Q\) telle que \(|\lambda|=1\) et \(V \in \mathcal{M}_{N, 1}(\mathbb{R})\) un vecteur propre de \(Q\) associé à la valeur propre \(\lambda\).\\
II.B. 4 Prouver que le vecteur \(Q|V|-|V|\) est positif.\\
II.B. 5 Montrer que le vecteur \(|V|\) est invariant par \(Q\).

Indication : on pourra sommer les composantes du vecteur \(Q|V|-|V|\).\\
II.B. 6 Prouver l'existence d'au moins un vecteur de probabilité invariant par \(Q\).

\section*{C. Unicité d'un vecteur de probabilité invariant}
Dans cette section II.C, \(Q \in \mathcal{M}_{N}(\mathbb{R})\) est une matrice stochastique strictement positive. On sait d'après II.B. 6 qu'il existe au moins un vecteur de probabilité invariant par \(Q\) noté

\[
V_{\infty}=\left(\begin{array}{c}
\left(v_{\infty}\right)_{1} \\
\cdot \\
\cdot \\
\left(v_{\infty}\right)_{N}
\end{array}\right)
\]

Cette section II.C permettra de démontrer l'unicité d'un tel vecteur.\\
II.C. 1 Prouver que si \(V\) est un vecteur positif invariant par \(Q\), alors soit \(V=0_{\mathcal{M}_{N, 1}(\mathbb{R})}\) soit \(V\) est strictement positif.\\
II.C. 2 Justifier que \(V_{\infty}\) est strictement positif.

On considère à présent un autre vecteur de probabilité noté

\[
W_{\infty}=\left(\begin{array}{c}
\left(w_{\infty}\right)_{1} \\
\cdot \\
\cdot \\
\left(w_{\infty}\right)_{N}
\end{array}\right)
\]

invariant par \(Q\). Puis, on définit

\[
\begin{aligned}
\alpha & =\min \left\{\left.\frac{\left(w_{\infty}\right)_{i}}{\left(v_{\infty}\right)_{i}} \right\rvert\, 1 \leq i \leq N\right\}=\frac{\left(w_{\infty}\right)_{i_{0}}}{\left(v_{\infty}\right)_{i_{0}}} \text { et } \\
V & =W_{\infty}-\alpha V_{\infty}
\end{aligned}
\]

II.C. 3 Montrer que \(V\) est invariant par \(Q\).\\
II.C. 4 Montrer que \(V\) est positif mais pas strictement positif.\\
II.C. 5 En déduire que \(W_{\infty}=\alpha V_{\infty}\).\\
II.C. 6 En conclure que \(W_{\infty}=V_{\infty}\).

On reprend jusqu'à la fin de cette partie les notations de la partie I sur Google et la notion de PageRank.\\
II.C. 7 Montrer que le système ( S ) définissant le PageRank admet bien une et une seule solution.\\
II.C. 8 Démontrer que \(p(i) \geq(1-\rho) / N\) pour tout \(i \in\{1, \ldots, N\}\).\\
II.C. 9 Le rôle du paramètre \(\rho\) est essentiel pour assurer l'unicité de la solution du système (S). Que se passerait-il pour \(\rho=1\) et disons \(N=3\) pour simplifier à l'extrême? (Songer qu'il peut exister des pages Web qui ne pointent vers aucune autre!).

\section*{Partie III Validation du PageRank}
Dans toute cette partie III, on considère \(Q \in \mathcal{M}_{N}(\mathbb{R})\) matrice stochastique strictement positive. On notera \(V_{\infty}\) l'unique vecteur de probabilité invariant par \(Q\).

\section*{A. Valeurs propres de \(\boldsymbol{Q}\)}
Il s'agit dans cette section III.A de localiser les valeurs propres de \(Q\).\\
III.A. 1 Vérifier que pour tout vecteur \(V \in \mathcal{M}_{N, 1}(\mathbb{R})\) on a

\[
\|Q V\|_{1} \leq\|V\|_{1}
\]

avec de plus \(\|Q V\|_{1}=\|V\|_{1}\) lorsque \(V\) est positif.\\
III.A. 2 En déduire que pour toute valeur propre réelle \(\lambda\) de \(Q\), on a \(|\lambda| \leq 1\).

Soient \(\lambda\) une valeur propre réelle de \(Q\) telle que \(|\lambda|=1\), et \(V \in \mathcal{M}_{N, 1}(\mathbb{R})\) un vecteur propre de \(Q\) associé à \(\lambda\) tel que \(\|V\|_{1}=1\). On sait grâce au II.B. 5 que \(|V|=V_{\infty}\).\\
III.A. 3 Etablir l'identité

\[
\left|\sum_{j=1}^{N} Q(1, j) v_{j}\right|=\sum_{j=1}^{N} Q(1, j)\left|v_{j}\right|
\]

où \(v_{i}\) est la \(i^{\text {ème }}\) composante de \(V\) pour \(i \in\{1, \ldots, N\}\).\\
III.A. 4 En déduire en utilisant P 3 que \(V\) est colinéaire à \(|V|\) puis que \(\lambda=1\).

\section*{B. Convergence}
On fera dans cette section III.B l'hypothèse supplémentaire que \(Q\) est diagonalisable.\\
Le but de ce qui suit est d'établir que la suite \(\left(Q^{n}\right)_{n \geq 1}\) converge, lorsque \(n\) tend vers l'infini, vers la matrice \(Q_{\infty}\) dont les vecteurs colonnes sont tous égaux à \(V_{\infty}\).\\
III.B. 1 Montrer qu'il existe une matrice diagonale \(D \in \mathcal{M}_{N}(\mathbb{R})\) et une matrice inversible \(S \in \mathcal{M}_{N}(\mathbb{R})\), telles que pour tout \(n \geq 1, Q^{n}=S D^{n} S^{-1}\).\\
III.B. 2 Prouver que parmi les \(N\) coefficients diagonaux de \(D\) un et un seul est égal à 1 alors que tous les autres sont de valeur absolue strictement inférieure à 1 .\\
III.B. 3 En déduire que la suite \(\left(Q^{n}\right)_{n \geq 1}\) converge vers une matrice \(Q_{\infty}\).\\
III.B. 4 Prouver que pour tout \(n \geq 1, Q^{n}\) est stochastique puis que \(Q_{\infty}\) est stochastique.\\
III.B. 5 Démontrer que \(Q Q_{\infty}=Q_{\infty}\).\\
III.B. 6 En déduire que chacun des vecteurs colonnes de \(Q_{\infty}\) est invariant par \(Q\).\\
III.B. 7 Conclure.

On admettra pour la partie III.C que \(\left(Q^{n}\right)_{n \geq 1}\) converge lorsque \(n\) tend vers l'infini vers la matrice \(Q_{\infty}\) dont les vecteurs colonnes sont tous égaux à \(V_{\infty}\) sous les seules hypothèses \(Q\) stochastique et strictement positive.

\section*{C. Application au modèle du surfeur}
On reprend pour la fin du sujet les notations du PageRank de Google décrit dans l'introduction de la partie I et du modèle du surfeur décrit dans la partie I.B. On considère \(X_{\infty}\) la variable aléatoire à valeurs dans \(\{1, \ldots, N\}\) dont la loi est définie par

\[
P\left(X_{\infty}=i\right)=p(i) \text { pour tout } i \in\{1,2, \ldots, N\} .
\]

III.C. 1 Montrer que \(\left(X_{n}\right)_{n \geq 0}\) converge en loi vers \(X_{\infty}\) lorsque \(n\) tend vers l'infini.\\
III.C. 2 En quoi ce résultat donne-t-il du sens à l'assertion un peu vague: "le PageRank d'une page donnée représente la chance qu'un internaute se retrouve sur la page en question lorsqu'il surfe"?


\end{document}