Cette page contient 9 exercices.
Probabilités avec Python : exercices corrigés de mathématiques de seconde année, pour les classes de MP, MPI, PC et PSI.
Exercice 1 — Un jeton et quatre cases
| (Oral Centrale 2018) Soit quatre cases numérotées de {1} à {4}. À l’étape {n=0}, un jeton est placé sur la case {1}. Si à l’étape {n}, il se trouve sur la case {k\in\{2,3,4\}}, il va en {k-1}; sinon, il va au hasard sur une des cases {2,3,4}. On note {X_{n}} la variable aléatoire donnant la case à la date {n} et {U_{n}} la colonne des {P(X_{n}=i)} pour {1\leq i\leq 4}.
|
-
La fonction positions(n) renvoie la liste des positions de l’étape {0} à l’étape {n}.
from random import * def positions(n): pos = 1 listpos = [1] for k in range(n): if pos > 1: pos -= 1 else: pos = randint(2,4) listpos.append(pos) return listposOn écrit ensuite une fonction trace(n) représentant la liste de ces positions :
import matplotlib.pyplot as plt def trace(n): listpos = positionsn) plt.clf() plt.plot(listpos,'o-') plt.show()Voici les tracés pour {n=10}, {n=50} et {n=100}:


On peut conjecturer que pour {n} « assez grand » : {\begin{array}{l}\mathbb{P}(X_n=4)\le \mathbb{P}(X_n=3)\\[6pts]\qquad\le \mathbb{P}(X_n=2)\le \mathbb{P}(X_n=1)\end{array}}On écrit frequences(d,n) donnant les fréquences pour {n} dates à partir de la date {d}.def frequences(d,n): listpos = positions(d+n-1)[d::] freqs = [0]*4 for k in range(n): freqs[listpos[k]-1] += 1 return [freqs[k]/n for k in range(4)]Voici quelques résultats obtenus avec cette fonction
>>> frequences(0,1000) [0.324, 0.323, 0.231, 0.122] >>> frequences(0,10000) [0.3353, 0.3352, 0.2211, 0.1084] >>> frequences(1000,10000) [0.3351, 0.3352, 0.2219, 0.1078]
On peut donc raisonnablement penser que: {\begin{array}{l}\displaystyle\lim_{n\to+\infty}\mathbb{P}(X_n=1)=\displaystyle\lim_{n\to+\infty}\mathbb{P}(X_n=2)=\dfrac{1}{3}\\\\\displaystyle\lim_{n\to+\infty}\mathbb{P}(X_n=3)=\dfrac{2}{9},\quad\displaystyle\lim_{n\to+\infty}\mathbb{P}(X_n=4)=\dfrac{1}{9}\end{array}}
-
Pour simplifier, on pose {U_n=(a_n,b_n,c_n,d_n)^{T}}.
Avec le système complet d’événements {(X_n=1),(X_n=2),(X_n=3),(X_n=4)} on trouve respectivement : {\begin{array}{l}\mathbb{P}(X_{n+1}\!=\!1)\!=\!\displaystyle\sum_{k\!=\!1}^{4}\mathbb{P}(X_{n}\!=\!k)\,\mathbb{P}_{(X_{n}\!=\!k)}(X_{n+1}\!=\!2)\\[12pts]\qquad\!=\!\mathbb{P}(X_{n}\!=\!2)\end{array}}
{\begin{array}{l}\mathbb{P}(X_{n+1}\!=\!2)\!=\!\displaystyle\sum_{k\!=\!1}^{4}\mathbb{P}(X_{n}\!=\!k)\,\mathbb{P}_{(X_{n}\!=\!k)}(X_{n+1}\!=\!2)\\[9pts]\qquad\!=\!\dfrac{1}{3}\mathbb{P}(X_{n}\!=\!1)+\mathbb{P}(X_{n}\!=\!3)\end{array}} {\begin{array}{l}\mathbb{P}(X_{n+1}\!=\!3)\!=\!\displaystyle\sum_{k\!=\!1}^{4}\mathbb{P}(X_{n}\!=\!k)\,\mathbb{P}_{(X_{n}\!=\!k)}(X_{n+1}\!=\!3)\\[9pts]\qquad\!=\!\dfrac{1}{3}\mathbb{P}(X_{n}\!=\!1)+\mathbb{P}(X_{n}\!=\!4)\end{array}} {\begin{array}{l}\mathbb{P}(X_{n+1}\!=\!4)\!=\!\displaystyle\sum_{k\!=\!1}^{4}\mathbb{P}(X_{n}\!=\!k)\,\mathbb{P}_{(X_{n}\!=\!k)}(X_{n+1}\!=\!3)\\[9pts]\qquad\!=\!\dfrac{1}{3}\mathbb{P}(X_{n}\!=\!1)\end{array}}Ces résultats se résument en l’égalité matricielle : {U_{n+1}=AU_{n}\text{\ avec\ }A=\dfrac{1}{3}\begin{pmatrix}0&3&0&0\\ 1&0&3&0\\ 1&0&0&3\\ 1&0&0&0 \end{pmatrix}}
-
On diagonalise {A}. On trouve :
{\begin{array}{rl}\chi_{A}(\lambda)&=\dfrac{1}{81}\begin{vmatrix}3\lambda&-3&0&0\\ -1&3\lambda&-3&0\\ -1&0&3\lambda&-3\\ -1&0&0&3\lambda\end{vmatrix}\\\\&=\lambda^4+\dfrac{1}{27}\begin{vmatrix}-1&-3&0\\-1&3\lambda&-3\\-1&0&3\lambda\end{vmatrix}\\\\&=\lambda^4+\dfrac{1}{27}(-9\lambda^2-9-9\lambda)\\\\&=\lambda^4-\dfrac{1}{3}(\lambda^2+\lambda+1)\end{array}}NB: on peut trouver {\chi_{A}} plus vite, car c’est le déterminant d’une matrice-compagnon.
On ne trouve pas mieux que la factorisation : {\chi_{A}(\lambda)=\dfrac{1}{3}(\lambda-1)(3\lambda^3+3\lambda^2+2\lambda+1)}Le fait que {\lambda=1} soit valeur propre n’est pas étonnant ({A} est stochastique).
La matrice {A-I_3=\dfrac{1}{3}\begin{pmatrix}-3&3&0&0\\ 1&-3&3&0\\ 1&0&-3&3\\ 1&0&0&-3 \end{pmatrix}} est de rang {3}, donc {E_A(1)} est une droite.
Un vecteur directeur de {E_A(1)} est {\varepsilon_1=(3,3,2,1)}.
On finit la diagonalisation de {A} avec Python :
>>> A = np.array([[0,3,0,0],[1,0,3,0] [1,0,0,3],[1,0,0,0]])/3 >>> [a,b,c,d] = np.linalg.eigvals(A); >>> np.round([a,b,c,d],5) array([ 1.+0.j, -0.71806+0.j, -0.14097+0.66659j, -0.14097-0.66659j]) >>> np.abs([a,b,c,d]); array([1., 0.71805717, 0.68133369, 0.68133369])
Il y a donc quatre valeurs propres distinctes :{\begin{array}{l}a=1,\quad b\approx -0.71806\\\\c\approx -0.14097+i\,0.66659,\quad d=\overline{c}\end{array}}Les valeurs propres {\lambda_2,\lambda_3,\lambda_4} vérifient {\left|\lambda_i\right|\lt 1} (habituel pour une matrice stochastique). Voici le calcul en Python d’une matrice de diagonalisation (l’ordre des valeurs propres reste le même) :
>>> P = np.linalg.eig(A)[1]; P array([[ 0.62554324+0.j , 0.75285378+0.j , 0.65750284+0.j , 0.65750284-0.j ], [ 0.62554324+0.j , -0.54059205+0.j , -0.09268911+0.43828503j , -0.09268911-0.43828503j], [ 0.41702883+0.j , 0.13722474+0.j , -0.49825765-0.12357132j , -0.49825765+0.12357132j], [ 0.20851441+0.j , -0.34948647+0.j , -0.06655608-0.3147137j , -0.06655608+0.3147137j ]])On vérifie que {P} est une matrice de passage vers une réduite diagonale {D} de {A}.
>>> D = np.linalg.inv(P).dot(A).dot(P); np.round(D,5) array([[ 1. -0.j , 0. + 0.j , 0. -0.j , 0. + 0.j ], [ 0. -0.j , -0.71806 + 0.j , -0. -0.j , -0. + 0.j ], [ 0. +0.j , 0. - 0.j , -0.14097 + 0.66659j , 0. +0.j ], [ 0. -0.j , 0. - 0.j , 0. +0.j , -0.14097 - 0.66659j]])Ainsi {A=PDP^{-1}} donc {A^n=PD^nP^{-1}}.
De plus {D^n=\begin{pmatrix}1&0&0&0\\0&b^n&0&0\\0&0&c^n&0\\ 0&0&0&d^n\end{pmatrix}}.
Donc {D^n} tend vers {\Delta=\begin{pmatrix}1&0&0&0\\0&0&0&0\\0&0&0&0\\ 0&0&0&0\end{pmatrix}}.
Posons {B=\displaystyle\lim_{n\to+\infty}A^n=P\Delta P^{-1}}.
On forme {\Delta} et on calcule {B} avec Python :
>>> Delta = np.diag([1,0,0,0]) >>> B = P.dot(Delta).dot(np.linalg.inv(P)) >>> np.real(B) # éliminer les parties imaginaires (nulles de toutes façons) array([[0.33333333, 0.33333333, 0.33333333, 0.33333333], [0.33333333, 0.33333333, 0.33333333, 0.33333333], [0.22222222, 0.22222222, 0.22222222, 0.22222222], [0.11111111, 0.11111111, 0.11111111, 0.11111111]])Ainsi {B=\displaystyle\lim_{n\to+\infty}A^n=\Big(\varepsilon_1\mid\varepsilon_1\mid\varepsilon_1\mid\varepsilon_1\Bigr)}.
Pour tout {n\in\mathbb{N}^*}, on a {U_{n}=AU_{n-1}}.
On en déduit l’égalité : {U_n=A^nU_0}.
Ainsi {\displaystyle\lim_{n\to+\infty}U_n=BU_0=B\begin{pmatrix}1\\0\\0\\0\end{pmatrix}=\dfrac{1}{9}\begin{pmatrix}3\\3\\2\\1\end{pmatrix}}.
Pour justifier de façon théorique les résultats numériques précédents, on peut avancer les explications suivantes :
- La suite {n\mapsto A^n} converge vers {B=P\Delta P^{-1}} qui est rang {1} (comme {\Delta}).
-
On a {\Delta^2=\Delta} donc {B^2=B}.
{B} est une matrice de projection sur une droite. -
On a {A\varepsilon_1=\varepsilon_1}, donc {A^n\varepsilon_1=\varepsilon_1}.
À la limite, on trouve : {B\varepsilon_1=\varepsilon_1}.
Les colonnes de la matrice de projection {B} sont donc colinéaires à {\varepsilon_1}.
Mais {A} est stochastique (suivant les colonnes).
Cela reste vrai pour les {A^n} donc pour {B}.
Les colonnes de {B} sont donc égales à {\varepsilon_1}.
-
La variable {Y_n(i)} mesure le nombre de fois où le jeton se trouve dans la case n°{i}, entre la date {0} et la date {n} (comprises). On pourrait réutiliser notre fonction fréquences, mais on va réécrire une fonction Y plus simple :
def Y(n): listpos = positions(n) y = [0]*4 for k in range(n): y[listpos[k]-1] += 1 return yVoici quelques exemples d’utilisation :
>>> Y(9) # de la date 0 à la date 9 [4, 4, 1, 1] >>> Y(99) # de la date 0 à la date 99 [34, 33, 22, 11] >>> Y(999) # de la date 0 à la date 999 [337, 336, 215, 112]
Expérimentalement, le résultat est donc le suivant :
{\begin{array}{ll}\displaystyle\lim_{n\to+\infty}\dfrac{Y_n(1)}{n}=\dfrac{1}{3},&\displaystyle\lim_{n\to+\infty}\dfrac{Y_n(2)}{n}=\dfrac{1}{3}\\\\\displaystyle\lim_{n\to+\infty}\dfrac{Y_n(3)}{n}=\dfrac{2}{9},&\displaystyle\lim_{n\to+\infty}\dfrac{Y_n(4)}{n}=\dfrac{1}{9}\end{array}}
Exercice 2 — Vidages d’urnes bicolores
| (Oral Centrale) Une urne contient {b} boules blanches et {n-b} rouges. On tire ces {n} boules, une à une, sans remise. Soit {X_{i}} la variable indicatrice d’un changement de couleur entre les tirages i et i+1. Soit {C} le nombre de changements de couleur.
|
-
On écrit \text{changements(n,b)} renvoyant le nombre de changements de couleur.
Pour cela, on modélise la couleur « blanc » par {0}, la couleur « rouge » par {1}.
L’urne initiale est donc une liste de longueur {n}, contenant {b} fois {0} et {n-b} fois {1}.
Cette liste est permutée aléatoirement par la fonction \text{permutation} de \text{numpy.random}.
La liste représente alors la succession des couleurs observées pendant le tirage.
On commence par importer les fonctions Python dont on aura besoin dans l’exercice :
import numpy as np from numpy.random import permutation import matplotlib.pyplot as plt
Voici la fonction \text{changements} :
def changements(n,b): urne = b*[0] + (n-b)*[1] urne = permutation(urne) print(urne) # ligne facultative chg = 0 for i in range(n-1): if urne[i] != urne[i+1]: chg += 1 return chgVoici quelques exemples d’utilisation ({15} boules, dont {6} blanches):
>>> chgts(15,6) [1 1 0 0 1 1 1 0 1 1 1 0 1 0 0] 7 >>> chgts(15,6) [0 1 0 1 1 1 0 0 1 1 1 0 1 1 0] 8 >>> chgts(15,6) [1 1 1 0 0 0 0 0 1 0 1 1 1 1 1] 4
-
-
Bien sûr, pour tout {i\in[[ 1,n-1]]}, la variable {X_i} suit une loi de Bernoulli {\mathcal{B}(p_i)}.
Le piège est de croire que {p_i} dépend de {i} (car un changement de couleur dépendrait de « ce qui s’est passé avant »).
Le mieux est de considérer, temporairement, que les boules sont numérotées de {1} à {n} (les blanches de {1} à {b}, et les rouges de {b+1} à {n}).
Soit {N_i} le numéro de la boule au {n}-ième tirage.
Par symétrie {\mathbb{N}_i\leadsto \mathcal{U}_{[[ 1,n]]}}.
Fixons {i} dans {[[ 1,n-1]]}.
Par symétrie, {(N_i,N_{i+1})} suit une loi uniforme.
Ses valeurs possibles sont les {n(n-1)} couples {(k,l)} avec {k} et {l} distincts dans {[[ 1,n]]}.
Dire que {X_i=1} est réalisé, c’est dire qu’on est dans l’un des deux cas suivants :
— {\begin{cases}1\le N_i\le b\\b+1\le N_{i+1}\le n\end{cases}} ({b(n-b)} possibilités);
— {\begin{cases}b+1\le N_{i}\le n\\1\le N_j\le b\end{cases}} ({b(n-b)} possibilités).
Ainsi {\mathbb{P}(X_i=1)=p=\dfrac{2b(n-b)}{n(n-1)}}.
Donc {X_i\leadsto\mathcal{B}\biggl(\dfrac{2b(n-b)}{n(n-1)}\biggr)}.
- On a {C=\displaystyle\sum_{i=1}^{n-1}X_i}, donc par linéarité : {\begin{array}{rl}\text{E}(C)&=\displaystyle\sum_{i=1}^{n-1}\text{E}(X_i)\\\\&=(n-1)\text{E}(X_1)=\dfrac{2b(n-b)}{n}\end{array}}Il est rassurant que {\text{E}(C)=0} si {b\in\{0,n\}}.
-
La fonction \text{simulesp(n,b,N)} réalise {N} fois l’expérience consistant à vider l’urne de ses {n} boules (dont {b} blanches) et calcule la moyenne des valeurs du nombre {C} de changements observés (ce sera notre estimation de l’espérance {\text{E}(C)}).
def simulesp(n, b, N=1000): return sum([changements(n,b) for _ in range(N)])/NVoici dix approximations de {\text{E}(C)} avec {n=100} et {b=30} (avec {N=1000} tirages complets) :
>>> [simulesp(100, 30) for _ in range(10)] [41.79, 42.123, 41.893, 42.128, 42.116, 41.959, 42.094, 42.019, 41.905, 42.197]
Voici cinq approximations de {\text{E}(C)} avec {n=100} et {b=30} ({N=10000} tirages complets) :
>>> [simulesp(100, 30, N=10000) for _ in range(5)] [41.9655, 41.9847, 41.9439, 41.9494, 42.042]
On réalise enfin la fonction de tracé demandée par l’énoncé. On représente ici le nuage des valeurs approchées de {E(C)} quand {n=26}, et pour les valeurs {b\in[[ 0,26]]}.
Le premier argument est {n} (par défaut {n=26}).
def trace(n=26): x = np.linspace(0,n,n+1) # en abscisses, les valeurs possibles de b y = [simulesp(n,b) for b in x] # les approximations de E(C) plt.clf() # efface préventivement la fenêtre graphique plt.plot(x,y,'o') # trace le nuage des points (x,y) plt.show() # montre le contenu de la fenêtre graphiqueVoici le résultat :

