Random walk on tree

Question

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!

Answer 1

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

Answer 2

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$