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

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?

• Have you included non-connected graphs in you small examples? Note that $(k-1)!\binom{n-2}{k-1}=\frac{(n-2)!}{(n-k-1)!}$ Jan 14, 2014 at 16:08
• Yes, I have included them.
– Leox
Jan 14, 2014 at 16:33
• The sum you give doesn't have to equal $1$, because there doesn't have to be a path between every pair of vertices. (There isn't a path if they are not in the same connected subgraph.) Jan 14, 2014 at 16:41
• Is correct my expression for $P_n(k)?.$
– Leox
Jan 14, 2014 at 16:54
• Yes, it is correct. I also think your approach is good, but I am not completely sure. For example, it is possible that there is a path of length $2$ and $4$, and you count them both. Jan 14, 2014 at 16:56

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.

• So, what is correct formula for $P_n(k)?$
– Leox
Jan 14, 2014 at 17:13
• @Leox I doubt there is a simple formula for $P_n(k)$ for general $n$ and $k$. To find this probability, you would need to do something like inclusion/exclusion over the set of paths. The amount of variables that you would sum over all possible cases would grow quite large. Jan 15, 2014 at 18:29
• @DPoole how about the case where we don't specify the length? (i.e. we only care about existence of any path): math.stackexchange.com/questions/2817161/… Jun 12, 2018 at 19:21

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$$.

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}

• Why divide the expected number of "2-paths" by $n-2$? $p^k$ is the probability of a specific path of $k$ edges is present. The question wants the probability that at least one of these paths occur. Jun 28, 2016 at 19:21
• @DPoole you're absolutely right. That was a hasty answer, apologies! Jul 21, 2016 at 15:59