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

\title{ECOLE DES HAUTES ETUDES COMMERCIALES E.S.C.P. - E.A.P. ECOLE SUPERIEURE DE COMMERCE DE LYON }

\author{CONCOURS D'ADMISSION SUR CLASSES PREPARATOIRES}
\date{}


\begin{document}
\maketitle


\section*{OPTION ECONOMIQUE}
\section*{MATHEMATIQUES II}
Mercredi 9 Mai 2001, de 8h. à 12h.

\begin{abstract}
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.
\end{abstract}

Dans tout le problème, \(n\) désigne un entier supérieur ou égal à 2 .\\
On dispose de \(n\) jetons numérotés de 1 à \(n\). On tire, au hasard et sans remise, les jetons un à un. La suite ( \(a_{1}, a_{2}, \ldots, a_{n}\) ) des numéros tirés est aussi appelée permutation de l'ensemble \(\{1,2, \ldots, n\}\).\\
Étant donné deux entiers \(k\) et \(p\) vérifiant \(1 \leqslant k \leqslant p \leqslant n\), la suite ( \(a_{k}, \ldots, a_{p}\) ) - se réduisant à ( \(a_{k}\) ) dans le cas où \(k\) est égal à \(p\) - est appelée sous-suite de \(\left(a_{1}, a_{2}, \ldots, a_{n}\right)\) et son nombre d'éléments est appelé longueur de cette sous-suite.\\
On admettra que cette expérience aléatoire peut être modélisée par la donnée de l'univers \(\Omega\), ensemble des permutations de \(\{1,2, \ldots, n\}\), muni de la tribu de ses parties \(\mathcal{P}(\Omega)\) et de la probabilité uniforme \(\mathbf{P}\), ce qui signifie que, pour toute permutation \(\omega\) de \(\{1,2, \ldots, n\}\), on a : \(\mathbf{P}(\{\omega\})=\frac{1}{n!}\).\\
Si \(X\) est une variable aléatoire définie sur \((\Omega, \mathcal{P}(\Omega), \mathbf{P})\), on note \(\mathrm{E}(X)\) son espérance et \(\mathrm{V}(X)\) sa variance.\\
Si \(X\) et \(Y\) sont deux variables aléatoires définies sur \((\Omega, \mathcal{P}(\Omega), \mathbf{P})\), on note \(\operatorname{Cov}(X, Y)\) leur covariance.

\section*{Préliminaire}
Soit \(X\) une variable aléatoire prenant ses valeurs dans \(\{1,2, \ldots, m\}\) où \(m\) est un entier supérieur ou égal à 2 .\\
Montrer l'égalité : \(\quad \mathbf{E}(X)=\sum_{k=1}^{m} \mathbf{P}([X \geqslant k])\).

\section*{Partie 1 : Première sous-suite croissante}
Étant donné une permutation \(\left(a_{1}, a_{2}, \ldots, a_{n}\right)\) de \(\{1,2, \ldots, n\}\), la première sous-suite croissante est définie de la façon suivante : dans le cas \(a_{1}<a_{2}<\cdots<a_{n}\), la première sous-suite croissante est ( \(a_{1}, a_{2}, \ldots, a_{n}\) ); dans le cas contraire, \(k\) étant le plus petit entier de \(\{1, \ldots, n-1\}\) vérifiant \(a_{k}>a_{k+1}\), la première sous-suite croissante est ( \(a_{1}, \ldots, a_{k}\) ).

Soit \(L\) la variable aléatoire définie sur \((\Omega, \mathcal{P}(\Omega), \mathrm{P})\) qui, à toute permutation \(\omega\), associe la longueur de sa première sous-suite croissante.\\
Par exemple, si \(n=9\) et \(\omega=(2,3,5,4,9,6,7,8,1)\), comme \(2<3<5\) et \(5>4\), on a : \(L(\omega)=3\).

\begin{enumerate}
  \item a) Quelles sont la plus petite et la plus grande des valeurs prises par \(L\) ? Que vaut \(\mathbf{P}([L=n])\) ?\\
b) Montrer que, pour tout entier \(k\) de \(\{1,2, \ldots, n\}\), on a : \(\mathbf{P}([L \geqslant k])=\frac{1}{k!}\). En déduire la loi de \(L\).
  \item Donner la valeur de \(\mathrm{E}(L)\) sous forme d'une somme et déterminer la limite de \(\mathrm{E}(L)\) quand \(n\) tend vers l'infini.
\end{enumerate}

