# In a random graph of $n$ vertices, what is the expected value of the number of simple paths?

I am very new to discrete probabilty and was asked this question:

In a random graph $G$ on $n$ vertices (any edge can be in the graph with probabilty of $\frac{1}{2}$,) what is the expected value of the number of paths between a vertex $v$ and a vertex $u$? (The answer might be a summation).

How do we exactly begin this? I know we have to define $f(u,v) = \text{number of simple paths between v and u}$, and we need to calculate $E[f(u,v)] = \sum_{u,v \in \omega} {f(u,v) \cdot Pr(u,v)}$. But what exactly is $f(u,v)$ here and what is our $\omega$?

Given any simple path between $u,v$ of length $l$, the expected number of times that it will be a path is $\left(\frac{1}{2}\right)^l$. Hence we need to sum over all such paths between $2$ vertices $uv$.
Fix $k$. How many simple paths of length $k+1$ are there from $u$ to $v$? There must be $k+2$ vertices involved, of which the initial and final vertices are $u$ and $v$. Next, we have to pick any $k$ out of the remaining $n-2$ vertices. The order that the vertices are picked matter, hence there are $(n-2)^{\underline k} = k!{n-2\choose k}$ simple paths of length $k+1$ between vertices $u, v$.
$$E[X] = {n \choose 2} \left[ \sum_{k=0}^{n-2} k!{n-2\choose k} \times \frac{1}{2^{k+1}}\right]$$
• can you explain the $n-2 \choose k$ again please? – TheNotMe Jun 19 '13 at 21:26
• @TheNotMe It should be $(n-2)Pk$ instead (edited). – Calvin Lin Jun 19 '13 at 21:45
• What is $Pk$ here? First time I see this symbol. – TheNotMe Jun 20 '13 at 10:36
• $nPk$ is permuting $k$ items out of $n$, and it is equal to $nPk = \frac{n!}{(n-k)!}$. Just as how ${n \choose r}$ is often denoted as $nCr$, and both are equal to $\frac{n!}{k!(n-k)!}$. Just different conventions/notations. – Calvin Lin Jun 20 '13 at 14:39