Rapport du jury Mines Ponts 2018

Questions du sujet

1. Montrer que pour toute variable aléatoire $X$ réelle à valeurs dans $\{1,\ldots,n\}$ et pour tout $m \in \{1,\ldots,n\}$,
\[ E(X) \leq m + 1 + n P(X \geq m). \]

2. À l’aide d’une comparaison entre une somme et une intégrale, montrer que
\[ n \ln(n) - n + 1 \leq \sum_{k=1}^n \ln(k). \]
En déduire l’inégalité
\[ \frac{n^n}{e^n} \leq n! \]

3. Justifier que $u$ et $u$ sont bien définies. Montrer qu’elles sont monotones puis qu’elles convergent.

4. Montrer que $u$ est la plus petite suite (au sens de $\preceq$) qui est décroissante et plus grande que $u$. Montrer de même que $u$ est la plus grande suite (au sens de $\preceq$) qui est croissante et plus petite que $u$.

5. Si $v = (v_n)_{n \in \mathbb{N}^*}$ est une autre suite réelle bornée plus grande que $u$, comparer les limites de $u$ et de $v$.}

6. Montrer que $u$ et $u$ sont adjacentes si et seulement si $u$ converge. En ce cas, que peut-on dire des limites des trois suites $u$, $u$ et $u$ ?

7. Soit $m$ et $n$ deux entiers naturels non nuls tels que $m \geq 2n$. On note $q$ le quotient et $r$ le reste de la division euclidienne de $m$ par $n$. Montrer que
\[ u_m \leq (q-1)u_n + u_{n+r} \]
et en déduire l’inégalité
\[ \frac{u_m}{m} \leq \frac{m-n-r}{m}\cdot \frac{u_n}{n} + \frac{\max\{u_n,u_{n+1},...,u_{2n-1}\}}{m}. \]

8. En déduire que la suite $\left(\frac{u_m}{m}\right)_{m\in\mathbb{N}^*}$ est bornée, puis que pour tout $n\in\mathbb{N}^*$,
\[
\lim_{m\to+\infty} \frac{u_m}{m} \leq \frac{u_n}{n}.
\]

9. En conclure que la suite $\left(\frac{u_n}{n}\right)_{n\in\mathbb{N}^*}$ converge.

10. Montrer que si $P(X_1 < x) = 1$, alors pour tout $n \in \mathbb{N}^*$, $P(Y_n < x) = 1$ et que si $P(X_1 \geq x) > 0$, alors pour tout $n \in \mathbb{N}^*$, $P(Y_n \geq x) > 0$.}

11. Soit $m$ et $n$ deux entiers naturels non nuls. Montrer l’inclusion d’événements suivante :
\[
\left\{Y_m \geq x \right\} \cap \left\{ \frac{1}{n} \sum_{k=m+1}^{m+n} X_k \geq x\right\} \subset \left\{ Y_{m+n} \geq x\right\}
\]
et en déduire l’inégalité
\[
P(Y_{m+n} \geq x) \geq P(Y_m \geq x)P(Y_n \geq x).
\]

12. Démontrer la convergence de la suite
\[
\left( P(Y_n \geq x)^{1/n} \right)_{n\in\mathbb{N}^*}
\]

13. À l’aide d’un raisonnement par récurrence sur le nombre $s$ de piles, montrer qu’à l’issue du processus, pour tout jeton de valeur $z$ de la dernière pile, il existe une liste $b = (b_1,\ldots,b_s)$ de réels extraite de la liste $a$ vérifiant :
\begin{itemize}
\item $b$ est décroissante et de longueur $s$ ;
\item pour tout $i \in \{1,\ldots,s\}$ le jeton n°$i$ de valeur $b_i$ est dans la $i$-ème pile en partant de la gauche ;
\item $b_s = z$.
\end{itemize}

14. En déduire que la liste $a$ admet au moins une liste extraite croissante de longueur $p+1$ ou une liste extraite décroissante de longueur $q+1$.

