Erdős – Rényi modeli ile ilgili problem

Question

Birkaç hafta önce rastgele değer $X$ Varyans - Değişken ($X$) ve Beklenti - $\mathbb{E}X$olasılık dersimiz açısından tanıtıldı. Bir hafta önce düşünmemiz gereken sorunlar verildi, bunlardan biri şudur: verilen bir grafik için$G(n, p)$ tam bir grafikte rastgele ve bağımsız olarak kenarların kaldırılmasıyla oluşturulur. $n$ köşeler, her kenara olasılıkla dokunulmadan bırakılır $p$. İzin Vermek$T_n$ 'üçgen' sayısını karakterize eden rastgele bir değer olmak $G(n, p)$. Görev bulmaktır$\mathbb{E}T_n$ ve Var (T_n).

Bunun Erdős – Rényi modeliyle ilgili olduğunu buldum, ancak bunu 3 gün üst üste çözemedim. Hiç fikrin var mı? Özellikle Var ($X$)

Answer 1

İpuçları:

Beklentilerin doğrusallığını kullanın. Var$\ {n\choose3}\ $orijinal tam grafikteki üçgenler. İçin$\ t=1,2,\dots,{n\choose3}\ $ bir gösterge işlevi tanımlayın $$ I_t=\cases{0& if one of the edges of the $\ t ^ \ text {th} \ $triangle gets deleted\\ 1& otherwise}\ . $$ Sonra $\ \displaystyle T_n=\sum_{t=1}^{n\choose3}I_t\ $. Hesaplayabilir misin$\ \mathbb{E}\big(I_t\big)\ $?

Almak $\ \text{Var}\big(T_n\big)\ $, formülü kullan \begin{align} \text{Var}\big(T_n\big)&=\mathbb{E}\big(T_n^2\big)~-\mathbb{E}\big(T_n\big)^2\\ &=\mathbb{E}\left(\sum_{s=1}^{n\choose3}\sum_{t=1}^{n\choose3} I_sI_t\right) -\mathbb{E}\big(T_n\big)^2\\ &=\mathbb{E}\big(T_n\big)+2 \mathbb{E}\left(\sum_{s=1}^{{n\choose3}-1} \sum_{t=s+1}^{n\choose3} I_sI_t\right)- \mathbb{E}\big(T_n\big)^2\ . \end{align} Bu formülü değerlendirmek için hesaplamanız gerekecek $\ \mathbb{E}\big(I_sI_t\big)\ $ için $\ 1\le s<t\le{n\choose3}\ $. Eğer$\ s^\text{th}\ $ ve $\ t^\text{th}\ $ üçgenlerin ortak kenarları yoktur, o zaman $\ I_s\ $ ve $\ I_t\ $ bağımsız, yani $\ \mathbb{E}\big(I_sI_t\big)=$$\ mathbb {E} \ büyük (I_s \ büyük) \ mathbb {E} \ büyük (I_t \ büyük) \ $ . Hesaplamayı tamamlamak için yapmanız gerekenler:

• Hesaplama $ \ \ mathbb {E} \ büyük (I_sI_t \ büyük) \ $ durum için $ \ s ^ \ metni {inci} \ $ ve $ \ t ^ \ metni {inci} \ $ üçgenler tam sahip bir kenar bölgesindeki ortaktır ve orijinal tam grafikte bu tür kaç tane üçgen olduğunu hesaplayın ve
• zaman durum için aynı şeyi $ \ s ^ \ metni {inci} \ $ ve $ \ t ^ \ metni {inci} \ $ üçgenler tam sahip iki ortak noktası kenarları.