Rozkład i wariancja liczby trójkątów na losowym wykresie

Rozważmy losowy wykres Erdosa-Renyi . Zbiór wierzchołków jest oznaczony . Zbiór krawędzi jest konstruowany losowo.$G=(V(n),E(p))$$n$$V$$V = \{1,2,\ldots,n\}$$E$

Niech będzie prawdopodobieństwem , wtedy każda nieuporządkowana para wierzchołków ( ) występuje jako krawędź w z prawdopodobieństwem , niezależnie od innych par.$p$$0<p<1$$\{i,j\}$$i \neq j$$E$$p$

Trójkąt w to nieuporządkowany potrójny różnych wierzchołków, taki że , i są krawędziami .$G$$\{i,j,k\}$$\{i,j\}$$\{j,k\}$$\{k,i\}$$G$

Maksymalna liczba możliwych trójkątów to $\binom{n}{3}$ . Określić zmienną losową $X$ być obserwowana liczba trójkątów na wykresie $G$ .

Prawdopodobieństwo obecności trzech łączy jednocześnie wynosi $p^3$ . Dlatego oczekiwaną wartość $X$ podaje $E(X) = \binom{n}{3} p^3$ . Naiwnie można się domyślać, że wariancję podaje $E(X^2) =\binom{n}{3} p^3 (1-p^3)$ , ale tak nie jest.

Poniższy kod Mathematica symuluje problem:

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]

Jaka jest wariancja $X$ ?

Niech iff utworzy trójkąt. Następnie i każdy . Właśnie tego użyłeś do obliczenia oczekiwanej wartości.$Y_{ijk}=1$$\{i, j, k\}$$X=\sum_{i, j, k}Y_{ijk}$$Y_{ijk}\sim Bernoulli(p^3)$

W przypadku wariancji problem polega na tym, że nie są niezależne. Rzeczywiście, napisz Musimy obliczyć , czyli prawdopodobieństwo, że oba trójkąty są obecne. Istnieje kilka przypadków:$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'}]$

• Jeśli (te same 3 wierzchołki), to . W podwójnej sumie będzie takich warunków.$\{i,j,k\}=\{i',j',k'\}$$E[Y_{ijk}Y_{i'j'k'}]=p^3$$\binom{n}{3}$
• Jeśli zestawy i mają dokładnie 2 wspólne elementy, to potrzebujemy 5 krawędzi, aby uzyskać dwa trójkąty, tak aby . w sumie będzie takich warunków.$\{i,j,k\}$$\{i',j',k'\}$$E[Y_{ijk}Y_{i'j'k'}]=p^5$$12 \binom{n}{4}$
• Jeśli zestawy i mają wspólny 1 element, to potrzebujemy 6 krawędzi, aby . W będzie takich warunków.$\{i,j,k\}$$\{i',j',k'\}$$E[Y_{ijk}Y_{i'j'k'}]=p^6$$30 \binom{n}{5}$
• Jeśli zestawy i mają wspólny element 0, to potrzebujemy 6 krawędzi, aby . W będzie takich warunków.$\{i,j,k\}$$\{i',j',k'\}$$E[Y_{ijk}Y_{i'j'k'}]=p^6$$20 \binom{n}{6}$

Aby zweryfikować, że uwzględniliśmy wszystkie sprawy, zauważ, że suma sumuje się do .$\binom{n}{3}^{2}$

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

Pamiętanie o odjęciu kwadratu oczekiwanej średniej, zebranie tego razem daje:

$$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$$

Korzystając z tych samych wartości liczbowych co w przykładzie, poniższy kod R oblicza odchylenie standardowe, które jest dość zbliżone do wartości 262 z twojej symulacji.

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

Poniższy kod Mathematica oblicza również odchylenie standardowe, co daje ten sam wynik.

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

Podaję nieco inne podejście do wyprowadzania .$\mathrm{X}^{2}$

Z takim samym rozróżnieniem skrzynek jak Robin Ryder:

• Jeśli tj. 3 wierzchołki są takie same, więc musimy wybrać 3 wierzchołki spośród n możliwych . Musimy mieć 3 krawędzie obecne . Połączone:$\{i, j, k\} = \{i', j', k'\}$$\Rightarrow \binom{n}{3}$$\Rightarrow \mathrm{p}^{3}$$\binom{n}{3}\mathrm{p}^{3}$

• Jeśli i mają dwa wspólne wierzchołki, oznacza to, że dla którego i odwrotnie (każdy trójkąt ma jeden wierzchołek, który nie jest częścią drugiego trójkąta). Wlog wyobraża sobie, że oraz są wspomnianymi wierzchołkami rozłącznymi i = , = . Aby osiągnąć = , = , musimy wybrać te same dwa wierzchołki spośród n możliwych . Dla$\{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'$musimy wybrać jeszcze dwa z pozostałych wierzchołków. Pierwszy: i drugi: . Ponieważ krawędzie i są takie same, musimy mieć 5 krawędzi . Łącznie:$(n-2)$$(n-3)$$\{i, j\}$$\{i', j'\}$$\Rightarrow \mathrm{p}^{5}$$\binom{n}{2}(n-2)(n-3)\mathrm{p}^{5}$

• Jeśli i mają tylko jeden wspólny wierzchołek, wówczas 4 są rozłączne. Wyobraź sobie, wlog, że = . Oznacza to, że spośród n możliwych wierzchołków musimy wybrać 1 . Dla trójkąta wybieramy 2 wierzchołki z pozostałych . W przypadku trójkąta wybieramy 2 z pozostałych , wynika to z założenia, że i . Ponieważ mamy tylko jeden wspólny wierzchołek, musimy mieć 6 krawędzi$\{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}$ . Łącznie:$n\binom{n-1}{2}\binom{n-3}{2}\mathrm{p}^{6}$

• W ostatnim przypadku: jeśli i nie mają wspólnego wierzchołka, wówczas dwa trójkąty są rozłączne. Wybieramy pierwszy trójkąt, 3 wierzchołki z n możliwych . I drugiego trójkąta, 3 wierzchołki z pozostały . Trójkąty są rozłączne, tzn. Nie mają żadnych krawędzi i wierzchołków, dlatego musi być obecnych 6 krawędzi . Połączone:$\{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}$

Podobnie jak w podejściu Robina Rydera, możemy również zweryfikować, czy:

$\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}$ trzyma.

To prowadzi do:

$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}.$