C’est conforme à {\text{E}(C)=\dfrac{2b(n-b)}{n}} (parabole).
-
Bien sûr, pour tout {i\in[[ 1,n-1]]}, la variable {X_i} suit une loi de Bernoulli {\mathcal{B}(p_i)}.
-
Puisque {C=\displaystyle\sum_{i=1}^{n-1}X_i}, on a : {\text{V}(C)=\displaystyle\sum_{i=1}^{n-1}\text{V}(X_i)+2\displaystyle\sum_{i\lt j}\text{Cov}(X_i,X_j)\quad(\star)}On a {X_i^2=X_i\leadsto\mathcal{B}(p)}, où {p=\dfrac{2b(n-b)}{n(n-1)}}.
On en déduit {\text{V}(X_i)=p(1-p)}.
Ensuite, pour tous {i,j}, avec {i\lt j}, on a : {\begin{array}{rl}\text{Cov}(X_i,X_j)&=\text{E}(X_iX_{j})-\text{E}(X_i)\text{E}(X_j)\\\\&=\text{E}(X_iX_{j})-p^2\end{array}}Dans la suite de la question, on fixe {i} et {j} dans {[[ 1,n]]}, avec {1\le i\lt j\le n-1}.
Il y a {\dfrac{(n-1)(n-2)}{2}} tels couples {(i,j)}.
La variable {X_iX_j} est une variable de Bernoulli.
Notons {p_{i,j}} son paramètre.
Ainsi {\text{Cov}(X_i,X_j)=p_{i,j}-p^2}.
On distingue les cas {j=i+1} et {j>i+1}.
Si on revient à l’égalité {(\star)}, on peut écrire :
\begin{array}{l}\text{V}(C)=(n\!-\!1)\text{V}(X_1)\!+\!2\displaystyle\sum_{i\lt j}(p_{i,j}\!-\!p^2)\\\\=(n\!-\!1)p(1\!-\!p)\!-\!(n\!-\!1)(n\!-\!2)p^2+2\displaystyle\sum_{i\lt j}p_{i,j}\\\\=-(n\!-\!1)p\bigl((n\!-\!1)p\!-\!1\bigr)\\\\\qquad+2\displaystyle\sum_{i=1}^{n-2}p_{i,i+1}\!+\!2\displaystyle\sum_{i+1\lt j}p_{i,j}\\\\=-\dfrac{2b(n-b)}{n}\Bigl(\dfrac{2b(n-b)}{n}\!-\!1\Bigr)\\\\\qquad+2\displaystyle\sum_{i=1}^{n-2}p_{i,i+1}\!+\!2\displaystyle\sum_{i+1\lt j}p_{i,j}\quad(\star\star)\end{array}On va réutiliser la modélisation de l’expérience utilisée dans la question 2a).
-
Commençons par le cas {j=i+1} (avec {1\le i\le n-2} car on considère les tirages {i,i+1,i+2}).
Avec des notations évidentes, il y a deux configurations « BRB » et « RBR ».
Le nombre de triplets favorables est {b(n-b)(b-1)} dans le premier cas, {b(n-b)(n-b-1)} dans le deuxième.
Il y a {n(n-1)(n-2)} triplets possibles.
On trouve donc :
\begin{array}{l}p_{i,i+1}=\mathbb{P}(X_i=X_{i+1}=1)\\\\\quad=\dfrac{b(n-b)(b-1)+b(n-b)(n-b-1)}{n(n-1)(n-2)}\\\\\quad=\dfrac{b(n-b)}{n(n-1)}\end{array}En particulier les {p_{i,i+1}} sont égaux, pour les {n-2} valeurs de {i\in[[ 1,n-2]]}. -
On étudie ensuite le cas {j>i+1}.
On a {1\le i\le n-3} et {i+2\le j\le n-1} car on étudie les tirages {i,i+1} d’une part et {j,j+1} d’autre part.
Il y a quatre configurations possibles :
« BR…BR », « BR…RB », « RB…BR », « RB…RB ».À chaque fois, le nombre de quadruplets favorables est {b(b-1)(n-b)(n-b-1)}.
Le nombre de quadruplets possibles est :{n(n-1)(n-2)(n-3)}Ainsi, lorsque {i+1\lt j}, on a : {\begin{array}{rl}p_{i,j}&=\mathbb{P}(X_i=X_{j}=1)\\\\&=4\dfrac{b(b-1)(n-b)(n-b-1)}{n(n-1)(n-2)(n-3)}\end{array}}En particulier les {p_{i,j}} sont égaux pour {i+1\lt j\le n-1}.
On revient à {(\star\star)}, et {V(X)} s’écrit :
{\begin{array}{l}-\dfrac{2b(n-b)}{n-1}\Bigl(\dfrac{2b(n-b)}{n-1}-1\Bigr)\\\\\quad+2(n-2)p_{1,2}+(n-2)(n-3)p_{1,3}\\\\=-\dfrac{2b(n-b)}{n-1}\Bigl(\dfrac{2b(n-b)}{n-1}-1\Bigr)\\\\\quad+2(n-2)\dfrac{b(n-b)}{n(n-1)}\\\\\quad+4\dfrac{b(b-1)(n-b)(n-b-1)}{n(n-1)}\\\\=\dfrac{2 b (n-b) \left(2b(n-b)-n\right)}{(n-1) n^2}\end{array}}On a bien sûr {\text{V}(C)=0} quand {b=0} ou {b=n}.
Par ailleurs, le fait que {V(X)} soit inchangé dans la transformation {b\leftarrow n-b} est rassurant!
-
Commençons par le cas {j=i+1} (avec {1\le i\le n-2} car on considère les tirages {i,i+1,i+2}).
-
On peut effectuer une vérification rapide quand {b=1} (une seule boule blanche).
Si la boule blanche apparaît au début ou à la fin, alors {C=1}. La probabilité est {\dfrac{2}{n}}.
Dans tous les autres cas, on a {C=2}.
Donc {Z=C-1} suit la loi {\mathcal{B}\Bigl(1-\dfrac{2}{n}\Bigr)}.
Ainsi : {\text{E}(C)=\text{E}(Z)+1=\dfrac{2(n-1)}{n}}.
Quand {b=1}, on retrouve {\dfrac{2b(n-b)}{n}}.
On trouve enfin: {\text{V}(C)=\text{V}(Z)=\dfrac{2}{n}\Bigl(1-\dfrac{2}{n}\Bigr)=\dfrac{2(n-2)}{n^2}}Là aussi, quand {b=1}, on retrouve bien :{\dfrac{2 b (n-b) \left(2b(n-b)-n\right)}{(n-1) n^2}}
Exercice 3 — Étude d’un temps d’attente
| (Oral Centrale) Soit {(X_{i})_{i\in \mathbb{N}^{\ast}}} des v.a.r indépendantes de loi : {\mathbb{P}(X_{i}=1)=p\;\text{et}\;\mathbb{P}(X_{i}=2)=1\!-\!p}Soit {S_{n}\!=\!\!\displaystyle\sum\limits_{i=1}^{n}X_{i}} et {Y_{k}=\inf \{n\!\ge\!1,S_{n}\geq k\}}
|
Pour chaque issue {\omega}, {(S_n(\omega))_{n\ge1}} est une suite d’entiers, strictement croissante.
On a toujours {S_{n+1}(\omega)=S_n(\omega)+X_{n+1}(\omega)}.
Ainsi {S_{n+1}(\omega)-S_{n}(\omega)\in\{1,2\}}.
Dans ces conditions, {Y_{k}(\omega)} est le premier entier {n} pour lequel {S_{n}(\omega)} est supérieur ou égal à {k}.
-
Puisque {X_i(\Omega)=\{1,2\}}, on a {S_n(\Omega)\subset[[ n,2n]]}.
On a notamment {S_n(\Omega)\subset[k,+\infty[} pour {n\ge k}.
En particulier {\{n\in \mathbb{N}^{\ast},S_{n}\geq k\}} est non vide (il contient {[k,+\infty[}), donc {Y_k} existe.
Par définition on peut même dire que {\dfrac{k}{2}\le Y_k\le k}.
Voici une fonction Python \texttt{Y(k,p)}.
from random import random def Y(k,p): s = n = 0 while s < k: if random() < p: s += 1 else: s += 2 n += 1 return nExemples avec {k=100} et {p\in\Big\{\dfrac{1}{2},\dfrac{1}{10},\dfrac{9}{10}\Big\}} :
>>> [Y(100,1/2) for _ in range(10)] [69, 64, 65, 68, 67, 65, 66, 65, 65, 69] >>> [Y(100,1/10) for _ in range(10)] [51, 52, 53, 51, 54, 52, 54, 54, 53, 53] >>> [Y(100,9/10) for _ in range(10)] [89, 91, 91, 92, 90, 94, 95, 92, 89, 93]
-
La question est ici un peu vague. L’examinateur attend certainement que le candidat lance la fonction \texttt{Y(k,p)} suffisamment longtemps, qu’il fasse la moyenne des résultats obtenus, et qu’il considère cette moyenne comme une valeur approchée de l’espérance de {Y_k} : tout ça est un peu trop qualitatif.
La fonction \texttt{m(k,p,N=1000)} calcule la moyenne de {N} appels à \texttt{Y(k,p)} (défaut {N=100}) :
def m(k,p,N=100): return sum([Y(k,p) for _ in range(N)])/NQuelques essais, où {k=100} et {p\in\Big\{\dfrac{1}{2},\dfrac{1}{10},\dfrac{9}{10}\Big\}}.
>>> [m(100,1/10), m(100,1/2), m(100,9/10)] [53.02, 66.97, 91.23] >>> [m(100,1/10), m(100,1/2), m(100,9/10)] [52.85, 67.11, 91.26] >>> [m(100,1/10), m(100,1/2), m(100,9/10)] [52.94, 66.33, 90.8] >>> [m(100,1/10), m(100,1/2), m(100,9/10)] [53.03, 66.46, 91.11]
Avec {N=1000} les résultats sont plus précis :
>>> [m(100,1/10,N=1000), m(100,1/2,N=1000), m(100,9/10,N=1000)] [52.917, 66.924, 90.979] >>> [m(100,1/10,N=1000), m(100,1/2,N=1000), m(100,9/10,N=1000)] [52.844, 66.885, 91.005] >>> [m(100,1/10,N=1000), m(100,1/2,N=1000), m(100,9/10,N=1000)] [52.911, 66.808, 91.015] >>> [m(100,1/10,N=1000), m(100,1/2,N=1000), m(100,9/10,N=1000)] [52.879, 66.874, 91.204]
Voici le programme qui réalise le tracé demandé, ainsi que le résultat (avec {N=1000}).
Les valeurs de {k} sont en abscisse (de {k=1} à {k=100}) et {m_k} sont en ordonnée.
On voit clairement apparaître une proportionnalité {m_k\approx C_p k}, où {C_p} ne dépend que de {p}.
def tracem(N=100): plt.clf() x = range(100) for p in [0.1, 0.3, 0.5, 0.7, 0.9]: y = [m(k,p,N) for k in x] plt.plot(x,y,label="p={}".format(p)) plt.legend(loc='upper left') plt.show()
-
On va voir deux démonstrations (on garde la meilleure pour la fin).
Pour simplifier les notations, on pose {q=1-p}.
-
Première démonstration :
Pour étudier {Y_k=n}, on regarde ce qui précède dans la chronologie.
Dire que {Y_k=n} c’est dire {\begin{cases}S_n\ge k\\S_{n-1}\lt k\end{cases}}
Il y a pour cela deux possibilités qui s’excluent:
— ou bien {S_{n}=k} (et alors peu importe {X_{n-1}})
— ou bien {\begin{cases}S_{n-1}=k-1\\X_{n}=2\end{cases}} et alors {S_{n}=k+1}.
On en déduit l’égalité notée {(E_{k,n})}: {\mathbb{P}(Y_k=n)=\mathbb{P}(S_{n}=k)+q\,\mathbb{P}(S_{n-1}=k-1)}En conditionnant par {X_{n-1}}, on a {(F_{n,k})}: {\begin{array}{rl}\mathbb{P}(S_{n}=k)&=p\,\mathbb{P}(S_{n-1}=k-1)\\[9pts]&\quad+q\,\mathbb{P}(S_{n-1}=k-2)\end{array}}Il suffit alors d’écrire :
\begin{array}{l}\mathbb{P}(Y_k=n)\\\\=\mathbb{P}(S_{n}=k)+q\,\mathbb{P}(S_{n-1}=k\!-\!1)\\\\=p\,\mathbb{P}(S_{n-1}=k\!-\!1)\!+\!q\,\mathbb{P}(S_{n-1}=k\!-\!2)\\[9pts]\quad+q\,\bigl(p\,\mathbb{P}(S_{n-2}=k\!-\!2)\!+\!q\,\mathbb{P}(S_{n-2}=k\!-\!3)\bigr)\\\\=p\bigl(\mathbb{P}(S_{n-1}=k\!-\!1)\!+\!q\,\mathbb{P}(S_{n-2}=k\!-\!2)\bigr)\\[9pts]\quad+q\bigl(\mathbb{P}(S_{n-1}=k\!-\!2)\!+\!q\,\mathbb{P}(S_{n-2}=k\!-\!3)\bigr)\\\\=p\,\mathbb{P}(Y_{k-1}=n\!-\!1)+q\,\mathbb{P}(Y_{k-2}=n\!-\!1)\end{array} -
Deuxième démonstration :
Pour étudier {Y_k=n}, on regarde ce qui s’est passé à la première partie.
C’est une technique appelée First Step Analysis.On effectue donc un conditionnement selon la valeur de {X_1}, et on considère qu’une succession de parties recommence à partir de là.
— Ou bien {X_{1}=1}, et dire que {Y_k=n} c’est affirmer que c’est le cumul des {n-1} étapes suivantes qui permet d’atteindre (ou dépasser) {k-1}: cela équivaut à la réalisation de l’événement {Y_{k-1}=n-1}.
— Ou bien {X_{1}=2}, et dire que {Y_k=n} c’est affirmer que c’est le cumul des {n-1} étapes suivantes qui permet d’atteindre (ou dépasser) {k-2}: cela équivaut à la réalisation de l’événement {Y_{k-2}=n-1}.
On en déduit l’égalité : {\begin{array}{l}\mathbb{P}(Y_k=n)=p\,\mathbb{P}(Y_{k-1}=n-1)\\\\\quad+q\,\mathbb{P}(Y_{k-2}=n-1)\end{array}}
-
Première démonstration :
-
Là aussi, on peut voir deux démonstrations.
- Première démonstration\begin{array}{l}\text{E}(Y_k)=\displaystyle\sum_{n=1}^{+\infty}n\,\mathbb{P}(Y_k=n)\\\\=\displaystyle\sum_{n=1}^{+\infty}n\bigl(p\,\mathbb{P}(Y_{k-1}=n-1)\\[9pts]\qquad+q\,\mathbb{P}(Y_{k-2}=n-1)\bigr)\\\\=p\displaystyle\sum_{n=1}^{+\infty}n\,\mathbb{P}(Y_{k-1}=n-1)\\[9pts]\qquad+q\displaystyle\sum_{n=1}^{+\infty}n\,\mathbb{P}(Y_{k-2}=n-1)\\\\=p\displaystyle\sum_{n=0}^{+\infty}(n+1)\,\mathbb{P}(Y_{k-1}=n)\\[9pts]\qquad+q\displaystyle\sum_{n=0}^{+\infty}(n+1)\mathbb{P}(Y_{k-2}=n)\\\\=p\Bigl(1+\displaystyle\sum_{n=0}^{+\infty}n\,\mathbb{P}(Y_{k-1}=n)\Bigr)\\[9pts]\qquad+q\Bigl(1+\displaystyle\sum_{n=0}^{+\infty}n\,\mathbb{P}(Y_{k-2}=n)\Bigr)\\\\=p\,\text{E}(Y_{k-1})+q\,\text{E}(Y_{k-2})+1\end{array}
-
Deuxième démonstration
On conditionne là encore par la valeur de {X_1}.
Par définition, {Y_k} est le temps d’attente pour que le cumul des {X_i} successifs atteigne {k}.
Si {X_1=1} (probabilité {p}), il reste à attendre qu’un cumul de {X_i} successifs atteigne {k-1}.
L’espérance de ce temps d’attente est {\text{E}(Y_{k-1})}.
Si {X_1=1} (probabilité {p}), il reste à attendre qu’un cumul de {X_i} successifs atteigne {k-2}.
L’espérance de ce temps d’attente est {\text{E}(Y_{k-2})}.
Ainsi {\text{E}(Y_k)=p\,\text{E}(Y_{k-1})+q\,\text{E}(Y_{k-2})+1}
(ici le « {+1} » est le temps consacré à {X_1}!)
-
La suite {k\mapsto E(Y_k)} satisfait à la récurrence : {\forall\, k\ge3,\;u_k=pu_{k-1}+qu_{k-2}+1\quad(\star)}On a {E(Y_1)=1} ({Y_1} est constante égale à {1}).
On a {Y_2(\Omega)=\{1,2\}}, avec {\begin{cases}\mathbb{P}(Y_2=1)=q\\\mathbb{P}(Y_2=2)=p\end{cases}}
Il en résulte {E(Y_2)=q+2p=1+p}.
On constate alors que la convention {E(Y_0)=0} permet de démarrer {(\star)} à {k=2}.
La récurrence homogène {(H)} associée à {(\star)} a pour équation caractéristique :{t^2-pt-q=(t-1)(t+q)=0}La solution générale de {(H)} s’écrit donc :{k\mapsto u_k=\alpha+\beta(-q)^k}On cherche une solution particulière de {(\star)} sous la forme {u_k=\lambda k}.
Ainsi {\lambda k=\lambda k\!-\!\lambda(p\!+\!2q)\!+\!1} donc {\lambda=\dfrac{1}{1+q}}.
La solution générale de {(\star)} est donc : {u_k=\alpha+\beta(-q)^k+\dfrac{k}{1+q}}Or {\begin{cases}\text{E}(Y_0)=0\\\text{E}(Y_1)=1\end{cases}} donc {\begin{cases}\alpha+\beta=0\\\alpha-\beta q=\dfrac{q}{1+q}\end{cases}}
Il en résulte : {\alpha=-\beta=\dfrac{q}{(1+q)^2}}.
Finalement, pour tout {k\in\mathbb{N}^*} : {\text{E}(Y_k)=\dfrac{k}{1+q}+q\dfrac{1-(-q)^k}{(1+q)^2}\stackrel{k\rightarrow\infty}{\sim}\dfrac{k}{1+q}}Avec les notations de l’énoncé : C_p=\dfrac{1}{2-p}.
Cette page contient 9 exercices. La suite est réservée aux abonnés.
- avoir une souscription active sur mathprepa
- et être connecté au site
Pour poursuivre votre exploration, vous pouvez :
- revenir à la page d’accueil
- ou tester la page d’extraits libres


On peut conjecturer que pour 