15. Les variables aléatoires réelles $A_1, A_2, ..., A_n$ sont-elles mutuellement indépendantes ?}

16. Soit $k \in \{1,...,n\}$ et $s = (s_1, ..., s_k)$ une liste croissante de longueur $k$ d’éléments de $\{1,...,n\}$. On note $A_s$ l’événement : « la liste $(A_{s_1},..., A_{s_k})$ est croissante ». Montrer que $P(A_s) = \frac{1}{k!}$.

17. Démontrer que $C_n$ et $D_n$ ont la même loi. Démontrer alors, à l’aide du résultat de la question 14, que :
\[
\mathbb{E}(C_n) \geq \sqrt{\frac{n}{2}}.
\]

18. Démontrer que pour tout $k \in \{1,...,n\}$,
\[
P(C_n \geq k) \leq \frac{\binom{n}{k}}{k!}.
\]

19. Soit $n$ un entier naturel non nul et $\alpha$ un réel strictement supérieur à $1$.
Justifier qu’il existe un entier naturel non nul $k$ tel que $k-1 < \alpha e \sqrt{n} \leq k$. À l’aide du résultat de la question 2, déduire de la question précédente que \[ P(C_n \geq \alpha e \sqrt{n}) \leq \left(\frac{1}{\alpha}\right)^{2\alpha e \sqrt{n}}. \] 20. En déduire qu’il existe une suite $(\epsilon_n)_{n\in\mathbb{N}^*}$ tendant vers $0$ telle que, pour tout $n \in \mathbb{N}^*$, \[ \frac{\mathbb{E}(C_n)}{\sqrt{n}} \leq \left( 1 + n^{-1/4} \right)e + \epsilon_n. \] En conclure que $\lim_{n \to +\infty} \frac{\mathbb{E}(C_n)}{\sqrt{n}}$ existe et que $\lim_{n \to +\infty} \frac{\mathbb{E}(C_n)}{\sqrt{n}} \leq e$. }

Questions du sujet

1. Montrer que la matrice $A = I_2$ admet une infinité de racines carrées (on pourra utiliser la notion de symétrie). Lesquelles sont des polynômes en $A$ ?

2. Montrer que $A = \begin{pmatrix}0 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{pmatrix}$ admet une infinité de racines carrées et qu’aucune d’entre elles n’est un polynôme en $A$.

3. Montrer que $A$ admet une unique racine carrée symétrique réelle définie positive.\\
(On pourra montrer que deux racines carrées de ce type possèdent les mêmes valeurs et sous-espaces propres.)

