Distribution et variance du nombre de triangles dans le graphique aléatoire

Considérons un graphe aléatoire Erdos-Renyi . L'ensemble des sommets est étiqueté par . L'ensemble des arêtes est construit par un processus aléatoire.$G=(V(n),E(p))$$n$$V$$V = \{1,2,\ldots,n\}$$E$

Soit une probabilité , puis chaque paire non ordonnée de sommets ( ) se présente comme une arête dans de probabilité , indépendamment des autres paires.$p$$0<p<1$$\{i,j\}$$i \neq j$$E$$p$

Un triangle en est un triple non ordonné de sommets distincts, tels que , et \ {k, i \} sont des arêtes dans G .$G$$\{i,j,k\}$$\{i,j\}$$\{j,k\}$$\{k,i\}$$G$

Le nombre maximum de triangles possibles est $\binom{n}{3}$ . Définir la variable aléatoire $X$ comme le nombre observé de triangles dans le graphe $G$ .

La probabilité que trois liens soient simultanément présents est $p^3$ . Par conséquent, la valeur attendue de $X$ est donnée par $E(X) = \binom{n}{3} p^3$ . Naïvement, on peut deviner que la variance est donnée par $E(X^2) =\binom{n}{3} p^3 (1-p^3)$ , mais ce n'est pas le cas.

Le code Mathematica suivant simule le problème:

n=50;
p=0.6;
t=100;
myCounts=Table[Length[FindCycle[RandomGraph[BernoulliGraphDistribution[n,p]],3,All]],{tt,1,t}];
N[Mean[myCounts]] // 4216. > similar to expected mean
Binomial[n,3]p^3 // 4233.6
N[StandardDeviation[myCounts]] // 262.078 > not similar to "expected" std
Sqrt[Binomial[n,3](p^3)(1-p^3)] // 57.612
Histogram[myCounts]

Quelle est la variance de $X$ ?

Soit ssi forment un triangle. Alors et chaque . C'est ce que vous avez utilisé pour calculer la valeur attendue.$Y_{ijk}=1$$\{i, j, k\}$$X=\sum_{i, j, k}Y_{ijk}$$Y_{ijk}\sim Bernoulli(p^3)$

Pour la variance, le problème est que les ne sont pas indépendants. En effet, écrivez Nous devons calculer , qui est la probabilité que les deux triangles soient présents. Il existe plusieurs cas:$Y_{ijk}$

$$X^2=\sum_{i, j, k}\sum_{i', j', k'}Y_{ijk}Y_{i'j'k'}.$$ $E[Y_{ijk}Y_{i'j'k'}]$

• Si (mêmes 3 sommets) alors . Il y aura ces termes dans la double somme.$\{i,j,k\}=\{i',j',k'\}$$E[Y_{ijk}Y_{i'j'k'}]=p^3$$\binom{n}{3}$
• Si les ensembles et ont exactement 2 éléments en commun, alors nous avons besoin de 5 arêtes présentes pour obtenir les deux triangles, de sorte que . il y aura termes dans la somme.$\{i,j,k\}$$\{i',j',k'\}$$E[Y_{ijk}Y_{i'j'k'}]=p^5$$12 \binom{n}{4}$
• Si les ensembles et ont 1 élément en commun, alors nous avons besoin de 6 arêtes présentes, de sorte que . La somme contiendra termes.$\{i,j,k\}$$\{i',j',k'\}$$E[Y_{ijk}Y_{i'j'k'}]=p^6$$30 \binom{n}{5}$
• Si les ensembles et ont 0 élément en commun, alors nous avons besoin de 6 arêtes présentes, de sorte que . La somme contiendra termes.$\{i,j,k\}$$\{i',j',k'\}$$E[Y_{ijk}Y_{i'j'k'}]=p^6$$20 \binom{n}{6}$

Pour vérifier que nous avons couvert tous les cas, notez que la somme s'additionne à .$\binom{n}{3}^{2}$

$$\binom{n}{3} + 12 \binom{n}{4} + 30 \binom{n}{5} + 20 \binom{n}{6} = \binom{n}{3}^{2}$$

N'oubliez pas de soustraire le carré de la moyenne attendue, tout cela donne:

$$E[X^2] - E[X]^2 = \binom{n}{3} p^3 + 12 \binom{n}{4} p^5 + 30 \binom{n}{5} p^6 + 20 \binom{n}{6} p^6 - \binom{n}{3}^2 p^6$$

En utilisant les mêmes valeurs numériques que votre exemple, le code R suivant calcule l'écart type, qui est raisonnablement proche de la valeur 262 de votre simulation.

