Distribusi dan Varians Jumlah Segitiga dalam Grafik Acak

Pertimbangkan grafik acak Erdos-Renyi . Himpunan simpul diberi label oleh . Himpunan tepi dibangun oleh proses acak.n V V = { 1 , 2 , … , n } $G=(V(n),E(p))$$n$$V$$V = \{1,2,\ldots,n\}$$E$

Misalkan adalah probabilitas , maka masing-masing pasangan unordered dari simpul ( ) terjadi sebagai tepi dalam dengan probabilitas , terlepas dari pasangan lainnya.0 < p < 1 { i , j } i ≠ j E $p$$0<p<1$$\{i,j\}$$i \neq j$$E$$p$

Segitiga dalam adalah triple unordered dari simpul yang berbeda, sehingga , , dan adalah tepi .{ i , j , k } { i , j } { j , k } { k , i } $G$$\{i,j,k\}$$\{i,j\}$$\{j,k\}$$\{k,i\}$$G$

Jumlah maksimum dari kemungkinan segitiga adalah $\binom{n}{3}$ . Mendefinisikan variabel random $X$ menjadi hitungan diamati dari segitiga dalam grafik $G$ .

Probabilitas bahwa tiga tautan secara bersamaan hadir adalah $p^3$ . Oleh karena itu, nilai yang diharapkan dari $X$ diberikan oleh $E(X) = \binom{n}{3} p^3$ . Secara naif, orang mungkin menebak bahwa varians diberikan oleh $E(X^2) =\binom{n}{3} p^3 (1-p^3)$ , tetapi ini tidak terjadi.

Kode Mathematica berikut mensimulasikan masalah:

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]

Apa varian $X$ ?

Biarkan iff membentuk segitiga. Kemudian dan masing-masing . Ini yang Anda gunakan untuk menghitung nilai yang diharapkan.$Y_{ijk}=1$$\{i, j, k\}$$X=\sum_{i, j, k}Y_{ijk}$$Y_{ijk}\sim Bernoulli(p^3)$

Untuk varian, masalahnya adalah tidak independen. Memang, tulis Kita perlu menghitung , yang merupakan probabilitas bahwa kedua segitiga hadir. Ada beberapa kasus:$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'}]$

• Jika (3 simpul yang sama) maka . Akan ada istilah seperti itu dalam jumlah ganda.$\{i,j,k\}=\{i',j',k'\}$$E[Y_{ijk}Y_{i'j'k'}]=p^3$$\binom{n}{3}$
• Jika set dan memiliki 2 elemen yang sama, maka kita membutuhkan 5 edge yang ada untuk mendapatkan dua segitiga, sehingga . akan ada istilah tersebut dalam penjumlahan.$\{i,j,k\}$$\{i',j',k'\}$$E[Y_{ijk}Y_{i'j'k'}]=p^5$$12 \binom{n}{4}$
• Jika set dan memiliki 1 elemen yang sama, maka kita membutuhkan 6 sisi, sehingga . Akan ada istilah tersebut dalam penjumlahan.$\{i,j,k\}$$\{i',j',k'\}$$E[Y_{ijk}Y_{i'j'k'}]=p^6$$30 \binom{n}{5}$
• Jika set dan memiliki 0 elemen yang sama, maka kita membutuhkan 6 sisi, sehingga . Akan ada istilah tersebut dalam penjumlahan.$\{i,j,k\}$$\{i',j',k'\}$$E[Y_{ijk}Y_{i'j'k'}]=p^6$$20 \binom{n}{6}$

Untuk memverifikasi bahwa kami telah membahas semua kasus, perhatikan bahwa jumlah ditambahkan ke .$\binom{n}{3}^{2}$

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

Mengingat untuk mengurangi kuadrat dari rata-rata yang diharapkan, menyatukan semua ini memberi:

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

Dengan menggunakan nilai numerik yang sama dengan contoh Anda, kode R berikut menghitung deviasi standar, yang cukup dekat dengan nilai 262 dari simulasi Anda.

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

Kode Mathematica berikut ini juga menghitung deviasi standar, yang memberikan hasil yang sama.

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

Saya memberikan pendekatan yang sedikit berbeda untuk memperoleh .$\mathrm{X}^{2}$

Dengan perbedaan kasus yang sama seperti yang dilakukan Robin Ryder:

• Jika yaitu 3 simpul adalah sama, maka kita harus memilih 3 simpul dari n yang mungkin . Kita harus memiliki 3 sisi sekarang . Gabungan:$\{i, j, k\} = \{i', j', k'\}$$\Rightarrow \binom{n}{3}$$\Rightarrow \mathrm{p}^{3}$$\binom{n}{3}\mathrm{p}^{3}$

• Jika dan memiliki dua simpul yang sama, itu berarti yang dan sebaliknya (setiap segitiga memiliki satu simpul yang bukan bagian dari segitiga lainnya). Wlog bayangkan dan adalah simpul terpisah yang disebutkan dan = , = . Untuk mencapai = , = , kita harus memilih dua simpul yang sama dari n yang mungkin . Untuk$\{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'$kita harus mengambil dua lagi dari simpul yang tersisa. Yang pertama: dan yang kedua: . Karena edge dan adalah sama, kita harus memiliki 5 edge sekarang . Gabungan:$(n-2)$$(n-3)$$\{i, j\}$$\{i', j'\}$$\Rightarrow \mathrm{p}^{5}$$\binom{n}{2}(n-2)(n-3)\mathrm{p}^{5}$

• Jika dan memiliki hanya satu simpul yang sama, maka 4 dipisahkan. Bayangkan, wlog, bahwa = . Itu berarti, dari n simpul yang memungkinkan, kita harus memilih 1 . Untuk segitiga kita memilih 2 simpul dari yang tersisa . Untuk segitiga kita memilih 2 dari yang tersisa , ini disebabkan oleh asumsi bahwa dan . Karena kita hanya memiliki satu simpul yang sama, kita harus memiliki 6 sisi$\{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}$ . Gabungan:$n\binom{n-1}{2}\binom{n-3}{2}\mathrm{p}^{6}$

• Untuk kasus terakhir: Jika dan memiliki tidak ada simpul yang sama, maka 2 segitiga dipisahkan. Kami memilih segitiga pertama, 3 simpul dari n kemungkinan . Dan segitiga kedua, 3 simpul dari tersisa . Segitiga terpisah, yaitu mereka tidak berbagi tepi dan simpul, sehingga 6 tepi harus ada . Gabungan:$\{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}$

Seperti dalam pendekatan Robin Ryder, kami juga dapat memverifikasi bahwa:

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

Ini mengarah ke:

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