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:
- I find the reasoning extremely difficult, especially for a first year introductory course.
- 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!
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:
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.)