2
$\begingroup$

I'm trying to solve part (b) of Problem 3 here. The background of the problem is as follows: $G$ is a (simple, undirected) random graph with $n>3$ vertices, where each edge is independently included with probability $p$. $E(x,y)$ where $x,y$ are vertices means that the two are joined by an edge. $P(x,y)$ means that there is a length-2 path between them. The question is whether the events $$P(w,x) $$ and $$P(x,y) $$ are independent.

Using the principle of inclusion-exclusion carefully, I have obtained the probabilities $$\text{Pr}[P(w,x)]=1-(1-p^2)^{n-2}=\text{Pr}[P(x,y)], $$ and $$\text{Pr}[P(w,x) \cap P(x,y)]=\sum_{d=1}^{(n-2)^2} (-1)^{d+1} \sum_{k=0}^d \binom{n-3}{k} \binom{(n-2)^2-(n-3)}{d-k}(p^3)^k (p^4)^{d-k}. $$ By comparing the degrees with respect to $p$, we have that $$\deg_p \left[ \text{Pr}[P(w,x) \cap P(x,y)] \right]=4(n-2)^2 \neq4(n-2)=\deg_p \left[\text{Pr}[P(w,x)] \right] \deg_p \left[\text{Pr}[P(x,y)] \right] .$$ It follows that the polynomial $$ \text{Pr}[P(w,x) \cap P(x,y)]-\text{Pr}[P(w,x)] \text{Pr}[P(x,y)]$$ has at most $4(n-2)^2$ roots. This means that the events are not independent, with possibly a finite number of exceptional values of $p$. I'm not satisfied with my proof for several reasons:

  1. I find the reasoning extremely difficult, especially for a first year introductory course.
  2. I'm looking for a proof of non-independence which works for all values of $p$.

Hopefully, I haven't made any errors above. If you know of a more elegant way of proving the events are not independent, please share it. Thank you!

$\endgroup$
  • $\begingroup$ typo alert: you mean where each edge is independently included with probability $p$. $\endgroup$ – antkam May 1 '18 at 13:25
  • $\begingroup$ @antkam Thank you. Corrected! $\endgroup$ – user1337 May 1 '18 at 13:46
  • $\begingroup$ I'd think the reason they are dependent, is that $P(x,y) \Rightarrow \exists v: E(x,v) \cap E(v,y) \Rightarrow \exists v: E(x,v)$. I.e. $x$ has at least one edge, and based on that alone, $Pr[P(x,w)|P(x,y)]$ is now a bigger value. I can argue this informally but I'm not sure I can prove it 100% rigorously. $\endgroup$ – antkam May 1 '18 at 13:58
  • $\begingroup$ The events are certainly independent when $p=0$ and when $p=1$, so you can't hope for a proof that's entirely independent of the value of $p$. $\endgroup$ – Misha Lavrov May 1 '18 at 21:07
2
$\begingroup$

The easiest thing to do is to prove that when $p \ne 0,1$, $$ \Pr[\neg P(w,x) \land \neg P(x,y)] > \Pr[\neg P(w,x)] \cdot \Pr[\neg P(x,y)], $$ because both of these are easy to compute. The right-hand side, as you've found, is $(1-p^2)^{2(n-2)} = (1-2p^2 + p^4)^{n-2}$.

For the left-hand side, we divide the relevant edges into the following $n-2$ triples:

  • $wx$, $xy$, and $wy$.
  • $wz$, $yz$, and $xz$, for each vertex $z$ other than $w,x,y$.

In each triple, we obtain a path we don't want if the third edge is present along with one of the first two. Different triples don't interact. So we have $$ \Pr[\neg P(w,x) \land \neg P(x,y)] = (1 - p(1-(1-p)^2))^{n-2} = (1-2p^2+p^3)^{n-2}. $$ Since $1-2p^2+p^3 > 1-2p^2+p^4$, we have $(1-2p^2+p^3)^{n-2} > (1-2p^2+p^4)^{n-2}$, giving us the inequality we want.


So that wasn't too bad. Next, I want to reassure you that nobody does this.

In practice, we hardly ever care to prove that two events are not independent. If two events are independent, that makes many things simpler, so it requires proof. But nothing special happens only when events are not independent; if we're wrong in that direction, we'll just make use of more complicated machinery that we didn't need to use.

Much more important is the intuition that these events are not independent. Intuitively, both $P(w,x)$ and $P(x,y)$ are correlated with the existence of many edges out of $x$, so they shouldn't be independent. Being able to make this guess accurately is a useful skill to have.

(Actually, we might be more sloppy still, and say: these events involve some of the same edges, so they're not obviously independent, and we might as well treat them as dependent to be safe.)

$\endgroup$
  • $\begingroup$ Love your comment re: "nobody does this." I'm guessing the professor agrees, since he/she set this problem as a tiny true/false question within a sub part of a question. (see link in OP) :) $\endgroup$ – antkam May 2 '18 at 11:39
  • $\begingroup$ Originally I was trying to "prove" the dependence exactly by correlating with a 3rd event (e.g. $x$ has at least 1 edge). However, it is not always true that if event $E_1$ correlates with $E_3$, and $E_2$ correlates with $E_3$, then $E_1$ and $E_2$ are correlated. This is not always true even if you specify positive correlations. Something a little more "causal" is going on here, that I cant quite abstractly quantify. $\endgroup$ – antkam May 2 '18 at 11:42
  • $\begingroup$ That can be made to work if the correlation is not just positive but sufficiently high (though I'm not sure how to get that here). Correlations are like angles. If the angle between lines $\ell_1, \ell_2$ and between lines $\ell_2, \ell_3$ is acute, then the angle between $\ell_1,\ell_3$ is not always acute. But this holds if we replace the first two "acutes" with "less than $45^\circ$". $\endgroup$ – Misha Lavrov May 2 '18 at 13:50

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.