Erdős-Rényi-Modellproblem

Question

Vor einigen Wochen zufälliger Wert $X$ Varianz - Var ($X$) und Erwartung - $\mathbb{E}X$wurden in Bezug auf unseren Wahrscheinlichkeitskurs eingeführt. Vor einer Woche hatten wir Probleme, über die wir nachdenken mussten. Eines davon ist das Folgende: für ein bestimmtes Diagramm$G(n, p)$ wird konstruiert, indem zufällige und unabhängige Kanten in einem vollständigen Diagramm mit entfernt werden $n$ Eckpunkte, jede Kante bleibt mit Wahrscheinlichkeit unberührt $p$. Lassen$T_n$ sei ein zufälliger Wert, der die Anzahl der Dreiecke in kennzeichnet $G(n, p)$. Aufgabe ist es zu finden$\mathbb{E}T_n$ und Var (T_n).

Ich habe festgestellt, dass dies mit dem Erdős-Rényi-Modell zusammenhängt, habe es jedoch noch nicht an drei aufeinander folgenden Tagen gelöst. Hast du eine Idee? Besonders interessiert an Var ($X$)

Answer 1

Hinweise:

Verwenden Sie die Linearität der Erwartungen. Es gibt$\ {n\choose3}\ $Dreiecke im ursprünglichen vollständigen Diagramm. Zum$\ t=1,2,\dots,{n\choose3}\ $ Definieren Sie eine Indikatorfunktion $$ I_t=\cases{0& if one of the edges of the $\ t ^ \ text {th} \ $triangle gets deleted\\ 1& otherwise}\ . $$ Dann $\ \displaystyle T_n=\sum_{t=1}^{n\choose3}I_t\ $. Kannst du rechnen$\ \mathbb{E}\big(I_t\big)\ $?

Zu bekommen $\ \text{Var}\big(T_n\big)\ $Verwenden Sie die Formel \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} Um diese Formel auszuwerten, müssen Sie berechnen $\ \mathbb{E}\big(I_sI_t\big)\ $ zum $\ 1\le s<t\le{n\choose3}\ $. Wenn die$\ s^\text{th}\ $ und $\ t^\text{th}\ $ Dreiecke haben also keine gemeinsamen Kanten $\ I_s\ $ und $\ I_t\ $ sind also unabhängig $\ \mathbb{E}\big(I_sI_t\big)=$$\ mathbb {E} \ big (I_s \ big) \ mathbb {E} \ big (I_t \ big) \ $ . Um die Berechnung abzuschließen, müssen Sie:

• Berechnen Sie $ \ \ mathbb {E} \ big (I_sI_t \ big) \ $ für den Fall, dass $ \ s ^ \ text {th} \ $ und $ \ t ^ \ text {th} \ $ Dreiecke genau eine Kante haben gemeinsam und berechnen Sie, wie viele solcher Dreiecke im ursprünglichen vollständigen Diagramm vorhanden waren, und
• Machen Sie dasselbe für den Fall, dass $ \ s ^ \ text {th} \ $ und $ \ t ^ \ text {th} \ $ Dreiecke genau zwei Kanten gemeinsam haben.