隨機圖中三角形計數的分佈和方差

考慮一個Erdos-Renyi隨機圖. 該組頂點被標記為. 邊的集合是由一個隨機過程構建的。

讓成為概率, 然後每個無序對頂點數 () 作為邊緣出現在有概率，獨立於其他對。

一個三角形在是一個無序的三元組不同的頂點，這樣,， 和是邊緣在.

最大可能的三角形數是. 定義隨機變量是圖中三角形的觀察計數.

三個鏈接同時存在的概率是. 因此，期望值為是（誰）給的. 天真地，人們可能會猜測方差由下式給出， 但這種情況並非如此。

下面的Mathematica代碼模擬了這個問題：

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]

什麼是方差?

讓當且當形成一個三角形。然後並且每個. 這是您用來計算期望值的內容。

對於方差，問題在於不是獨立的。確實，寫

我們需要計算，這是兩個三角形都存在的概率。有幾種情況：

• 如果（相同的3個頂點）然後. 將有雙倍總和中的此類條款。
• 如果集和正好有 2 個共同的元素，那麼我們需要 5 個邊來得到這兩個三角形，所以. 將有總和中的此類條款。
• 如果集和有 1 個共同元素，那麼我們需要 6 個邊，所以. 將有總和中的此類條款。
• 如果集和共有 0 個元素，那麼我們需要 6 個邊，所以. 將有總和中的此類條款。

要驗證我們是否涵蓋了所有情況，請注意總和為.

記住要減去預期均值的平方，將它們放在一起給出：

使用與您的示例相同的數值，以下R代碼計算標準偏差，該值相當接近模擬中的 262 值。

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

以下Mathematica代碼還計算標準偏差，得出相同的結果。

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

引用自：https://stats.stackexchange.com/questions/338267