Probability of a path of a given length between two vertices of a random graph

Question

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?

Answer 1

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.

Answer 2

It's an old question, but I was thinking about the same problem today, and here's a solution for a special case.

Let's say that there are $n+2$ total vertices and the edge-probability is $p$. Edge-probability is the probability that there exists a direct edge between two vertices. Let's say we want to find the probability that ∃ a path of length two between two vertices $x$, and $z$.

This probability equals $1 - (1 - p^2)^n \approx np^2$ when $p$ is small enough.

For example, if there are 100 vertices, and the edges of the graph are in a matching, i.e. the total edges in the graph equals 100, then $p = 100/(100*100)$, and the probability of length 2 path equals $0.009 \approx 0.01$.

Answer 3

Lets try the case k = 2. Pick any two vertices, without loss of generality you can call them 1 and 2. To construct a 2-path between them we first need to choose a third vertex, call it $i$. Clearly there are n-2 choices for $i$. Thus

$$\text{ total number of possible paths from 1 to 2 } = n-2 $$

Now for any $k$, there is an edge from 1 to $k$ with probability $p$. There is an edge from $k$ to $2$ with probability $p$ also. These are independent events, so the probability of both occuring is $p^{2}$. Thus the expected number of 2-paths from $1$ to $2$ is $p^{2}(n-2)$. and so the probability of observing one is:

$$\frac{p^{2}(n-2)}{n-2} = p^{2} $$

I suspect that in general the probability of observing a $k$ path between any two fixed vertices in such an random graph (i.e. an Erdos-Renyi random graph) is p^{k}