2
$\begingroup$

You begin at a root node that has 2 children. Each of those two children have two more children, and each of those children have two final children (i.e., there are 15 nodes in the graph). How do I find the expected value of how many steps it will take to reach the final children, if at each step the current node moves to the parent node with probability 1/3 and to each child with probability 1/3 (except, of course the root, which just moves to its children)?

I can treat the problem like a random walk in 1d, with each forward step occurring with probability 2/3 and backwards occurring with probability 1/3. However, the root node never moves backward. I'm having trouble reconciling this part with the normal random walk analysis, as well as the different probabilities of forward and backward steps. Thanks!

$\endgroup$
  • $\begingroup$ I'm curious is it possible to solve this problem for the general $n$ levels deep case? $\endgroup$ – user137302 May 6 '14 at 1:23
  • 1
    $\begingroup$ Hmmm... Did you read my answer? $\endgroup$ – Did May 6 '14 at 6:03
2
$\begingroup$

You have four levels, with 1,2,4 and 8 vertices respectively. You want to find the expected number of steps it will take to reach any leaf.

First, it matters only on which level you are, the particular node is unimportant.

Now, let $t_0, t_1, t_2, t_3$ denote the expected number of steps from that level to any leaf. Now, we can obtain the set of equations:

$$ \begin{cases} t_0 = 1+t_1, \\ t_1 = 1+ \frac{2}{3}t_2 + \frac{1}{3}t_0, \\ t_2 = 1+ \frac{2}{3}t_3 + \frac{1}{3}t_1, \\ t_3 = 0. \end{cases} $$

Simplifying we get

$$ \begin{cases} t_0 = 1+t_1 \\ t_1 = 1+ \frac{2}{3}(1+\frac{1}{3}t_1) + \frac{1}{3}(1+t_1) = \frac{5}{9}t_1 + 2 \\ t_2 = 1 + \frac{1}{3}t_1 \\ t_3 = 0 \end{cases} $$

which implies that $t_1 = \frac{9}{2}$ and $t_0 = 5.5$.

I hope this helps $\ddot\smile$

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

As usual, one computes the expected number of steps $e_i$ necessary to reach level $3$ starting from a node at level $i$ with $0\leqslant i\leqslant3$, and the answer is $e_0$. The boundary condition is $e_3=0$ and the one-step recursion reads $$e_0=1+e_1,\quad e_1=1+\frac13e_0+\frac23e_2,\quad e_2=1+\frac13e_1, $$ which yields $$e_0=\frac{11}2.$$ More generally, to reach the level at distance $n$ from the root, the mean number of steps necessary is $$ 3n-4\cdot(1-2^{-n}). $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How did you solve the system of equations for $n$ variables? The induction seems pretty involved. $\endgroup$ – user137302 May 5 '14 at 21:45
  • $\begingroup$ But would you mind explaining how you did the inductive step so easily? $\endgroup$ – user137302 May 6 '14 at 3:41
  • $\begingroup$ For general $n$, one solves $e_k=ae_{k-1}+(1-a)e_{k+1}+b$ by looking for $e_k=Ar^k+Bs^k+Ck+D$ where $r$ and $s$ solve the characteristic equation $x=a+(1-a)x^2$. $\endgroup$ – Did May 6 '14 at 6:05
  • $\begingroup$ How did you know to do this? And can you elaborate further about how you solve for the coefficients A, B, C, and D? $\endgroup$ – user137302 May 6 '14 at 20:49
  • $\begingroup$ A general result is that difference equations $\sum\limits_{i=0}^Ia_iu_{k+i}=0$ are solved by linear combinations of the sequences $u_k=r^k$ where $r$ solves $\sum\limits_{i=0}^Ia_ir^i=0$. Here, the $+Ck$ terms allows to get the $+b$ term. By the way, there is a mistake in my previous comment: the characteristic equation has roots $r$ and $1$ hence $e_k=Ar^k+Ck+D$. The two coefficients $A$ and $D$ are determined by the two boundary conditions $e_n=0$ and $e_0=1+e_1$. $\endgroup$ – Did May 6 '14 at 23:32

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.