7

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

TheNotMe
  • 4,841

1 Answers1

5

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

dibyendu
  • 539
Calvin Lin
  • 68,864
  • 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
  • I can't see how you use the linearity of expectation. Could you elaborate it a bit? – Ahmet Bilal Dec 24 '21 at 12:55
  • @AhmetBilal Can you elaborate on which part you don't understand? EG Do you know what the linearity of expectation is? Do you understand why we want to "count the number of times a given path is in a configuration", or how it is counted? – Calvin Lin Dec 24 '21 at 16:33
  • Ok I think I didn't understand the fact that linearity of expectation applies even though random variables are not independent. So you defined a boolean random variable for each simple path between any two vertex of an n-vertex graph which is 1 when the path exists and 0 otherwise. Then in order to find the expected value of the sum you use the linearity of expectation and sum up expectations of individual random variables. Even though they are indeed dependent. I think I see now, thank you :) – Ahmet Bilal Dec 24 '21 at 18:24
  • @AhmetBilal Right, and that's part of the reason why using indicator variables is so powerful. For a more basic illustration, what is the expected number of consecutive HH pairs when you toss 5 coins in a row? $\quad$ We could also apply this Indicator variable approach to calculating variance, but just deal with the covariance. IE $Var(\sum I_i) = \sum Var (I_i) + \sum 2 Cov(I_i, I_j) $. EG What is the variance of the previous? – Calvin Lin Dec 24 '21 at 19:40
  • I defined 4 identical random variables one for each pair in a series of 5 tosses. Let's call any of them $X$. From what I understand the formula you wrote down, the second sum should be for all $i$,$j$ that are not equal. And the whole thing can be expressed as sum of covariances for all $i$,$j$ (including the identicals which end up being variance). Am I right? Since these are identical r.v. covariance boils down to variance and hence I calculated $3 \times 4 \times Var(X) = 35/8$. – Ahmet Bilal Dec 25 '21 at 22:03
  • @AhmetBilal You're forgetting/miscalculating the covariance. Note that $Cov(I_1, I_2)$ is positive. Can you recheck? – Calvin Lin Dec 27 '21 at 16:42