Covariance of isolated vertices in a random graph

388 Views Asked by At

Question: Let G(V,E) be a complete graph of size n (5 $\le$ n). We create a random graph by erasing each edge in Pr=(1-p) and keeping it in Pr=p. A vertex is called "isolated" if no edge is reaching it. 2 vertices are called "married" if they have an edge between them, but no other edge reaching each of them. Let X be the number of isolated vertices in a graph, Y be the number of married couples in the graph.

Calculate Cov(X,Y).

What I did: I figured that Y~Bin($n \choose 2$,$p(1-p)^{2n-4}$) calculated $E[Y]=p(1-p)^{2n-4}$$n \choose 2$ and that X~Bin(n,$(1-p)^{n-1}$) and therefore E[X]=$n(1-p)^{n-1}$ don't really get how to calculate E[XY]

Thanx in advance

1

There are 1 best solutions below

6
On

$X=\sum_iX_i$, where $X_i$ is the indicator variable for the $i$-th vertex being isolated. $Y=\sum_{i\lt j}Y_{ij}$, where $Y_{ij}$ is the indicator variable for the vertices $i$ and $j$ being married. (Interesting idea of marriage, by the way, not to have any other edge reaching them :-)

Thus

$$ \begin{align} \def\ex#1{E\left[#1\right]} \ex X &= \ex{\sum_iX_i} \\ &= \sum_i\ex{X_i} \\ &= n\ex{X_1} \\ &=n(1-p)^{n-1} \end{align} $$

and

$$ \begin{align} \ex Y &= \ex{\sum_{i\lt j}Y_{ij}} \\ &= \sum_{i\lt j}\ex{Y_{ij}} \\ &= \binom n2\ex{Y_{12}} \\ &= \binom n2p(1-p)^{2n-4}\;, \end{align} $$

as you'd already found. Likewise

$$ \begin{align} \ex{XY} &= \ex{\sum_iX_i\sum_{j\lt k}Y_{jk}} \\ &= \sum_i\sum_{j\lt k}\ex{X_iY_{jk}} \\ &= 3\binom n3\ex{X_1Y_{23}}+2\binom n2\ex{X_1Y_{12}}\;. \end{align} $$

Can you take it from there?