Connectez-vous pour consulter le corrigé.
Dans tout le problème, \(n\) désigne un entier supérieur ou égal à \(2\).
On dispose d’une urne contenant \(n\) jetons, numérotés de \(1\) à \(n\). On vide l’urne en tirant, au hasard et sans remise, les jetons un à un. La suite \((a_1,a_2, \dots, a_n)\) des numéros tirés est aussi appelée permutation de l’ensemble \(\{1,2,\dots,n\}\).
Étant donnés deux entiers \(k\) et \(p\) vérifiant \(1 \leqslant k \leqslant p \leqslant n\), la suite \((a_k, \dots, a_p)\) — se réduisant à \((a_k)\) dans le cas où \(k\) est égal à \(p\) — est appelée sous-suite de \((a_1,a_2,\dots, a_n)\) et son nombre d’éléments est appelé longueur de cette sous-suite.
On admet que cette expérience aléatoire peut être modélisée par un espace probabilisé \((\Omega,\mathcal{A},\mathbb{P})\) où :
\(\Omega\) est l’ensemble des permutations de \(\{1,2,\dots,n\}\),
\(\mathcal{A}= \mathcal{P}(\Omega)\) est l’ensemble des parties de \(\Omega\),
\(\mathbb{P}\) est la probabilité uniforme, c’est-à-dire que : \[\forall \omega\in \Omega,\ \mathbb{P}(\{\omega\})=\frac{1}{\mathrm{Card}(\Omega)}.\]
Quel est le nombre de permutations de \(\left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\) ?
Soit \(X\) une variable aléatoire définie sur \((\Omega,\mathcal{A},\mathbb{P})\). Justifier l’existence de l’espérance, notée \(\mathbb{E}(X)\) et de la variance, notée \(\mathbb{V}(X)\), de \(X\).
On suppose que \(X\) est une variable aléatoire définie sur \((\Omega,\mathcal{A},\mathbb{P})\) et prenant ses valeurs dans \(\left[\kern-0.15em\left[ {1,m} \right]\kern-0.15em\right]\), où \(m\) est un entier naturel non nul.
Pour tout entier \(k\) compris entre \(1\) et \(m\), exprimer \(\mathbb{P}(X=k)\) en fonction de certaines des probabilités \(\mathbb{P}(X\geqslant i)\) où \(i\in \mathbb{N}\).
En déduire que : \[\mathbb{E}(X)=\sum_{k=1}^m \mathbb{P}(X\geqslant k).\]
Prouver également que : \[\mathbb{E}(X^2)=\sum_{k=1}^m (2k-1)\;\mathbb{P}(X\geqslant k).\]
Étant donnée une permutation \((a_1,a_2, \dots, a_n)\) de \(\{1,2,\dots,n\}\), la première sous-suite croissante est définie de la façon suivante :
si \(a_1<a_2<\dots<a_n\), la première sous-suite croissante est \((a_1,a_2, \dots, a_n)\),
sinon, en notant \(k\) le plus petit entier de \(\{1,\dots,n-1\}\) tel que \(a_k>a_{k+1}\), la première sous-suite croissante est \((a_1, \ldots, a_k)\).
On note \(L\) la variable aléatoire définie sur \((\Omega,\mathcal{A},\mathbb{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)\), la première sous-suite croissante est \((2,3,5)\) et : \(L(\omega)=3\).
On suppose, dans cette question uniquement, que \(n=3\).
Écrire toutes les permutations de \(\{1,2,3\}\).
Déterminer l’ensemble \(L(\Omega)\) des valeurs prises par \(L\).
Déterminer la loi de \(L\).
Calculer l’espérance et la variance de \(L\).
On revient désormais au cas général.
Déterminer l’ensemble \(L(\Omega)\) des valeurs prises par \(L\).
Calculer \(\mathbb{P}(L=n)\) et \(\mathbb{P}(L=n-1)\).
Montrer que : \[\forall k\in \left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right],\ \mathbb{P}(L\geqslant k)=\frac{1}{k!}.\]
En déduire la loi de \(L\).
Déterminer la limite de \(\mathbb{E}(L)\) quand \(n\) tend vers l’infini.
Soit \((a_1,a_2, \dots, a_n)\) une permutation de \(\{1,2,\dots,n\}\). Sa première sous-suite croissante est notée \((a_1, \ldots, a_k)\).
Si celle-ci 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 \((a_{k+1}, \dots, a_n)\) est appelée deuxième sous-suite croissante de \((a_1,a_2, \ldots, a_n)\).
On note alors \(L'\) la variable aléatoire définie sur \((\Omega,\mathcal{A},\mathbb{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 on a : \(L'(\omega)=2\).
On suppose, dans cette question seulement, que \(n\) est égal à \(3\).
Montrer que la loi du couple \((L,L')\) est donnée par le tableau suivant :
| \diagbox{$L'$}{$L$} | 1 | 2 | 3 |
| 0 | 0 | 0 | $\dfrac{1}{6}$ |
| 1 | $\dfrac{1}{6}$ | $\dfrac{1}{3}$ | 0 |
| 2 | $\dfrac{1}{3}$ | 0 | 0 |
En déduire la loi de \(L'\).
Calculer l’espérance et la variance de \(L'\).
Calculer la covariance de \(L\) et de \(L'\). Son signe était-il prévisible ?
On revient désormais au cas général, où \(n\) est un entier quelconque supérieur ou égal à \(2\).
Déterminer la plus petite et la plus grande des valeurs prises par \(L'\).
Calculer \(\mathbb{P}(L'=0)\) et \(\mathbb{P}(L'=n-1)\).
Combien y a-t-il de parties de \(\{1,2,\dots,n\}\) distinctes de \(\varnothing,\{1\}, \{1,2\}, \dots, \{1,2,\dots,n-1\}\) ?
En déduire la valeur de \(\mathbb{P}(L+L'=n)\).
Montrer de même que : \[\forall k\in \left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right],\ \mathbb{P}(L+L'\geqslant k)=\frac{2^k-k}{k!}.\]
En déduire une expression de \(\mathbb{E}(L')\) sous forme de somme puis sa limite quand \(n\) tend vers l’infini.
Soit \((a_1,a_2, \dots, a_n)\) une permutation de \(\{1,2,\dots,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, puis la quatrième, etc, jusqu’à ce que l’on ait défini une sous-suite croissante se terminant par \(a_n\).
On note alors \(T\) la variable aléatoire définie sur \((\Omega,\mathcal{A},\mathbb{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)\), et on a : \(T(\omega)=4\).
On suppose, dans cette question uniquement, que \(n=2\).
Déterminer la loi de \(T\).
Calculer l’espérance et la variance de \(T\).
On suppose, dans cette question uniquement, que \(n=3\).
Déterminer la loi de \(T\) et calculer son espérance et sa variance.
Déterminer la loi conjointe du couple \((L,T)\).
Calculer la covariance du couple \((L,T)\).
On suppose désormais que \(n\) est supérieur ou égal à \(4\).
Déterminer l’ensemble \(T(\Omega)\) des valeurs prises par \(T\).
Calculer \(\mathbb{P}(T=1)\) et \(\mathbb{P}(T=n)\).
Comparer les événements \([L+L'=n]\) et \([T\leqslant 2]\). En déduire la valeur de \(\textbf{P}([T=2])\).
Donner la loi de \(T\) dans le cas où \(n\) vaut \(4\) puis calculer son espérance et sa variance.
Pour tout entier \(i\) de \(\{1,2,\dots,n-1\}\), on note :
\(A_i\) l’ensemble des permutations \((a_1,a_2, \dots, a_n)\) vérifiant \(a_i>a_{i+1}\),
\(X_i\) la variable aléatoire qui, à toute permutation \(\omega\), associe \(1\) si \(\omega \in A_i\) et \(0\) sinon.
Montrer que \(X_i\) suit la loi de Bernoulli de paramètre \(\dfrac{1}{2}\) et préciser son espérance et sa variance.
Donner une expression de \(T\) en fonction des variables aléatoires \(X_1,\dots,X_n\).
En déduire que : \[\mathbb{E}(T)=\dfrac{n+1}{2}.\]
Montrer que : \[\forall i \in\{1,\dots,n-2\},\ \mathbb{P}(A_i\cap A_{i+1})=\dfrac{1}{6}.\] En déduire la valeur de \(\mathrm{Cov}(X_i, X_{i+1})\).
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.
Prouver finalement que : \[\mathbb{V}(T)=\dfrac{n+1}{12}.\]
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 à \(\displaystyle \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é \(\mathbb{P}(2,95< S < 3,05)\).
On s’intéresse au programme Python suivant,
qui sera complété plus loin.
import numpy.random as rd
import numpy as np
def experience(n):
A=np.arange(1,n+1)
for i in range(n-1):
alea=rd.randint(n-i)
aux=A[alea]
A[alea]=A[n-i-1]
A[n-i-1]=aux
return A
On suppose que les valeurs successives de alea à
l’appel de experience(5) sont \(3,1,2\) et \(1\). Donner la valeur renvoyée par la
fonction.
Quelles valeurs successives doit prendre alea pour
obtenir, à la fin de l’exécution de l’exécution de
experience(5), le tableau
A=[3,5,2,4,1]?
Expliquer pourquoi la fonction ci-dessus permet de simuler l’expérience aléatoire décrite au début du problème.
Écrire une fonction def T(A) qui
renvoie le nombre de sous-suites croissantes du tableau A
correspondant à une permutation de \(\{1,\ldots,n\}\).
On suppose que le programme est complété par les instructions suivantes :
n=int(input("Entrez n : "))
S=0
for k in range(1000):
A=experience(n)
S=S+T(A)
print(S/1000)
Après exécution du programme pour \(n=5\), la valeur affichée de S
est \(2,98\). Ce résultat est-il
étonnant?
Le corrigé pas à pas, les aides et les explications sont disponibles dans la plateforme.