\section*{Partie 2 : Deuxième sous-suite croissante}
Étant donné une permutation \(\left(a_{1}, a_{2}, \ldots, a_{n}\right)\) de \(\{1,2, \ldots, n\}\) et sa première sous-suite croissante \(\left(a_{1}, \ldots, a_{k}\right)\); si celleci se termine par \(a_{n}\) (i.e. si \(k=n\) ), on dit que la deuxième sous-suite croissante n'existe pas; dans le cas contraire, la première sous-suite croissante de \(\left(a_{k+1}, \ldots, a_{n}\right)\) est appelée deuxième sous-suite croissante de ( \(a_{1}, a_{2}, \ldots, a_{n}\) ).\\
Soit \(L^{\prime}\) la variable aléatoire définie sur \((\Omega, \mathcal{P}(\Omega), \mathbf{P})\) qui, à toute permutation \(\omega\), associe 0 s'il n'existe pas de deuxième sous-suite croissante, et la longueur de la deuxième sous-suite croissante, dans le cas contraire.\\
Par exemple, si \(n=9\) et \(\omega=(2,3,5,4,9,6,7,8,1)\), la deuxième sous-suite croissante est ( 4,9 ) et l'on a : \(L^{\prime}(\omega)=2\).

\begin{enumerate}
  \item Quelles sont la plus petite et la plus grande des valeurs prises par \(L^{\prime}\) ? Que vaut \(\mathbf{P}\left(\left[L^{\prime}=0\right]\right)\) ?
  \item On suppose, dans cette question seulement, que \(n\) est égal à 3 .\\
a) Montrer que la loi du couple \(\left(L, L^{\prime}\right)\) est donnée par le tableau suivant:
\end{enumerate}

\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
\(L^{\prime}\) &  &  &  \\
\(L^{\prime}\) & 1 & 2 & 3 \\
\hline
0 & 0 & 0 & \(1 / 6\) \\
\hline
1 & \(1 / 6\) & \(1 / 3\) & 0 \\
\hline
2 & \(1 / 3\) & 0 & 0 \\
\hline
\end{tabular}
\end{center}

b) Donner la loi de \(L^{\prime}\) et calculer son espérance.\\
c) Calculer la covariance de \(L\) et de \(L^{\prime}\). Pouvait-on prévoir le signe de cette covariance?\\
3) On suppose à nouveau que n est un entier quelconque supérieur ou égal à 2 .\\
a) Dénombrer les parties de l'ensemble \(\{1,2, \ldots, n\}\) distinctes de \(\emptyset,\{1\},\{1,2\}, \ldots,\{1,2, \ldots, n-1\}\).\\
b) En déduire \(\mathbf{P}\left(\left[L+L^{\prime}=n\right]\right)\).\\
c) Montrer de même que, pour tout entier \(k\) de \(\{1,2, \ldots, n\}\), on a : \(\mathbf{P}\left(\left[L+L^{\prime} \geqslant k\right]\right)=\frac{2^{k}-k}{k!}\).\\
d) Donner la valeur de \(\mathrm{E}\left(L+L^{\prime}\right)\) sous forme d'une somme.\\
e) En déduire \(\mathrm{E}\left(L^{\prime}\right)\) et sa limite quand \(n\) tend vers l'infini.

\section*{Partie 3 : Nombre de sous-suites croissantes}
Étant donné une permutation \(\left(a_{1}, a_{2}, \ldots, a_{n}\right)\) de \(\{1,2, \ldots, n\}\), si sa deuxième sous-suite croissante existe et ne se termine pas par \(a_{n}\), on définit la troisième sous-suite croissante à l'instar de la deuxième, etc., jusqu'à ce que l'on ait défini une sous-suite croissante se terminant par \(a_{n}\).\\
Soit \(T\) la variable aléatoire définie sur ( \(\Omega, \mathcal{P}(\Omega), \mathbf{P}\) ) qui, à toute permutation \(\omega\), associe le nombre de ses sous-suites croissantes.\\
Par exemple, si \(n=9\) et \(\omega=(2,3,5,4,9,6,7,8,1)\), comme les sous-suites croissantes sont \((2,3,5),(4,9),(6,7,8)\) et (1), on a : \(T(\omega)=4\).

\begin{enumerate}
  \item a) Donner la loi de \(T\) dans le cas où \(n\) vaut 2 . Calculer son espérance et sa variance.\\
b) Donner la loi de \(T\) dans le cas où \(n\) vaut 3 . Calculer son espérance et sa variance.
  \item On suppose désormais l'entier \(n\) supérieur ou égal à 4 .\\