4. Soit $T = (t_{i,j})_{1 \leq i,j \leq n}$ et $U = (u_{i,j})_{1 \leq i,j \leq n}$ deux matrices complexes triangulaires supérieures. On suppose que $T$ est inversible. Montrer que l’équation $U^2 = T$ est équivalente au système d’équations suivant :\\
\[
\left\{
\begin{array}{l}
u_{i,i}^2 = t_{i,i} \quad (1 \leq i \leq n)\\
(u_{i,i} + u_{j,j})u_{i,j} = t_{i,j} - \sum_{k=i+1}^{j-1} u_{i,k}u_{k,j} \quad (1 \leq i < j \leq n) \end{array} \right. \] Montrer que $T$ étant donnée, on peut résoudre ce système en choisissant une solution $U$ telle que $u_{i,i} + u_{j,j} \neq 0$ pour tous $i, j \in \{1,2,...,n\}$. (On pourra considérer les parties réelles et imaginaires des $u_{i,i}$.) 5. En déduire que $A$ admet une racine carrée. Si en outre, les valeurs propres de $A$ appartiennent à $C_e$, montrer que $A$ admet une racine carrée dont les valeurs propres sont de partie réelle strictement positive.\\ On admet qu’une telle racine carrée est unique et on la notera $\sqrt{A}$ dans toute la suite du problème.} 6. Montrer que $\| AB \| \leq \|A\| \|B\|$. 7. On note $m_A$ le polynôme minimal de $A$. Montrer que la matrice $m_A(B)$ est inversible si et seulement si $A$ et $B$ n’ont aucune valeur propre commune.\\ En déduire que s’il existe une matrice $M \in M_n(\mathbb{C})$ non nulle telle que $AM = MB$, alors $A$ et $B$ ont au moins une valeur propre commune. 8. Réciproquement, si $A$ et $B$ ont au moins une valeur propre commune, montrer qu’il existe une matrice $M \in M_n(\mathbb{C})$ non nulle telle que $AM = MB$.\\ (On pourra considérer une matrice de la forme $X Y^T$ où $X$ et $Y$ sont deux matrices colonnes bien choisies). 9. Soit $F : M_n(\mathbb{C}) \rightarrow M_n(\mathbb{C})$ l’application définie par la formule $F(X) = X^2 - A$.\\ Montrer que la différentielle $dF_X$ de $F$ en $X \in M_n(\mathbb{C})$ est donnée par\\ \[ \forall H \in M_n(\mathbb{C}),\quad dF_X(H) = XH + HX. \] Déduire des deux questions précédentes une condition nécessaire et suffisante pour que $dF_X$ soit inversible. Montrer que cette condition implique que $X$ est inversible. 10. Montrer que $dF_{\sqrt{A}}$ est inversible et qu’il existe $r > 0$ tel que $dF_X$ soit inversible pour tout $X \in B(\sqrt{A}, r)$.\\
Pour tout $Y \in B(\sqrt{A}, r)$ on pose $G(Y) = Y - (dF_Y)^{-1}(F(Y))$.}

11. Calculer $G(\sqrt{A})$ et montrer que pour tout $H \in B(0, r)$,
\[
G(\sqrt{A} + H) - G(\sqrt{A}) = \left(dF_{\sqrt{A} + H}\right)^{-1}(H^2)
\]
où
\[
dF_{\sqrt{A} + H}^{-1} = \left(I + (dF_{\sqrt{A}})^{-1} \circ dF_H\right)^{-1} \circ (dF_{\sqrt{A}})^{-1}.
\]

12. En déduire qu’il existe une constante $C > 0$ telle que pour tout $X$ de $B(\sqrt{A}, r)$, $\| G(X) - \sqrt{A} \| \leq C \| X - \sqrt{A} \|^2$. (On pourra utiliser le résultat de la question 6.)

13. Montrer qu’il existe $\Omega > 0$ tel que pour tout $X_0 \in B(\sqrt{A}, \Omega)$ la suite $(X_k)_{k \in \mathbb{N}}$ soit bien définie et vérifie, pour tout $k \in \mathbb{N}$,
\[
\| X_k - \sqrt{A} \| \leq \left(\frac{\Omega \sqrt{C}}{2^k C}\right)
\]
Que peut-on en conclure ?

