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.
Aucun document n'est autorisé. 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.
Si au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il la signalera sur sa copie et poursuivra sa composition en expliquant les raisons des initiatives qu'il sera amené à prendre.
Dans tout le sujet on considère un espace probabilisé ( Ω, A, ℙ ), toutes les variables aléatoires qui interviennent dans la suite sont définies sur cet espace.
Soit n un entier supérieur ou égal à 3 et p un réel appartenant à ]0, 1[.
Pour génèrer des graphes non orientés de manière aléatoire, on se donne :
S = [ [0, n − 1] ], les sommets du graphe;
pour toute paire de sommets {u, v} avec u < v, T_(u, v) une variable de Bernoulli de paramètre p.
Les variables T_(u, v), pour {u, v} décrivant les paires de sommets avec u < v, sont supposées indépendantes ;
les arêtes d'un graphe G ainsi généré sont les paires {u, v} telles que T_(u, v) = 1 si u < v ou T_(v, u) = 1 si v < u.
Dans tout le problème, par convention, une somme portant sur un ensemble d'indices vide vaut 0 , un produit vaut 1 , une intersection vaut Ω, une réunion vaut ∅.
Partie 1 - Nombre aléatoire de triangles
On note T l'ensemble des parties {u, v, w} à trois éléments de l'ensemble des sommets, r le nombre de ses éléments et on pose
T = {t_1, …, t_r}
Étant donné t = {u, v, w}, un élément de T, on dit que t est un triangle dans un graphe G généré aléatoirement si {u, v}, {v, w} et {w, u} sont des arêtes de G.
Pour tout k ∈ [ [1, r] ], on note Y_k la variable aléatoire de Bernoulli associée à l'événement ≪t_k est un triangle de G≫ et Z_n est la variable aléatoire égale au nombre de triangles de G.
Par exemple si n = 5 et le graphe G est représenté ainsi,
alors Z_5 = 3.
Quelle est la valeur de r en fonction de n ?
a) Soit k ∈ [ [1, r] ]. Posons t_k = {u, v, w} avec u < v < w. Montrer que Y_k = T_(u, v)T_(v, w)T_(u, w).
b) En déduire que, pour tout k ∈ [ [1, r] ], Y_k suit la loi de Bernoulli de paramètre p^3.
c) Justifier que Z_n = ∑_(k = 1)^r Y_k. En déduire que E(Z_n) = (n/3)p^3.
On s'intéresse à la variance de Z_n.
Si i et j appartiennent à [ [1, r] ] et sont différents, on note i ≡ j lorsque t_i et t_j ont exactement deux éléments en commun et i≢j dans le cas contraire.
On note E l'ensemble des couples ( i, j ) tels que i ≡ j, et F l'ensemble des couples ( i, j ) tels que i ≠ j et i≢j.
On désigne par a_n le nombre d'éléments de E.
3. a) Montrer que :
Montrer que si i ≡ j, E(Y_i Y_j) = p^5 et en déduire que Δ_n = a_n p^5.
En conclure que : V(Z_n) = (n/3)(p^3 − p^6) + a_n(p^5 − p^6).
5. Calcul de a_n.
a) Déterminer le nombre de triplets ( {u, v}, w, y ) où u, v, w, y sont quatre éléments distincts de l'ensemble [ [0, n − 1] ].
b) En déduire que a_n = (n(n − 1)(n − 2)(n − 3))/2.
Partie 2 - Étude informatique
On se donne un graphe G généré par le procédé décrit dans le préambule.
On définit la fonction supprimeDer(L) qui si L est la liste des listes d'adjacence du graphe G dont les sommets sont 0, 1, …, n − 1, modifie L afin quelle devienne la liste des listes d'adjacence du graphe G^′, dont les sommets sont 0, 1, …, n − 2, obtenu en supprimant dans G le sommet n − 1 et les arêtes contenant ce sommet.
def supprimeDer(L):
s = len(L)-1
L.pop() # supprime le dernier élément de la liste L
for a in L:
if s in a:
a.remove(s) # supprime s dans la liste a
Compléter la fonction suivante pour qu'elle retourne le nombre de triangles dont un des sommets est le sommet s dans le graphe G dont la liste des listes d'adjacence est L :
def triangle2s(s, L):
cpt = 0
adj = L[s]
for i in range(len(adj)):
for j in range(..., len(adj)):
if ... in L[...]:
cpt += 1
return cpt
Écrire une fonction nbTriangles(L), utilisant les deux fonctions précédentes, qui retourne le nombre de triangles du graphe G dont la liste des listes d'adjacence est représentée par L.
On suppose que la fonction graphe(n,p) génère un graphe aléatoire suivant les hypothèses décrites dans le préambule.
Expliquer ce que retourne la fonction suivante :
def fonctionMystere(n):
cpt = 0
for i in range(1000):
L = graphe(n,1/n)
if nbTriangles(L) == 0:
cpt += 1
return cpt / 1000
Partie 3 - Inégalité de Harris
k désigne un entier naturel non nul.
Soit f une fonction définie sur une partie D de ℝ^k à valeurs dans ℝ.
Si k ⩾ 2, on dit que f est k-croissante sur D si, pour tout (x_1, …, x_k) élément de D et i ∈ [ [1, k] ], t ↦ f(x_1, …, x_(i − 1), t, x_(i + 1), …, x_k) est croissante sur son ensemble de définition.
Si k = 1, une fonction 1 -croissante sur D est simplement une fonction croissante sur D.
On définit de même la notion de fonction k-décroissante.
On considère X_1, …, X_k des variables aléatoires finies.
On admet le résultat suivant (théorème de transfert d'ordre k ):
Si f une fonction définie sur X_1(Ω) × … × X_k(Ω) et Y_k = f(X_1, …, X_k) alors
On note (H_k) la propriété suivante :
Si X_1, …, X_k sont des variables aléatoires finies indépendantes, f et g deux fonctions définies sur X_1(Ω) × … × X_k(Ω) et k-croissantes sur cet ensemble, et si l'on pose Y_k = f(X_1, …, X_k) et Z_k = g(X_1, …, X_k), alors :
E(Y_k Z_k) ⩾ E(Y_k)E(Z_k) (inégalité de Harris)
Dans cette question k = 1, on pose X = X_1 une variable aléatoire finie, f et g sont deux fonctions croissantes sur X(Ω).
a) Montrer que pour tout (x, y) ∈ (X(Ω))^2, (f(x) − f(y))(g(x) − g(y)) ⩾ 0.
b) Montrer que pour tout y ∈ X(Ω),
c) En déduire que ( H_1 ) est vraie.
10. On suppose que ( H_k ) est vraie pour un certain k et on considère X_1, …, X_(k + 1) des variables aléatoires finies indépendantes, f et g deux fonctions définies sur X_1(Ω) × … × X_(k + 1)(Ω) et (k + 1)-croissantes.
On pose Y_(k + 1) = f(X_1, …, X_(k + 1)) et Z_(k + 1) = g(X_1, …, X_(k + 1)).
a) A l'aide des théorèmes de transfert d'ordre k + 1 et k, montrer que:
c) On pose pour tout x ∈ X_(k + 1)(Ω), u(x) = E(f(X_1, …, X_k, x)) et v(x) = E(g(X_1, …, X_k, x)).
Montrer que u et v sont croissantes sur X_(k + 1)(Ω) et E(Y_(k + 1)Z_(k + 1)) ⩾ E(u(X_(k + 1))v(X_(k + 1))).
d) En conclure que ( H_(k + 1) ) est vraie. Conclure.
e) La propriété ( H_k ) reste-t-elle vraie si f et g sont k-décroissantes? Justifier votre réponse.
Que se passe-t-il si l'une est k-croissante et l'autre k-décroissante?
Partie 4 - Inégalité de Janson et application
On reprend les notations de la partie 1 .
De plus, pour tout i ∈ [ [1, r] ], on pose Z_(n, i) = ∑_(k = 1)^i Y_k. On remarquera que Z_(n, r) = Z_n.
Dans cette partie on établit un encadrement de ℙ(Z_n = 0).
11. Justifier que ⋂_(0 ⩽ u < v ⩽ n − 1)[T_(u, v) = 0] ⊂ [Z_n = 0]. En déduire que ℙ(Z_n = 0) ⩾ (1 − p)^((n/2)) > 0.
12. Montrer que pour tout i ∈ [ [1, r] ], ℙ(Y_i = 0) = E(1 − Y_i) et ℙ(Z_(n, i) = 0) = E(∏_(k = 1)^i(1 − Y_k)).
13. a) On pose m = (n/2). Justifier brièvement que, pour tout k ∈ [ [1, r] ], Y_k s'exprime comme une fonction m-croissante sur {0, 1}^m des variables aléatoires T_(u, v) pour u < v éléments de [ [0, n − 1] ].
En déduire que, pour tout i ∈ [ [2, r] ], 1 − Y_i puis ∏_(k = 1)^(i − 1)(1 − Y_k) s'expriment comme des fonctions m-décroissantes des variables aléatoires T_(u, v) pour u < v éléments de [ [0, n − 1] ].
b) En conclure que, pour tout i ∈ [ [2, r] ], ℙ(Z_(n, i) = 0) ⩾ ℙ(Z_(n, i − 1) = 0)ℙ(Y_i = 0) puis que :
Inégalité de Boole. Montrer par récurrence sur k ⩾ 2 que si B_1, …, B_k sont des événements, on a :
ℙ(⋃_(i = 1)^k B_i) ⩽ ∑_(i = 1)^k ℙ(B_i)
Si A est un événement de probabilité non nulle, on rappelle que la probabilité conditionnelle sachant A est notée ℙ_A. On admet qu'elle possède les mêmes propriétés que la probabilité ℙ.
En particulier l'inégalité de Boole est vérifiée par ℙ_A.
De plus si X est une variable finie, on note E_A(X) l'espérance de X pour la probabilité ℙ_A ce qui signifie que :
E_A(X) = ∑_(x ∈ X(Ω))xℙ_A(X = x)
Cette espérance conditionnelle possède les mêmes propriétés que l'espérance en particulier l'inégalité de Harris vue dans la partie 3.
15. Soit A, B et C trois événements tels que ℙ(B ∩ C) ≠ 0 et ℙ(A ∩ C) ≠ 0.
Montrer que ℙ_(B ∩ C)(A) ⩾ ℙ_C(A)ℙ_(A ∩ C)(B).
On admet que les probabilités conditionnelles qui interviennent dans la suite sont bien définies.
Pour tout i ∈ [ [1, r] ], on pose A_i = [Y_i = 0].
On note aussi I_i = {j ∈ [ [1, i − 1] ]/j ≡ i} et J_i = {j ∈ [ [1, i − 1] ]/j≢i}
Soit i ⩾ 2, on définit B_i = ⋂_(j ∈ I_i)A_j et C_i = ⋂_(j ∈ J_i)A_j, ainsi on a : B_i ∩ C_i = ⋂_(j = 1)^(i − 1)A_j.
a) Justifier que A_i et C_i sont indépendants. En déduire que ℙ_(B_i ∩ C_i)(A_i^–) ⩾ ℙ(A_i^–)ℙ_(A_i^– ∩ C_i)(B_i).
b) Établir que ℙ_(A_i^– ∩ C_i)(B_i) ⩾ 1 − ∑_(j ∈ I_i)ℙ_(A_i^– ∩ C_i)(A_j^–).
c) On admet provisoirement que pour j ∈ [ [1, i − 1] ] :
ℙ_(A_i ∩ C_i^–)(A_j^–) ⩽ ℙ_(A_i^–)(A_j^–)
En déduire que, ℙ_(B_i ∩ C_i)(A_i) ⩽ 1 − ℙ(A_i^–)(1 − ∑_(j ∈ I_i)ℙ_(A_i^–)(A_j^–)).
d) Justifier que pour tout x ∈ ℝ, 1 − x ⩽ exp(− x) et en déduire que :
On rappelle que Δ_n = ∑_((i, j) ∈ E)E(Y_i Y_j) où E a été défini dans la partie 1 à la suite de la question 2.
a) Montrer que ℙ(Z_n = 0) = ℙ(⋂_(i = 1)^r A_i) = ℙ(A_1)∏_(i = 2)^r ℙ_(B_i ∩ C_i)(A_i).
b) En conclure que :
Soit c un réel strictement positif.
a) Montrer que lim_(n → + ∞) − (n/3)(c/n)^3 + (a_n)/2(c/n)^5 = − (c^3)/6.
b) Établir que lim_(n → + ∞)(n/3)ln(1 − (c^3)/(n^3)) = − (c^3)/6.
c) On suppose que n > c et p = c/n. En déduire la limite de ℙ(Z_n = 0) quand n → + ∞.
On reprend les notations de la partie 2. L'exécution de l'instruction fonctionMystere (100) affiche dans la console Python 0.849. Est-ce cohérent avec le résultat de la question précédente si on considère que pour x assez petit, e^(− x) est proche de 1 − x + (x^2)/2 ?
Démonstration de (1) - Soit m un entier plus grand que 2. On considère X_1, …, X_m des variables de Bernoulli indépendantes et I un sous ensemble de [ [1, m] ]. On note J le complémentaire de I dans [ [1, m] ]. On note A l'événement [∏_(i ∈ I)X_i = 1].
a) Montrer que, pour tout (x_1, …, x_m) ∈ {0, 1}^m,
b) En déduire que les variables aléatoires X_1, …, X_m sont indépendantes pour la probabilité conditionnelle ℙ_A.
Soit i ⩾ 2, on reprend les notations de la question 16.
c) Montrer que pour j ∈ [ [1, i − 1] ], ℙ_(A_i^– ∩ C_i)(A_j^–) = (E_(A_i^–)(Y_j∏_(k ∈ J_i)(1 − Y_k)))/(ℙ_(A_i^–)(C_i)).
d) En utilisant l'inégalité de Harris, montrer que pour j ∈ [ [1, i − 1] ] :
Même chapitre : Probabilités continues (+4)BCE Maths approfondies HEC/ESCP ECS 2017, épreuve 2BCE · 2017Corrigé
Même année, EcricomeEcricome Maths appliquées ECG 2024Ecricome · 2024Corrigé
Même sessionBCE Maths appliquées EDHEC ECG 2024BCE · 2024Corrigé
Même sessionBCE Maths appliquées emlyon ECG 2024BCE · 2024Corrigé
Même sessionBCE Maths appliquées ESSEC ECG 2024, épreuve 2BCE · 2024Corrigé