WikiPrépaLivrets

BCE Maths appliquées ESSEC ECE 2008, épreuve 2Sujet, corrigé et rapport du jury

Epreuve de maths appliquées - ECE 2008

Pas encore noté
Logo concours BCE

Explorer les annales

BanqueBCEAnnée2008FilièreECEMatièreMathématiques
Annales BCE ECE MathématiquesBCE ECE 2008ECE MathématiquesMathématiques 2008

Téléchargements

Télécharger le sujet (PDF)
Corrigé
Rapport du juryLire en ligneLaTeXWord
Source du document : annales-prepa.fr

Description

Annale de maths appliquées BCE ESSEC pour la filiere ECE, session 2008.

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.
Afficher ou masquer la section
Sujet en PDF

OPTION ECONOMIQUE

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 :
  • Pour x ∈ ℝ, on note |x| la valeur absolue de x.
  • Pour tout vecteur V = (v_1; ⋅; ⋅; v_N) ∈ M_(N, 1)(ℝ), on note |V| = (|v_1|; ⋅; ⋅; |v_N|) ∈ M_(N, 1)(ℝ)
    et ‖V‖_1 = ∑_(j = 1)^N|v_j|.
  • On notera I_N la matrice identitée de M_N(ℝ).
  • Pour A ∈ M_N(ℝ), on note ^t A la matrice transposée de A.
Résultat admis :
  • Pour (A, B) ∈ M_N(ℝ)^2, on a ^t(AB) = ^t B^t A.

Définitions :

  • 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.
  • Un vecteur colonne V ∈ M_(N, 1)(ℝ) est dit de probabilité si V est positif et si ‖V‖_1 = 1.
  • Une matrice Q = (Q(i, j))_(1 ≤ i ≤ N, 1 ≤ j ≤ N) ∈ M_N(ℝ) est dite stochastique si elle est positive et si ∑_(i = 1)^N Q(i, j) = 1 pour tout 1 ≤ j ≤ N.
  • Un vecteur V ∈ M_(N, 1)(ℝ) est dit invariant par Q ∈ M_N(ℝ) si QV = V.
  • Soit Q ∈ M_N(ℝ). La suite de matrice (Q^n)_(n ≥ 0) est convergente vers la matrice Q_∞ si pour tout (i, j) ∈ {1, …, N}^2, (Q^n(i, j))_(n ≥ 0) converge vers Q_∞(i, j).

Préliminaires

