Expression for $\mathbb{E}({X_T}^2)$, where $X_T$ is the number of isolated copies of a fixed tree $T$ on $k$ vertices in $G_{n,p}$.

33 Views Asked by At

I’m reading a proof that contains the following expression for $\mathbb{E}({X_T}^2)$, where $X_T$ is the number of isolated copies of a fixed tree $T$ on $k$ vertices in the random graph $G_{n,p}$, and $\mathscr{T}$ the set of copies of $T$ in $K_n$. I’d like to know how this is derived.

$$\mathbb{E}({X_T}^2) = \underset{T_1,T_2 \in \mathscr{T}}{\sum} \mathbb{P}(T_1 \in G_{n,p} \ \wedge \ T_2 \in G_{n,p})$$

1

There are 1 best solutions below

2
On BEST ANSWER

I think you probably mean $\mathcal{T}$ is the set of copies of $T$ in $K_n$. Then

$X_T = \sum_{S\in\mathcal{T}}\mathbb{1}_S$ where $\mathbb{1}_S$ is an indicator random variable for the event $\{S\in G_{n,p}\}$. So then

$X_T^2 = (\sum_{S\in\mathcal{T}}\mathbb{1}_S)^2 = \sum_{S_1, S_2\in \mathcal{T}}\mathbb{1}_{S_1}\mathbb{1}_{S_2}$.

So applying linearity of expectation gives that $\mathbb{E}(X_T^2) = \sum_{S_1, S_2\in \mathcal{T}}\mathbb{E}(\mathbb{1}_{S_1}\mathbb{1}_{S_2}) = \sum_{S_1, S_2\in \mathcal{T}}\mathbb{P}(S_1\in G_{n,p}\,\, \wedge \,\,S_2\in G_{n,p} )$