Suppose that in random graph $G$ on $n$ vertices any $2$ vertices can be connected by an edge with probability $\dfrac{1}{2}$, independently of all other edges. What is the probability $P_n(k)$ that two arbitrary vertices are connected by a simple path of length $k$, $0<k \leq n-1$?
My attempt. Fix $2$ vertices. To build a path of length $k$ we have to choose $k-1$ vertices from the remaining $n-2$ vertices. Since order is important we can do it in $(k-1)! {n-2 \choose k-1}$ ways. There are $2^k$ configurations of the edges for a path of length $k$. Thus the probability seems to be
$$
P_n(k)=\frac{(k-1)! {n-2 \choose k-1}}{2^k}.
$$
The sum over all path lengths, $\displaystyle \sum_{k=1}^{n-1}P_n(k)$, must equal $1$, but my calculations for small $n$ show that it is not $1$.
Where is my mistake?
Best Answer
Your mistake is that you assume that the probability of a union of events is the sum of their probabilities. This is only true if the events are disjoint, which isn't the case here.
Your formula for the probability that there is a path of length $k$ is wrong. Note for example that for $k=2$ your expression for $P_n(k)$ is $\frac{n-2}{2}$, which is larger than 1. Probabilities are always between zero and one.
In fact, your formula is the expected number of paths of length $k$.
When you add the probabilities together, once again you are computing an expectation. What your formula actually computes is the expected number of paths between two vertices.