14. Dans cette partie, on étudie deux algorithmes équivalents à celui de Newton.\\
On rappelle que $A$ désigne une matrice inversible de $M_n(\mathbb{C})$ dont les valeurs propres appartiennent à $C_e$. Soit $U_0$ et $V_0$ deux matrices de $M_n(\mathbb{C})$. Sous réserve d’existence, on note $(U_k)_{k \in \mathbb{N}}$ la suite de matrices de $M_n(\mathbb{C})$ définie par\\
\[
(I)\left\{
\begin{array}{l}
U_0 \in M_n(\mathbb{C})\\
U_{k+1} = U_k + H_k~\text{où}~ H_k \in M_n(\mathbb{C})~\text{vérifie}\\
U_k H_k + H_k U_k = A - U_k^2~\text{pour tout}~k \geq 0
\end{array}
\right.
\]
et $(V_k)_{k \in \mathbb{N}}$ la suite de matrices de $M_n(\mathbb{C})$ définie par
\[
(II)\left\{
\begin{array}{l}
V_0 \in M_n(\mathbb{C})\\
V_{k+1} = \frac{1}{2}(V_k + V_k^{-1} A)~\text{pour tout}~k \geq 0
\end{array}
\right.
\]
Si la suite $(X_k)_{k \in \mathbb{N}}$ est bien définie par (N) et $U_0 = X_0$, montrer que la suite $(U_k)_{k \in \mathbb{N}}$ est bien définie par (I) et égale à $(X_k)_{k \in \mathbb{N}}$. Réciproquement si la suite $(U_k)_{k \in \mathbb{N}}$ est bien définie par (I) et $X_0 = U_0$, montrer que la suite $(X_k)_{k \in \mathbb{N}}$ est bien définie par (N) et égale à $(U_k)_{k \in \mathbb{N}}$.

15. On suppose que $U_0 = V_0$ commute avec $A$. Montrer que la suite $(V_k)_{k \in \mathbb{N}}$ est bien définie par (II) et que pour tout $k \in \mathbb{N}$, $U_k = V_k$ commute avec $A$.\\
(On pourra d’abord montrer que $U_k$ est inversible pour tout $k \in \mathbb{N}$ et considérer la matrice $G_k = \frac{1}{2}\left(U_k^{-1}A - U_k\right)$.)}

16. Montrer que $V_k$ est symétrique réelle définie positive de mêmes vecteurs propres $e_1,...,e_n$ que $A$ dont on notera $\lambda_{k,1}, ... , \lambda_{k,n}$ les valeurs propres correspondantes. Trouver une relation entre $\lambda_{k+1,\ell}$ et $\lambda_{k,\ell}$.

17. Montrer que
\[
\frac{\lambda_{k+1,\ell} - \sqrt{\lambda_\ell}}{\lambda_{k+1,\ell} + \sqrt{\lambda_\ell}}=
\left(
\frac{\mu - \sqrt{\lambda_\ell}}{\mu+\sqrt{\lambda_\ell}}
\right)^{2^{k+1}}.
\]

18. Déterminer la limite de la suite $(V_k)_{k \in \mathbb{N}}$.

19. On considère la suite $(V_k)_{k \in \mathbb{N}}$ définie par la relation (II) avec $V_0 = \sqrt{A}$. Soit $\epsilon >0$ et $i, j$ deux indices distincts de $\{1,...,n\}$. On note $C_1,...,C_n$ les colonnes de la matrice orthogonale $P$ définie dans la partie précédente et on pose $\Delta = \epsilon C_i C_j^T$.\\
Soit $\tilde{V}_0 = V_0 + \Delta$. La matrice $\tilde{V}_1$ est calculée par la relation (II) à partir de $\tilde{V}_0$ et on pose $\Delta_1 = \tilde{V}_1 - V_1$. Ensuite $\tilde{V}_2$ est calculé à partir de $\tilde{V}_1$ par la relation (II), puis $\tilde{V}_3, \tilde{V}_4...$ de la même manière.\\
Montrer les relations suivantes :\\
\[
\left\{
\begin{array}{l}
(V_0+\Delta)^{-1} = V_0^{-1} - V_0^{-1} \Delta V_0^{-1}\\
\Delta_1 = \frac{1}{2}\left(\Delta - V_0^{-1} \Delta V_0^{-1}A\right)
\end{array}
\right.
\]

20. Déterminer la valeur de $\gamma\in\mathbb{R}$ telle que pour tout $k \in \mathbb{N}$,
\[
\tilde{V}_k = \sqrt{A} + \gamma_k \Delta.
\]}

21. On appelle conditionnement de $A$ le rapport entre sa plus grande valeur propre et sa plus petite. Que doit vérifier le conditionnement de $A$ pour que la suite $(\tilde{V}_k)_{k\geq 0}$ converge ?}