HEC, ESSEC 2024Maths appliquées

Dans tout le sujet on considère un espace probabilisé \((\Omega, \mathcal{A}, \mathbb{P})\), 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=\left[\!\left[0, n-1\right]\!\right]\), 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 \(\Omega\), une réunion vaut \(\varnothing\).

Partie I - Nombre aléatoire de triangles

On note \(\mathcal{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 : \[\mathcal{T}= \{t_1, \ldots , t_r \}\]

Étant donné \(t=\{u, v, w\}\), un élément de \(\mathcal{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 \in \left[\kern-0.15em\left[ {1,r} \right]\kern-0.15em\right]\), 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\).

1. Quelle est la valeur de \(r\) en fonction de \(n\) ?

2. 1. Soit \(k \in \left[\!\left[1, r\right]\!\right]\). Posons \(t_k=\{u, v, w\}\) avec \(u<v<w\). Montrer que \(Y_k=T_{u, v} T_{v, w} T_{u, w}\).

   2. En déduire que, pour tout \(k \in \left[\!\left[1, r\right]\!\right]\), \(Y_k\) suit la loi de Bernoulli de paramètre \(p^3\).

   3. Justifier que \(\displaystyle Z_n=\sum_{k=1}^r Y_k\). En déduire que \(\mathbb{E}(Z_n)= \binom n3 p^3\).

• On s’intéresse à la variance de \(Z_n\). Si \(i\) et \(j\) appartiennent à \(\left[\!\left[1, r\right]\!\right]\) et sont différents, on note \(i \equiv j\) lorsque \(t_i\) et \(t_j\) ont exactement deux éléments en commun et \(i \not \equiv j\) dans le cas contraire.

  On note \(\mathcal{E}\) l’ensemble des couples \((i, j)\) tels que \(i \equiv j\), et \(\mathcal{F}\) l’ensemble des couples \((i, j)\) tels que \(i \neq j\) et \(i\not \equiv j\).

  On désigne par \(a_n\) le nombre d’éléments de \(\mathcal{E}\).

3. 1. Montrer que : \[\mathbb{V}(Z_n) =\operatorname{cov} \! \left(\sum_{i=1}^r Y_i, \sum_{j=1}^r Y_j\right)=\sum_{(i, j) \in \left[\kern-0.15em\left[ {1,r} \right]\kern-0.15em\right]^2} \operatorname{cov}(Y_i, Y_j)\]

   2. Montrer que si \((i, j) \in \mathcal{F},\) \(Y_i\) et \(Y_j\) sont indépendantes. En déduire que : \[\mathbb{V}(Z_n) =\sum_{i=1}^r \mathbb{V}(Y_i)+\sum_{(i, j) \in \mathcal{E}} \operatorname{cov} (Y_i,Y_j)\]

   3. En conclure que : \[\mathbb{V}(Z_n) = rp^3 \left( 1-p^3 \right) + \left( \sum_{(i, j) \in \mathcal{E}} \mathbb{E}(Y_iY_j) \right) - a_n p^6\]

• On note \(\Delta_n= \displaystyle \sum_{(i, j) \in \mathcal{E}} \mathbb{E}(Y_iY_j)\).

4. Montrer que si \(i \equiv j\), \(\mathbb{E}(Y_i Y_j)=p^5\) et en déduire que \(\Delta_n=a_n p^5\).

   En conclure que : \(\mathbb{V}(Z_n) = \binom n3\left(p^3-p^6\right)+a_n\left(p^5-p^6\right)\).

5. Calcul de \(a_n\).

   1. Déterminer le nombre de triplets \((\{u, v\}, w, y)\) où \(u, v, w, y\) sont quatre éléments distincts de l’ensemble \(\left[\!\left[0, n-1\right]\!\right]\).

   2. En déduire que \(\displaystyle a_n=\frac{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, \ldots, n-1\), modifie L afin qu’elle devienne la liste des listes d’adjacence du graphe \(G^{\prime}\), dont les sommets sont \(0,1, \ldots, 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

6. 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

7. É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.

8. 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 \(\mathcal{D}\) de \(\mathbb{R}^k\) à valeurs dans \(\mathbb{R}\).

  Si \(k \geqslant 2\), on dit que \(f\) est \(k\)-croissante sur \(\mathcal{D}\) si, pour tout \(\left(x_1, \ldots, x_k\right)\) élément de \(\mathcal{D}\) et \(i \in \left[\!\left[1, k\right]\!\right]\), \(t \mapsto f\left(x_1, \ldots, x_{i-1}, t, x_{i+1}, \ldots, x_k\right)\) est croissante sur son ensemble de définition.

  Si \(k=1\), une fonction 1-croissante sur \(\mathcal{D}\) est simplement une fonction croissante sur \(\mathcal{D}\).

• On définit de même la notion de fonction \(k\)-décroissante.

• On considère \(X_1, \ldots, X_k\) des variables aléatoires finies.

  On admet le résultat suivant (théorème de transfert d’ordre \(k\)) :

  Si \(f\) est une fonction définie sur \(X_1(\Omega) \times \ldots \times X_k(\Omega)\) et \(Y_k=f(X_1, \ldots, X_k)\) alors : \[\mathbb{E}(Y_k) = \sum_{ (x_1,\dots,x_k) \in X_1(\Omega) \times \ldots \times X_k(\Omega)} f(x_1,\dots,x_k) \,\mathbb{P}( [X_1=x_1] \cap \cdots [X_k = x_k])\]

On note \(\left(H_k\right)\) la propriété suivante :

Si \(X_1, \ldots, X_k\) sont des variables aléatoires finies indépendantes, \(f\) et \(g\) deux fonctions définies sur \(X_1(\Omega) \times \ldots \times X_k(\Omega)\) et \(k\)-croissantes sur cet ensemble, et si l’on pose \(Y_k=f(X_1, \ldots , X_k)\) et \(Z_k=g(X_1, \ldots, X_k)\) alors :

9. Dans cette question \(k=1\), on pose \(X=X_1\) une variable aléatoire finie, \(f\) et \(g\) sont deux fonctions croissantes sur \(X(\Omega)\).

   1. Montrer que pour tout \((x, y) \in(X(\Omega))^2, \ (f(x)-f(y))(g(x)-g(y)) \geqslant 0\).

   2. Montrer que pour tout \(y \in X(\Omega)\), \[\mathbb{E}(f(X) \, g(X))+f(y) \, g(y) \geqslant g(y) \,\mathbb{E}(f(X))+f(y) \,\mathbb{E}(g(X))\]

   3. En déduire que \(\left(H_1\right)\) est vraie.

10. On suppose que \(\left(H_k\right)\) est vraie pour un certain \(k\) et on considère \(X_1, \ldots, X_{k+1}\) des variables aléatoires finies indépendantes. \(f\) et \(g\) deux fonctions définies sur \(X_1(\Omega) \times \ldots \times X_{k+1}(\Omega)\) et \((k+1)\)-croissantes.

    On pose \(Y_{k+1}=f(X_1, \ldots, X_{k+1})\) et \(Z_{k+1}=g(X_1, \ldots, X_{k+1})\).

    1. À l’aide des théorèmes de transfert d’ordre \(k+1\) et \(k\), montrer que : \[\mathbb{E}(Y_{k+1} Z_{k+1})=\sum_{x \in X_{k+1}(\Omega)} \mathbb{E}(f(X_1, \ldots, X_k, x)\, g(X_1, \ldots, X_k, x)) \, \mathbb{P}(X_{k+1}=x)\]

    2. Justifier que pour tout \(x \in X_{k+1}(\Omega)\) : \[\mathbb{E}(f\left(X_1, \ldots, X_k, x) \, g(X_1, \ldots, X_k, x) \right) \geqslant \mathbb{E}(f(X_1, \ldots, X_k, x)) \, \mathbb{E}(g(X_1, \ldots, X_k, x))\]

    3. On pose pour tout \(x \in X_{k+1}(\Omega), \ u(x)= \mathbb{E}(f(X_1, \ldots, X_k, x))\) et \(v(x)= \mathbb{E}(g(X_1, \ldots, X_k, x))\). Montrer que \(u\) et \(v\) sont croissantes sur \(X_{k+1}(\Omega)\) et \(\mathbb{E}(Y_{k+1} Z_{k+1}) \geqslant \mathbb{E}(u(X_{k+1}) \, v(X_{k+1}))\).

    4. En conclure que \(\left(H_{k+1}\right)\) est vraie. Conclure.

    5. La propriété \(\left(H_k\right)\) 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 \in \left[\!\left[1, r\right]\!\right]\), on pose \(\displaystyle Z_{n, i}=\sum_{k=1}^i Y_k\). On remarquera que \(Z_{n, r}=Z_n\).

Dans cette partie on établit un encadrement de \(\mathbb{P}(Z_n=0)\).

11. Justifier que \(\displaystyle \bigcap_{0 \leqslant u<v \leqslant n-1}\left[T_{u, v}=0\right] \subset\left[Z_n=0\right]\). En déduire que \(\displaystyle \mathbb{P}(Z_n=0) \geqslant(1-p)^{ \binom n2}>0\).

12. Montrer que pour tout \(i \in \left[\!\left[1, r\right]\!\right], \ \mathbb{P}(Y_i=0)= \mathbb{E}(1-Y_i)\) et \(\displaystyle \mathbb{P}(Z_{n, i}=0)= \mathbb{E}\! \left( \prod_{k=1}^i(1-Y_k) \right)\).

13. 1. On pose \(m= \binom n2\). Justifier brièvement que, pour tout \(k \in \left[\!\left[1, r\right]\!\right]\), \(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 \(\left[\!\left[0, n-1\right]\!\right]\).

       En déduire que, pour tout \(i \in \left[\!\left[2, r\right]\!\right], 1-Y_i\) puis \(\displaystyle \prod_{k=1}^{i-1}\left(1-Y_k\right)\) s’expriment comme des fonctions \(m\)-décroissantes des variables aléatoires \(T_{u, v}\) pour \(u<v\) éléments de \(\left[\!\left[0, n-1\right]\!\right]\).

    2. En conclure que, pour tout \(i \in \left[\!\left[2, r\right]\!\right], \ \mathbb{P}(Z_{n, i}=0) \geqslant \mathbb{P}(Z_{n, i-1}=0) \, \mathbb{P}(Y_i=0)\) puis que : \[\mathbb{P}(Z_n=0) \geqslant \prod_{k=1}^r \mathbb{P}(Y_k=0) \text { puis } \mathbb{P}(Z_n=0) \geqslant\left(1-p^3\right)^{\binom n3}\]

14. Inégalité de Boole. Montrer par récurrence sur \(k \geqslant 2\) que si \(B_1, \ldots, B_k\) sont des événements, on a : \[\mathbb{P}\left(\bigcup_{i=1}^k B_i\right) \leqslant \sum_{i=1}^k \mathbb{P}\left(B_i\right)\]

• Si \(A\) est un événement de probabilité non nulle, on rappelle que la probabilité conditionnelle sachant \(A\) est notée \(\mathbb{P}_A\). On admet qu’elle possède les mêmes propriétés que la probabilité \(\mathbb{P}\). En particulier l’inégalité de Boole est vérifiée par \(\mathbb{P}_A\).

  De plus si \(X\) est une variable finie, on note \(\mathbb{E}_A(X)\) l’espérance de \(X\) pour la probabilité \(\mathbb{P}_A\) ce qui signifie que : \[\mathbb{E}_A(X)=\sum_{x \in X(\Omega)} x \, \mathbb{P}_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 \(\mathbb{P}(B \cap C) \neq 0\) et \(\mathbb{P}(A \cap C) \neq 0\).

    Montrer que \(\mathbb{P}_{B \cap C}(A) \geqslant \mathbb{P}_C(A) \, \mathbb{P}_{A \cap C}(B)\).

• On admet que les probabilités conditionnelles qui interviennent dans la suite sont bien définies.

16. Pour tout \(i \in \left[\!\left[1, r\right]\!\right]\), on pose \(A_i=\left[Y_i=0\right]\).

    On note aussi \(I_i=\{j \in \left[\!\left[1, i-1\right]\!\right] \ / \ j \equiv i\}\) et \(\displaystyle J_i=\{j \in \left[\!\left[1, i-1\right]\!\right] \ / \ j \not \equiv i\}\)

    Soit \(i \geqslant 2\), on définit \(\displaystyle B_i=\bigcap_{j \in I_i} A_j\) et \(\displaystyle C_i=\bigcap_{j \in J_i} A_j\), ainsi on a : \(\displaystyle B_i \cap C_i=\bigcap_{j=1}^{i-1} A_j\).

    1. Justifier que \(A_i\) et \(C_i\) sont indépendants. En déduire que \(\mathbb{P}_{B_i \cap C_i}(\overline{A_i}) \geqslant \mathbb{P}(\overline{A_i}) \, \mathbb{P}_{\overline{A_i} \cap C_i}(B_i)\).

    2. Établir que \(\displaystyle \mathbb{P}_{\overline{A_i} \cap C_i}(B_i) \geqslant 1-\sum_{j \in I_i} \mathbb{P}_{\overline{A_i} \cap C_i}(\overline{A_j})\).

    3. On admet provisoirement que pour \(j \in \left[\kern-0.15em\left[ {1,i-1} \right]\kern-0.15em\right]\) : \[\mathbb{P}_{\overline{A_i} \cap C_i}(\overline{A_j}) \leqslant \mathbb{P}_{\overline{A_i}}(\overline{A_j})\]

       En déduire que : \(\displaystyle \mathbb{P}_{B_i \cap C_i}\left(A_i\right) \leqslant 1-\mathbb{P}(\overline{A_i})\left(1-\sum_{j \in I_i} \mathbb{P}_{\overline{A_i}}(\overline{A_j}) \right)\).

    4. Justifier que pour tout \(x \in \mathbb{R}, \ 1-x \leqslant \exp (-x)\) et en déduire que : \[\mathbb{P}_{B_i \cap C_i}(A_i) \leqslant \exp \! \left(-\mathbb{P}(\overline{A_i})+\sum_{j \in I_i} \mathbb{P}(\overline{A_j} \cap \overline{A_i} ) \right)\]

17. On rappelle que \(\displaystyle \Delta_n=\sum_{(i, j) \in \mathcal{E}} \mathbb{E}(Y_i Y_j)\) où \(\mathcal{E}\) a été défini dans la partie 1 à la suite de la question 2.

    1. Montrer que \(\displaystyle \mathbb{P}(Z_n=0)=\mathbb{P} \! \left(\bigcap_{i=1}^r A_i\right)=\mathbb{P}(A_1) \prod_{i=2}^r \mathbb{P}_{B_i \cap C_i}(A_i)\).

    2. En conclure que : \[\mathbb{P}(Z_n=0) \leqslant \exp \! \left(- \mathbb{E}(Z_n)+\frac{\Delta_n}{2}\right) \quad \text { (inégalité de Janson) }\]

    3. En déduire l’encadrement : \[\left(1-p^3\right)^{\binom n3} \leqslant \mathbb{P}(Z_n=0) \leqslant \exp \! \left(- \binom n3 p^3+\frac{a_n}{2} p^5\right)\]

18. Soit \(c\) un réel strictement positif.

    1. Montrer que \(\displaystyle \lim _{n \rightarrow+\infty}- \binom n3\left(\frac{c}{n}\right)^3+\frac{a_n}{2}\left(\frac{c}{n}\right)^5=-\frac{c^3}{6}\).

    2. Établir que \(\displaystyle \lim _{n \rightarrow+\infty} \binom n3 \ln \! \left(1-\frac{c^3}{n^3}\right)=-\frac{c^3}{6}\).

    3. On suppose que \(n>c\) et \(p=\frac{c}{n}\). En déduire la limite de \(\mathbb{P}(Z_n=0)\) quand \(n \rightarrow+\infty\).

19. 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, \(\mathrm{e}^{-x}\) est proche de \(\displaystyle 1-x+\frac{x^2}{2}\) ?

20. Démonstration de (1) - Soit \(m\) un entier plus grand que 2. On considère \(X_1, \ldots, X_m\) des variables de Bernoulli indépendantes et \(I\) un sous ensemble de \(\left[\!\left[1, m\right]\!\right]\). On note \(J\) le complémentaire de \(I\) dans \(\left[\!\left[1, m\right]\!\right]\). On note \(A\) l’événement \(\displaystyle \left[\prod_{i \in I} X_i=1\right]\).

    1. Montrer que, pour tout \(\left(x_1, \ldots, x_m\right) \in\{0,1\}^m\), \[\mathbb{P}_A(\left[X_1=x_1\right] \cap \ldots \cap\left[X_m=x_m\right])= \begin{cases}\displaystyle \prod_{i \in J} \mathbb{P}(X_i=x_i) & \text { si } \displaystyle \prod_{i \in I} x_i=1 \\ \hfill 0 \hfill & \text { sinon } \end{cases}\]

    2. En déduire que les variables aléatoires \(X_1, \ldots, X_m\) sont indépendantes pour la probabilité conditionnelle \(\mathbb{P}_A\).

       \(\blacktriangleright\) Soit \(i \geqslant 2\), on reprend les notations de la question 16.

    3. Montrer que pour \(\displaystyle j \in \left[\!\left[1, i-1\right]\!\right], \ \mathbb{P}_{\overline{A_i} \cap C_i}\left(\overline{A_j}\right)=\frac{\mathbb{E}_{\overline{A_i}}\left(Y_j \prod\limits_{k \in J_i}\left(1-Y_k\right)\right)}{\mathbb{P}_{\overline{A_i}}\left(C_i\right)}\).

    4. En utilisant l’inégalité de Harris, montrer que pour \(j \in \left[\!\left[1, i-1\right]\!\right]\) : \[\mathbb{P}_{\overline{A_i }\cap C_i}(\overline{A_j}) \leqslant \mathbb{P}_{\overline{A_i}}(\overline{A_j})\]