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

  • $\begingroup$ The expectations you state are correct, but the distributions from which you derive them aren't. Different vertices being isolated aren't independent events (and neither are different pairs being married); you can ignore this in calculating expectations, because of the linearity of expectation, but not in deriving distributions. $\endgroup$
    – joriki
    Mar 6, 2013 at 8:50

1 Answer 1


$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 :-)


$$ \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} $$


$$ \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?

  • $\begingroup$ Thanks! I understood everything but your last line... could you please explain it? $\endgroup$
    – jreing
    Mar 6, 2013 at 10:01
  • $\begingroup$ @user1685224: The double sum runs over all vertices $i$ and all (unordered) pairs of distinct vertices $j,k$. There are two different cases: either $i$ is equal to either $j$ or $k$, or it isn't. If it isn't, $\{i,j,k\}$ is a set of three distinct vertices, of which there are $\binom n3$, there are $3$ ways to choose $i$ among them, which makes $3\binom n3$, and these all have the same expectation, $E[X_1Y_{23}]$. If it is, $\{i,j,k\}$ is a set of two vertices, of which there are $\binom n2$, there are $2$ ways to choose $i$ among them, and these all have the same expectation, $E[X_1Y_{12}]$. $\endgroup$
    – joriki
    Mar 6, 2013 at 10:08
  • $\begingroup$ okay, I understood your explanation... so It turned out that $ Cov(X,Y)=E[XY]-E[X]E[Y]= $${n(n-1)(n-2) \over 2} (1-p)^{3n-7}p $ - $n(1-p)^{n-1}$$n \choose 2$$p(1-p)^{2n-4}$ - but still pretty far from the real answer... am I still missing something? thanx $\endgroup$
    – jreing
    Mar 6, 2013 at 11:41
  • $\begingroup$ (forgot to mention your username) $\endgroup$
    – jreing
    Mar 7, 2013 at 5:15
  • $\begingroup$ @user1685224: That expression doesn't exactly give the impression that you've tried simplifying it. Also, if you want me to say something about how this relates to the answer you've been given, it would make sense to tell me that answer. You don't need to mention my username here because the owner of a post automatically gets notified of comments under it. $\endgroup$
    – joriki
    Mar 7, 2013 at 7:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.