Le graphe aléatoire

Exercice de TD · niveau 2 · mathématiques (PCSI), chapitre 15 — Probabilités sur un univers fini · C. Lois, couples, indépendance

Énoncé

Soit $n \geq 3$ . Sur l'ensemble de sommets ${1, \dots, n}$ , chacune des $(2 n)$ arêtes possibles ${i, j}$ est présente avec probabilité $p \in] 0, 1 [$ , indépendamment des autres : on dispose de variables aléatoires $A_{ij}$ ( $1 \leq i < j \leq n$ ) indépendantes, de loi de Bernoulli $B (p)$ , $A_{ij}$ valant $1$ si l'arête ${i, j}$ est présente. On note $D_{i}$ le degré du sommet $i$ , c'est-à-dire le nombre d'arêtes présentes qui le contiennent, et $M$ le nombre total d'arêtes présentes.

a) Donner les lois de $D_{1}$ et de $M$ .

b) Calculer $P (D_{1} = 0, D_{2} = 0)$ . Les variables $D_{1}$ et $D_{2}$ sont-elles indépendantes ?

c) Montrer que $D_{1} - A_{12}$ et $D_{2} - A_{12}$ sont indépendantes. Quel résultat du cours utilise-t-on ?

d) Soit $T$ le nombre de triangles du graphe, c'est-à-dire de parties ${i, j, l}$ à trois sommets deux à deux reliés. Calculer $E (T)$ , puis sa limite quand $p = \frac{c}{n}$ , avec $c > 0$ fixé.

Corrigé

La stratégie. Deux outils voisins qu'il faut distinguer : pour une loi, on reconnaît une somme de variables de Bernoulli indépendantes ; pour une espérance, une somme d'indicatrices suffit, sans aucune indépendance. Entre les deux, le lemme des coalitions dit quelles fonctions de ces variables restent indépendantes : celles qui portent sur des paquets disjoints.

a) Les lois. Écrivons aussi $A_{j i} = A_{ij}$ . Le degré du sommet $1$ est $D_{1} = \sum_{j = 2}^{n} A_{1 j}$ , somme de $n - 1$ variables de Bernoulli de paramètre $p$ , extraites d'une famille indépendante, donc indépendantes. Par le théorème sur les sommes de variables de Bernoulli indépendantes, $D_{1} \sim B (n - 1, p)$ . De même, $M = \sum_{i < j} A_{ij}$ est la somme des $(2 n)$ variables de la famille : $M \sim B ((2 n), p)$ , d'espérance $\frac{n ( n - 1 )}{2} p$ . Un sommet n'est pas relié à lui-même : son degré compte $n - 1$ arêtes possibles, pas $n$ .

b) Une arête commune suffit à lier. L'événement $(D_{1} = 0) \cap (D_{2} = 0)$ signifie que toutes les arêtes issues de $1$ et toutes celles issues de $2$ sont absentes : cela fait $(n - 1) + (n - 1) - 1 = 2 n - 3$ arêtes distinctes, l'arête ${1, 2}$ appartenant aux deux listes. Par indépendance, $P (D_{1} = 0, D_{2} = 0) = (1 - p)^{2 n - 3} .$ Or $P (D_{1} = 0) = P (D_{2} = 0) = (1 - p)^{n - 1}$ , de produit $(1 - p)^{2 n - 2}$ . Comme $0 < 1 - p < 1$ , ces nombres diffèrent : $D_{1}$ et $D_{2}$ ne sont pas indépendantes. Le sens de la dépendance : $P (D_{2} = 0 ∣ D_{1} = 0) = \frac{( 1 - p ) ^{2 n - 3}}{( 1 - p ) ^{n - 1}} = (1 - p)^{n - 2}$ , qui dépasse $P (D_{2} = 0) = (1 - p)^{n - 1}$ — savoir le sommet $1$ isolé apprend que l'arête ${1, 2}$ est absente, ce qui rend l'isolement du sommet $2$ plus probable.

c) Les coalitions. On a $D_{1} - A_{12} = \sum_{j = 3}^{n} A_{1 j}$ et $D_{2} - A_{12} = \sum_{j = 3}^{n} A_{2 j}$ . La première est une fonction des seules variables $A_{13}, \dots, A_{1 n}$ , la seconde des seules $A_{23}, \dots, A_{2 n}$ ; ces deux paquets sont disjoints — une arête ${1, j}$ avec $j \geq 3$ ne contient pas le sommet $2$ — et extraits de la famille indépendante des $A_{ij}$ . Le lemme des coalitions, dont la démonstration est hors programme, affirme que des fonctions de paquets disjoints de variables indépendantes sont indépendantes : $D_{1} - A_{12}$ et $D_{2} - A_{12}$ sont indépendantes, chacune de loi $B (n - 2, p)$ . Toute la dépendance entre $D_{1}$ et $D_{2}$ tient à la seule variable qu'ils partagent, $A_{12}$ .

d) Les triangles. Pour chaque partie ${i, j, l}$ à trois éléments, notons $C_{ij l}$ l'événement « les arêtes ${i, j}$ , ${i, l}$ et ${j, l}$ sont présentes ». Alors $T = {i, j, l} \sum 1_{C_{ij l}},$ la somme portant sur les $(3 n)$ parties à trois éléments (« trois parmi $n$ »). Les trois arêtes d'un triangle sont distinctes, donc, par indépendance, $P (C_{ij l}) = p^{3}$ . Par linéarité de l'espérance et grâce à $E (1_{C}) = P (C)$ : $E (T) = (3 n) p^{3} = \frac{n ( n - 1 ) ( n - 2 )}{6} p^{3} .$ Cette linéarité ne demande aucune indépendance entre les indicatrices — et il n'y en a pas : deux triangles qui partagent une arête sont liés. Avec $p = \frac{c}{n}$ : $E (T) = \frac{n ( n - 1 ) ( n - 2 )}{6} \cdot \frac{c ^{3}}{n ^{3}} = \frac{c ^{3}}{6} (1 - \frac{1}{n}) (1 - \frac{2}{n}) n \to + \infty \frac{c ^{3}}{6} .$

Contrôle exhaustif, $n = 4$ , $p = \frac{1}{3}$ . L'énumération des $2^{6} = 64$ configurations redonne $(\frac{2}{3})^{5} = \frac{32}{243}$ contre $(\frac{2}{3})^{6} = \frac{64}{729}$ , l'indépendance du c) pour toutes les valeurs, et $E (T) = \frac{4}{27}$ .

Le point délicat. L'indépendance intervient à trois endroits, avec trois statuts : indispensable pour la loi de $D_{1}$ — sans elle, une somme de variables de Bernoulli n'est pas binomiale — ; fausse entre $D_{1}$ et $D_{2}$ ; inutile pour $E (T)$ . Confondre ces statuts est l'erreur la plus fréquente du chapitre.

Ce que l'exercice installe. Le graphe aléatoire, terrain que suggère le programme, est le modèle de base des réseaux — contacts d'une épidémie, liaisons dans un matériau désordonné ; on y lit une dépendance sur les variables partagées. Dans le régime $p = \frac{c}{n}$ , le nombre moyen d'arêtes croît comme $\frac{c n}{2}$ tandis que celui des triangles reste borné : les cycles courts y sont rares.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.