a) Calculer \(\mathbf{P}([T=1])\) et \(\mathbf{P}([T=n])\).\\
b) Comparer les événements \(\left[L+L^{\prime}=n\right]\) et \([T \leqslant 2]\). En déduire la valeur de \(\mathbf{P}([T=2])\).\\
c) Donner la loi de \(T\) dans le cas où \(n\) vaut 4 . Calculer son espérance et sa variance.
  \item Pour tout entier \(i\) de \(\{1,2, \ldots, n-1\}\), soit \(A_{i}\) l'événement égal à l'ensemble des permutations ( \(a_{1}, a_{2}, \ldots, a_{n}\) ) vérifiant \(a_{i}>a_{i+1}\), et soit \(X_{i}\) la variable aléatoire qui, à toute permutation \(\omega\), associe 1 si \(\omega \in A_{i}\) et 0 sinon.\\
a) Montrer que \(X_{i}\) suit la loi de Bernoulli de paramètre \(\frac{1}{2}\). Donner son espérance et sa variance.\\
b) Donner une expression de \(T\) en fonction de \(X_{i}\). En déduire l'égalité : \(\mathrm{E}(T)=\frac{n+1}{2}\).\\
c) Montrer que l'on a: \(\forall i \in\{1, \ldots, n-2\}, \mathbf{P}\left(A_{i} \cap A_{i+1}\right)=\frac{1}{6}\). En déduire la valeur dc \(\operatorname{Cov}\left(X_{i}, X_{i+1}\right)\).\\
d) Montrer que, pour tout couple \((i, j)\) d'entiers vérifiant \(1 \leqslant i<i+2 \leqslant j \leqslant n-1\), les événements \(A_{i}\) et \(A_{j}\) sont indépendants.\\
En déduire l'égalité : \(\operatorname{Cov}\left(X_{i}, X_{j}\right)=0\).\\
e) Établir enfin l'égalité : \(\mathrm{V}(T)=\frac{n+1}{12}\).
  \item On suppose maintenant que \(n\) est égal à 5 . On considère 1000 variables aléatoires \(T_{1}, \ldots, T_{1000}\), mutuellement indépendantes, de même loi que la variable \(T\) et on note \(S\) la variable aléatoire égale à \(\frac{1}{1000} \sum_{i=1}^{1000} T_{i}\).\\
On note \(\phi\) la fonction de répartition de la loi normale centrée réduite et on donne la valeur approchée suivante : \(\phi(\sqrt{5}) \simeq 0,987\).\\
Calculer une valeur approchée de la probabilité \(\mathbf{P}([2,95<S<3,05])\).
\end{enumerate}

\section*{Partie 4 : Simulation informatique}
Dans le langage informatique PASCAL, la fonction random renvoie, pour un argument \(m\) de type integer vérifiant \(m \geqslant 1\), un nombre entier aléatoire compris entre 0 et \(m-1\) (cette fonction est initialisée au début du corps principal du programme par la procédure randomize).\\
On rappelle que, dans l'exécution d'une boucle for i \(:=n\) downto 2 , i prend successivement les valeurs \(n, n-1, \ldots, 2\). Dans un programme ćcrit en PASCAL, figurent la déclaration type tableau = array [1..5] of integer; et la procédure :

\begin{verbatim}
procedure aleatoire(var A :tableau);
var aux,i,alea : integer;
begin
    for i :=1 to 5 do A[i] :=i ;
    for i :=5 downto 2 do begin
                alea := random(i)+1 ;
                aux :=A[alea] ;
                A[alea] :=A[i] ;
                A[i] :=aux;
            end
end;
\end{verbatim}

\begin{enumerate}
  \item a) On suppose que les valeurs successives de alea sont \(4,2,3\) et 2 . Donner les valeurs de \(\mathrm{A}[1], \mathrm{A}[2], \mathrm{A}[3]\), A [4] et A [5] à la fin de l'exécution de la procédure.\\
b) Quelles valeurs successives doit prendre alea pour obtenir, à la fin de l'exécution de la procédure le tableau: \(\mathrm{A}[1]=3, \mathrm{~A}[2]=5, \mathrm{~A}[3]=2, \mathrm{~A}[4]=4, \mathrm{~A}[5]=1\) ?\\
c) Expliquer pourquoi la procédure ci-dessus permet de simuler l'expérience aléatoire définie au début du problème.
  \item Écrire une fonction d'en-tête function T (A :tableau) :integer; qui renvoie le nombre de sous-suites croissantes du tableau A correspondant à une permutation de \(\{1, \ldots, 5\}\).
  \item On suppose que le programme contient les déclarations var A :tableau; var k :integer; var S :real; et que le corps principal du programme est le suivant:
\end{enumerate}

begin

\begin{verbatim}
    randomize ;
    S :=0 ;
    for k :=1 to 1000 do begin
            aleatoire(A) ;
            S :=S+T(A) ;
        end;
    S :=S/1000 ;
    writeln(S) ;
end.
\end{verbatim}

Après exécution du programme la valeur affichée de S est 2,98 . Ce résultat est-il étonnant?


\end{document}