# Covariance of isolated vertices in a random graph

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 • 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. – joriki Mar 6 '13 at 8:50 ## 1 Answer 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? • Thanks! I understood everything but your last line... could you please explain it? – jreing Mar 6 '13 at 10:01 • @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}]. – joriki Mar 6 '13 at 10:08 • 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 – jreing Mar 6 '13 at 11:41
• (forgot to mention your username) – jreing Mar 7 '13 at 5:15
• @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. – joriki Mar 7 '13 at 7:08