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


This is where you should use the linearity of expectation. Instead of trying to count the number of simple paths in a given configuration, you count the number of times a given path is in a configuration.

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

  • $\begingroup$ can you explain the $n-2 \choose k$ again please? $\endgroup$ – TheNotMe Jun 19 '13 at 21:26
  • $\begingroup$ @TheNotMe It should be $(n-2)Pk$ instead (edited). $\endgroup$ – Calvin Lin Jun 19 '13 at 21:45
  • $\begingroup$ What is $Pk$ here? First time I see this symbol. $\endgroup$ – TheNotMe Jun 20 '13 at 10:36
  • $\begingroup$ $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. $\endgroup$ – Calvin Lin Jun 20 '13 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.