Soit V = (v_1; ⋅; ⋅; v_N) ∈ M_(N, 1)(ℝ) tel que
|∑_(j = 1)^N v_j| = ∑_(j = 1)^N|v_j|
P1. Montrer que, pour tout x réel, |x| − x ≥ 0.
P2. Etude du cas N = 3. On supposera donc, dans cette question P2 uniquement, N = 3.
P2.a Montrer que
(|v_1| + |v_2| + |v_3|)^2 − (v_1 + v_2 + v_3)^2 = 2(|v_1 v_2| − v_1 v_2) + 2(|v_1 v_3| − v_1 v_3) + 2(|v_2 v_3| − v_2 v_3).
P2.b Montrer à l'aide de (E), que si |v_j v_(j^′)| > 0 pour (j, j^′) ∈ {1, 2, 3}^2 tel que j ≠ j^′, alors v_j et v_(j^′) 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 ≥ 2.

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 ∈ {1, …, N} pointe vers une autre page i ∈ {1, …, N} s'il existe un lien dans la page j permettant de rejoindre la page i en cliquant dessus.
Pour tout j ∈ {1, …, N}, on note d_j le nombre de pages vers lesquelles la j^(ème) page pointe. Lorsque d_j = 0 pour chaque couple de pages (i, j) posons A(i, j) = 0 si i ≠ 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 ρ ∈ [0, 1[, on définit la matrice de Google G = (G(i, j))_(1 ≤ i ≤ N, 1 ≤ j ≤ N) par
G(i, j) = ρA(i, j) + ((1 − ρ))/N, pour tout 1 ≤ i ≤ N et 1 ≤ j ≤ N
Pour tout j ∈ {1, …, N}, le PageRank d'une page j est un nombre réel positif ou nul noté p(j). Les p(j), 1 ≤ j ≤ N sont par ailleurs définis par le système d'équations
∑_(j = 1)^N p(j) = 1 et ∑_(j = 1)^N G(i, j)p(j) = p(i) pour tout 1 ≤ i ≤ N.
A la question "que mesure exactement pour une page j ∈ {1, …, 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.

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 ∈ M_N(ℝ) est une matrice strictement positive.
I.A. 2 Soit j ∈ {1, …, N} tel que d_j = 0, montrer que ∑_(i = 1)^N G(i, j) = 1.
I.A. 3 Soit j ∈ {1, …, N} tel que d_j > 0. En écrivant que
∑_(i = 1)^N G(i, j) = ∑_(i ∈ {1, …, N}; j pointe vers i)G(i, j) + ∑_(i ∈ {1, …, N}; j ne pointe pas vers i)G(i, j)
montrer que ∑_(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 (p(1); ⋅; ⋅; p(N)) ∈ M_(N, 1)(ℝ) défini en (S), en admettant qu'il existe, est invariant par G.

B. Modèle du surfeur sur le Web

Dans toute cette partie ( Ω, 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 ∈ ℕ, X_n est à valeurs dans {1, 2, …, N} et on admettra que la suite de variables aléatoires (X_n)_(n ≥ 0) vérifie pour tout entier n ≥ 1 et tout (x_(n − 1), x_n) ∈ {1, 2, …, N}^2
P_({X_(n − 1) = x_(n − 1)})(X_n = x_n) = P(X_n = x_n|X_(n − 1) = x_(n − 1)) = G(x_n, x_(n − 1))
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 M_(N, 1)(ℝ) dont pour tout i ∈ {1, 2, …, N}, la i^(ème) composante est définie par (v_n)_i = P(X_n = i). Vérifier que V_n est bien un vecteur de probabilité.
I.B. 2 Exprimer pour tout (i, j) ∈ {1, 2, …, N}^2 P({X_n = i} ∩ {X_(n − 1) = j}) à l'aide de G et V_(n − 1).
I.B. 3 En déduire que V_n = GV_(n − 1).
I.B. 4 Montrer que pour tout k entier naturel V_k = G^k V_0.

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.

A. Etude d'un exemple

On considère une matrice Q ∈ M_2(ℝ) stochastique et strictement positive. Q peut se mettre sous la forme
Q = (1 − q, q^′; q, 1 − q^′)
avec q ∈ ]0, 1[ et q^′ ∈ ]0, 1[.
II.A. 1 Déterminer l'ensemble des vecteurs V ∈ M_(2, 1)(ℝ) vérifiant QV = V.
II.A. 2 Montrer qu'il existe un unique vecteur de probabilité V_∞ ∈ M_(2, 1)(ℝ) invariant par Q et le calculer.
II.A. 3 Prouver que pour tout entier n ≥ 1
Q^n = 1/(q + q^′)(q^′, q^′; q, q) + ((1 − q − q^′)^n)/(q + q^′)(q, − q^′; − q, q^′)
II.A. 4 En déduire que (Q^n)_(n ≥ 1) converge lorsque n tend vers l'infini vers une matrice dont les deux vecteurs colonnes sont égaux à V_∞.
On cherchera à généraliser ce résultat dans la partie III.

B. Existence d'un vecteur de probabilité invariant

Dans cette section II.B, Q ∈ M_N(ℝ) est une matrice stochastique.
II.B. 1 On note U le vecteur élément de M_(N, 1)(ℝ) dont toutes les composantes valent 1 . Calculer ^t QU.
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 λ une valeur propre réelle de Q telle que |λ| = 1 et V ∈ M_(N, 1)(ℝ) un vecteur propre de Q associé à la valeur propre λ.
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.

C. Unicité d'un vecteur de probabilité invariant

Dans cette section II.C, Q ∈ M_N(ℝ) 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_∞ = ((v_∞)_1; ⋅; ⋅; (v_∞)_N)
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_(M_(N, 1)(ℝ)) soit V est strictement positif.
II.C. 2 Justifier que V_∞ est strictement positif.
On considère à présent un autre vecteur de probabilité noté
W_∞ = ((w_∞)_1; ⋅; ⋅; (w_∞)_N)
invariant par Q. Puis, on définit
α, = min{((w_∞)_i)/((v_∞)_i)| 1 ≤ i ≤ N} = ((w_∞)_(i_0))/((v_∞)_(i_0)) et; V, = W_∞ − αV_∞
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_∞ = αV_∞.
II.C. 6 En conclure que W_∞ = V_∞.
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) ≥ (1 − ρ)/N pour tout i ∈ {1, …, N}.
II.C. 9 Le rôle du paramètre ρ est essentiel pour assurer l'unicité de la solution du système (S). Que se passerait-il pour ρ = 1 et disons N = 3 pour simplifier à l'extrême? (Songer qu'il peut exister des pages Web qui ne pointent vers aucune autre!).

Partie III Validation du PageRank

Dans toute cette partie III, on considère Q ∈ M_N(ℝ) matrice stochastique strictement positive. On notera V_∞ l'unique vecteur de probabilité invariant par Q.

A. Valeurs propres de 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 ∈ M_(N, 1)(ℝ) on a
‖QV‖_1 ≤ ‖V‖_1
avec de plus ‖QV‖_1 = ‖V‖_1 lorsque V est positif.
III.A. 2 En déduire que pour toute valeur propre réelle λ de Q, on a |λ| ≤ 1.
Soient λ une valeur propre réelle de Q telle que |λ| = 1, et V ∈ M_(N, 1)(ℝ) un vecteur propre de Q associé à λ tel que ‖V‖_1 = 1. On sait grâce au II.B. 5 que |V| = V_∞.
III.A. 3 Etablir l'identité
|∑_(j = 1)^N Q(1, j)v_j| = ∑_(j = 1)^N Q(1, j)|v_j|
où v_i est la i^(ème) composante de V pour i ∈ {1, …, N}.
III.A. 4 En déduire en utilisant P 3 que V est colinéaire à |V| puis que λ = 1.

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 (Q^n)_(n ≥ 1) converge, lorsque n tend vers l'infini, vers la matrice Q_∞ dont les vecteurs colonnes sont tous égaux à V_∞.
III.B. 1 Montrer qu'il existe une matrice diagonale D ∈ M_N(ℝ) et une matrice inversible S ∈ M_N(ℝ), telles que pour tout n ≥ 1, Q^n = SD^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 (Q^n)_(n ≥ 1) converge vers une matrice Q_∞.
III.B. 4 Prouver que pour tout n ≥ 1, Q^n est stochastique puis que Q_∞ est stochastique.
III.B. 5 Démontrer que QQ_∞ = Q_∞.
III.B. 6 En déduire que chacun des vecteurs colonnes de Q_∞ est invariant par Q.
III.B. 7 Conclure.
On admettra pour la partie III.C que (Q^n)_(n ≥ 1) converge lorsque n tend vers l'infini vers la matrice Q_∞ dont les vecteurs colonnes sont tous égaux à V_∞ sous les seules hypothèses Q stochastique et strictement positive.

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_∞ la variable aléatoire à valeurs dans {1, …, N} dont la loi est définie par
P(X_∞ = i) = p(i) pour tout i ∈ {1, 2, …, N}.
III.C. 1 Montrer que (X_n)_(n ≥ 0) converge en loi vers X_∞ 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"?

Pas de description pour le moment