Dans cet article, on va revenir sur les questions d’informatique du sujet de concours suivant : emlyon 2021 ECS. Les questions de Scilab ont été traduites en Python, pour te permettre de t’entraîner en informatique. Tu peux utiliser cet article comme traduction de la partie Scilab du sujet d’origine, ou bien comme un exercice sur les thèmes de Python abordés par le sujet, à savoir : approximation d’une limite, simulation d’une variable aléatoire et simulation d’une espérance.
Problème 1
✅ Cet exercice est faisable en première année.
❓ Énoncé
On définit les suites \((u_n)_{n\in\mathbb N^*}\) et \((v_n)_{n\in\mathbb N^*}\) par :
\[\forall n\in\mathbb N^*,\quad u_n=\sum_{k=1}^n\frac1k-\ln(n+1)\quad\text{et}\quad v_n=\sum_{k=1}^n\frac1k-\ln(n).\]
On peut montrer qu’elles convergent vers une même limite \(\gamma\), et que :
\[\forall n\in\mathbb N^*,\quad \left|\frac{u_n+v_n}2-\gamma\right|\leq\frac12(v_n-u_n).\]
En déduire une fonction Python d’en-tête def approx() qui renvoie une approximation du réel \(\gamma\) à \(10^{-5}\) près.
✏️ Corrigé
Tout d’abord, analysons rapidement cet énoncé.
L’inégalité \(\left|\frac{u_n+v_n}2-\gamma\right|\leq\frac12(v_n-u_n)\) est typiquement le genre d’inégalités utilisées chaque fois qu’on veut approximer en Python une limite de suite.
En effet, que signifie : « \(\frac{u_n+v_n}{2}\) est proche du réel \(\gamma\) à \(10^{-5}\) près » ?
Cela veut dire que la distance sur une droite graduée entre les réels \(\frac{u_n+v_n}{2}\) et \(\gamma\) est inférieure à \(10^{-5}\). Ce qui s’écrit symboliquement :
\[\left|\frac{u_n+v_n}2-\gamma\right|\leq 10^{-5}\]
Et donc, selon l’inégalité admise par l’énoncé, si \(\frac12(v_n-u_n)\leq 10^{-5}\), alors \(\left|\frac{u_n+v_n}2-\gamma\right|\leq 10^{-5}\), et ceci signifie exactement que \(\frac{u_n+v_n}{2}\) est proche à \(10^{-5}\) près de \(\gamma\).
Il suffit donc de faire calculer à Python le premier entier \(n\) tel que \(\frac12(v_n-u_n)\leq 10^{-5}\).
De plus, on a \(\frac12(v_n-u_n)=\frac{\ln(n+1)-\ln(n)}2\).
Cela nous simplifie la tâche ! Désormais, on cherche le premier entier \(n\) tel que
\[\frac{\ln(n+1)-\ln(n)}2\leq 10^{-5}\]
Pour cela, on va faire une boucle while, qui calcule \(\frac{\ln(n+1)-\ln(n)}2\) en augmentant cran par cran la valeur de \(n\) tant que cette fraction est strictement supérieure à \(10^{-5}\), et qui s’arrête dès qu’on a trouvé une valeur de \(n\) telle que la fraction est inférieure à \(10^{-5}\).
Une fois passée la boucle while (c’est-à-dire après avoir trouvé la bonne valeur de \(n\)), on renverra la valeur
\[\frac{u_n+v_n}2=\sum_{k=1}^n\frac1k-\frac{\ln(n(n+1))}2\]
On peut donc proposer le programme suivant :
Problème 2
✅ Cet exercice est faisable en première année (sauf la justification de la méthode d’estimation).
❓ Énoncé
On dispose d’une urne rouge et d’une urne bleue, ainsi que de \(n\) boules rouges et de \(n\) boules bleues, ces \(2n\) boules étant supposées indiscernables au toucher.
Initialement, on place les \(n\) boules rouges dans l’urne rouge et les \(n\) boules bleues dans l’urne bleue.
On procède alors à une succession d’épreuves aléatoires, chaque épreuve consistant à échanger au hasard une boule de l’urne rouge avec une boule de l’urne bleue. Après chaque épreuve, chaque urne contient donc toujours \(n\) boules.
Pour tout entier \(k\) de \(\mathbb N^*\), on définit la variable aléatoire \(Z_k\) égale au nombre de boules rouges présentes dans l’urne rouge à l’issue de la \(k^{\text{ième}}\) épreuve. On pose également \(Z_0=n\).
On pourra remarquer que, après chaque épreuve, le nombre de boules rouges dans l’urne rouge est toujours égal au nombre de boules bleues dans l’urne bleue.
1) Recopier et compléter les lignes incomplètes de la fonction Python suivante pour que, prenant en entrée le nombre \(n\) initial de boules rouges et le nombre \(k\) d’épreuves réalisées, elle renvoie une simulation de \(Z_k\).
2) Écrire une fonction Python d’en-tête def esperance(n,k) qui, prenant en entrée le nombre \(n\) initial de boules rouges et le nombre \(k\) d’épreuves réalisées, renvoie une simulation de l’espérance de \(Z_k\).
On justifiera, en particulier, la méthode d’estimation.
✏️ Corrigé
1) Analysons cette fonction Python point par point.
D’abord, comme indiqué généreusement par le commentaire en ligne 3, on initialise une variable R, qui représente le nombre de boules rouges dans l’urne rouge, avec comme valeur initiale n. C’est cohérent avec la situation initiale décrite par l’énoncé (\(n\) boules dans chaque urne).
Ensuite, avec une boucle for, on effectue \(k\) épreuves aléatoires.
Ce qu’il faut savoir remarquer rapidement, c’est que le booléen [aleaR <= R/n] est une simulation de l’événement \(A\) : « on tire une boule rouge dans l’urne rouge ». Expliquons ci-dessous pourquoi.
Puisqu’il y a R est le nombre de boules rouges dans l’urne rouge, \(P(A)=R/n\).
⚠️ Méthode classique : pour simuler \(A\), on simule un nombre aléatoire dans \([0,1]\), et alors le booléen [aleaR <= R/n] vaut True avec une probabilité R/n. On l’utilise donc comme simulation de l’événement \(A\), car il vaut True avec la même fréquence que la probabilité de \(A\).
Comme rappelé par l’énoncé, R est aussi égale au nombre de boules bleues dans l’urne bleue. Ainsi, de façon analogue : « on tire une boule bleue dans l’urne bleue » peut être simulé par [aleaB <= R/n] ; « on tire une boule rouge dans l’urne bleue » peut être simulé par [aleaB > R/n] ; « on tire une boule bleue dans l’urne rouge » peut être simulé par [aleaR > R/n].
Observons que, lorsqu’on tire une boule rouge dans l’urne rouge et une boule bleue dans l’urne bleue, l’urne rouge perd une boule rouge. Quand on tire deux boules de même couleur, ça ne change rien au nombre de boules rouges dans l’urne rouge. Enfin, quand on tire des boules de couleur différente de l’urne (bleue dans l’urne rouge et rouge dans l’urne bleue), l’urne rouge gagne une boule rouge.
Il faut donc compléter le programme de la manière suivante :
2) Pour simuler l’espérance de \(Z_k\), on va faire un grand nombre de simulations de \(Z_k\) et calculer la moyenne des simulations de \(Z_k\).
Justifions, comme demandé, la méthode d’estimation utilisée. Autrement dit : pourquoi utilise-t-on la moyenne pour simuler l’espérance ?
En fait, cette méthode d’estimation est « cohérente » parce que la moyenne empirique est un estimateur sans biais de l’espérance. C’est-à-dire que si \(X_1,\dots,X_n\) sont des variables indépendantes et toutes de même loi que \(Z_k\), alors \(E\left(\frac{X_1+\cdots+X_n}n\right)=E(Z_k)\). C’est donc une « bonne » estimation de l’espérance.
Voici deux façons de faire ce programme.
La plus classique :
La plus courte :
Conclusion
À l’issue de ces quelques programmes étudiés grâce à ce sujet, récapitulons quelques techniques à retenir :
- Pour faire une approximation de la limite \(\ell\) d’une suite \((u_n)\) à \(\varepsilon\) près : on calcule, via une boucle while, le plus petit entier \(n\) tel que \(|u_n-\ell|\leq\varepsilon\), puis pour cette valeur calculée de \(n\), on renvoie \(u_n\). Il faut savoir aussi adapter la condition dans la boucle while en utilisant les inégalités précédemment démontrées dans le sujet (ce qui généralement simplifie le programme).
- Pour simuler un événement de probabilité \(p\) : on simule un nombre aléatoire a dans l’intervalle \([0,1]\), puis on utilise le booléen [a<=p], qui vaut True avec la probabilité \(p\). (Ce n’est pas la seule manière de faire, on aurait pu également utiliser le booléen [rd.binomial(1,p)==1] par exemple.)
- Retenir la manière condensée de calculer une somme (pour ne pas être dérouté(e) si jamais cette écriture est employée dans un sujet de concours).