n=50
p=0.6
sqrt(choose(n, 3)*p^3+choose(n, 2)*(n-2)*(n-3)*p^5+(choose(n, 3)*choose(n-3, 3)+n*choose(n-1, 2)*choose(n-3, 2))*p^6-4233.6^2)
298.7945

Le code Mathematica suivant calcule également l'écart type, ce qui donne le même résultat.

mySTD[n_,p_]:=Sqrt[Binomial[n,3]p^3+12Binomial[n,4]p^5+30 Binomial[n,5]p^6+20Binomial[n,6]p^6-(Binomial[n,3]p^3)^2]
mySTD[50,0.6] // gives 298.795

Je propose une approche légèrement différente de la dérivation de .$\mathrm{X}^{2}$

Avec la même distinction de cas que Robin Ryder:

• Si c'est-à-dire que les 3 sommets sont les mêmes, nous devons donc choisir 3 sommets parmi n possibles . Nous devons avoir 3 arêtes présentes . Combiné:$\{i, j, k\} = \{i', j', k'\}$$\Rightarrow \binom{n}{3}$$\Rightarrow \mathrm{p}^{3}$$\binom{n}{3}\mathrm{p}^{3}$

• Si et ont deux sommets en commun, cela signifie que pour lesquels et vice versa (chaque triangle a un sommet qui ne fait pas partie de l'autre triangle). Wlog imagine que et sont les sommets disjoints mentionnés et = , = . Pour obtenir = , = , nous devons choisir les deux mêmes sommets parmi n possibles . Pour$\{i, j, k\}$$\{i', j', k'\}$$\exists v \in \{i, j, k\}$$v \notin \{i', j', k'\}$$v = k$$v' = k'$$i$$i'$$j$$j'$$i$$i'$$j$$j'$$\Rightarrow \binom{n}{2}$$k \neq k'$nous devons en choisir deux autres parmi les sommets qui restent. Premier: et deuxième: . Comme l'arête et est la même, nous devons avoir 5 arêtes présentes . Combiné:$(n-2)$$(n-3)$$\{i, j\}$$\{i', j'\}$$\Rightarrow \mathrm{p}^{5}$$\binom{n}{2}(n-2)(n-3)\mathrm{p}^{5}$

• Si et n'ont qu'un seul sommet en commun, alors 4 sont disjoints. Imaginez, wlog, que = . Cela signifie que, sur n sommets possibles, nous devons choisir 1 . Pour le triangle nous choisissons 2 sommets parmi les restants . Pour le triangle nous choisissons 2 des restants , ceci est dû à l'hypothèse que et . Parce que nous n'avons qu'un seul sommet en commun, nous devons avoir 6 arêtes présentes$\{i, j, k\}$$\{i', j', k'\}$$i$$i'$$\Rightarrow n$$\{i, j, k\}$$(n-1) \Rightarrow \binom{n-1}{2}$$\{i', j', k'\}$$(n-3) \Rightarrow \binom{n-3}{2}$$j'\notin\{i, j, k\}$$k'\notin\{i, j, k\}$$\Rightarrow \mathrm{p}^{6}$ . Combiné:$n\binom{n-1}{2}\binom{n-3}{2}\mathrm{p}^{6}$

• Pour le dernier cas: Si et n'ont pas de sommet en commun, alors les 2 triangles sont disjoints. Nous choisissons le premier triangle, 3 sommets sur n possibles . Et le deuxième triangle, 3 sommets sur restants . Les triangles sont disjoints, c'est-à-dire qu'ils ne partagent ni arêtes ni sommets, donc 6 arêtes doivent être présentes . Combiné:$\{i, j, k\}$$\{i', j', k'\}$$\Rightarrow \binom{n}{3}$$(n-3)$$\Rightarrow \binom{n-3}{3}$$\Rightarrow \mathrm{p}^{6}$$\binom{n}{3}\binom{n-3}{3}\mathrm{p}^{6}$

Comme dans l'approche de Robin Ryder, nous pouvons également vérifier que:

$\binom{n}{3} + \binom{n}{2}(n-2)(n-3) + n\binom{n-1}{2}\binom{n-3}{2} + \binom{n}{3}\binom{n-3}{3} = \mathrm{\binom{n}{3}}^{2}$ détient.

Cela mène à:

$Var[X] = E[\mathrm{X}^{2}] - \mathrm{E[X]}^{2} = \binom{n}{3}\mathrm{p}^{3} + \binom{n}{2}(n-2)(n-3)\mathrm{p}^{5} + n\binom{n-1}{2}\binom{n-3}{2}\mathrm{p}^{6} + \binom{n}{3}\binom{n-3}{3}\mathrm{p}^{6} - \mathrm{\binom{n}{3}}^{2}\mathrm{p}^{6}.$