What is the expected number of steps in a random walk from leaf to leaf in a full binary tree?

Question

Let $h \geq 2$ be a natural number. Consider a complete binary tree of height $h$. Say we take a random walk starting from the "leftmost" leaf. What is the expected number of steps before the "rightmost" leaf is visited? Is there a known closed form for this? If not, are there any lower or upper bounds?

As an example, let $h = 3$. Then we are looking at the above tree and asking what the expected number of steps to walk from node 4 to node 7 is.

---

What I've found:

Denote $n = 2^h - 1$ to be the number of nodes in the tree. This problem can be viewed as a system of linear equations. Let $x_i$ denote the expected number of steps to walk from node $i$ to node $n$. We are trying to find $x_{(n+1)/2}$ in the system $$ \begin{cases} x_1 = 1 + \frac{1}{2}x_2 + \frac{1}{2}x_3 \\ x_i = 1 + \frac{1}{3}x_{\lfloor i/2 \rfloor} + \frac{1}{3}x_{2i} + \frac{1}{3}x_{2i+1} & \text{for } 1 < i < \frac{n+1}{2} \\ x_i = 1 + x_{\lfloor i/2 \rfloor} & \text{for } \frac{n+1}{2} \leq i < n \\ x_n = 0. \end{cases} $$

I wrote a Python program to solve this system. I found the following values: $$ \begin{array}{c|c} h & \text{expected number of steps} \\ \hline 2 & 4 \\ \hline 3 & 24 \\ \hline 4 & 84 \\ \hline 5 & 240 \\ \hline 6 & 620 \\ \hline 7 & 1512 \\ \hline 8 & 3556 \\ \hline 9 & 8160 \\ \hline 10 & 18396 \end{array} $$ I plugged these values into OEIS, but there was no matching sequence.

---

Although I do not know how to solve for an exact value, I can provide a lower bound of $2^{h+1} - 3h - 1$.

Note that a walk from the leftmost leaf to the rightmost leaf must pass through the root. Therefore, we can lower bound the desired value by the expected number of steps before the root is visited in a random walk starting from the leftmost leaf. Then we are just asking how many steps it takes to randomly walk from a node at level $h$ to the root node at level $1$.

At level $h$, you always step to level $h-1$. At level $i$ where $1 < i < h$, you have a $\frac{2}{3}$ chance of stepping to a child at level $i+1$ and a $\frac{1}{3}$ chance of stepping to the parent at level $i-1$.

Let $x_i$ denote the expected number of steps to randomly walk from level $h-i+1$ to level 1. We are then trying to find $x_1$ in the system of equations $$ \begin{cases} x_h = 0\\ x_i = 1 + \frac{2}{3}x_{i-1} + \frac{1}{3}x_{i+1} & \text{for } 1 < i < h\\ x_1 = 1 + x_2. \end{cases} $$ I claim that $x_{i-1} = x_i + 2^i - 3$ for $1 < i \leq n$. Proceed by induction. As the case case, we have $x_1 = x_2 + 1 = x_2 + 2^2 - 3$. For the induction hypothesis, suppose that $x_{k-1} = x_k + 2^k - 3$. Then for our induction step, we have $$ \begin{align*} x_k &= 1 + \frac{2}{3}x_{k-1} + \frac{1}{3}x_{k+1} \\ &= 1 + \frac{2}{3}\left(x_k + 2^k - 3\right) + \frac{1}{3}x_{k+1} \end{align*} $$ which rearranges to $x_k = x_{k+1} + 2^{k+1} - 3$, proving the claim.

Then we have $$ x_1 = \sum_{i=2}^h \left( 2^i - 3 \right) = 2^{h+1} - 3h - 1. $$

Hence the expected number of steps to reach the root from a leaf is $2^{h+1} - 3h - 1$. This gives our lower bound.

---

I do not know where to go from here. Looking at the numbers, I suspect one might be able to prove a $\Omega(h2^h)$ lower bound.

Answer 1

First, the walk needs to get from the leaf to the root. This is a simple random walk in the vertical direction, with probability $\frac23$ to go down and $\frac13$ to go up. The expected time $a_k$ to reach the root from depth $k$ satisfies

$$ t_k=1+\frac23t_{k+1}+\frac13t_{k-1} $$

for $k=1,\ldots,h-2$ with boundary conditions $t_0=0$ and $t_{h-1}=1+t_{h-2}$. The general solution is $t_k=c_1+c_22^{-k}-3k$. The first boundary condition yields $c_2=-c_1$, and then the second one yields

$$ c_1-c_12^{1-h}-3(h-1)=1+c_1-c_12^{2-h}-3(h-2)\;, $$

with solution

$$ c_1=2^{h+1}\;. $$

Thus $t_k=2^{h+1}\left(1-2^{-k}\right)-3k$, so $t_{h-1}=2^{h+1}-4-3(h-1)=2^{h+1}-3h-1$.

Now we need to add up the times it takes to make progress towards the target leaf. At the root, we have probability $\frac12$ to go back to the left, where it will take us $t_1=2^{h+1}\left(1-2^{-1}\right)-3\cdot1=2^h-3$ to get back to the root, and probability $\frac12$ to go to the right, so the expected time $b_0$ to go right satisfies

$$ b_0=1+\frac12\left(2^h-3+b_0\right)\;, $$

with solution $b_0=2^h-1$. From then on, at depth $k$, we have probability $\frac13$ to make progress and $\frac23$ to stray back into a graph with $2^h-2-\frac12\left(2^{h-k}-2\right)=2^h-2^{h-k-1}-1$ edges, of which $2$ lead back, so the return time in this case is $2^h-2^{h-k-1}-1$. Thus the expected time $b_k$ to make progress satisfies

$$ b_k=\frac23\left(2^h-2^{h-k-1}-1+b_k\right)+\frac13\cdot1\;, $$

so

$$ b_k=2^{h+1}-2^{h-k}-1\;. $$

Note that this also covers $b_0=2^{h+1}-2^{h-0}-1=2^h-1$. Summing over $k$ from $0$ to $h-2$ yields a contribution

$$ \sum_{k=0}^{h-2}\left(2^{h+1}-2^{h-k}-1\right)=\left(2^{h+1}-1\right)h-2^{h+2}+5\;, $$

for a total of

\begin{align} 2^{h+1}-3h-1+\left(2^{h+1}-1\right)h-2^{h+2}+5 &=2^{h+1}h-2^{h+1}-4h+4\\ &=4(h-1)\left(2^{h-1}-1\right). \end{align}

P.S.: Note that this actually contains everything we need to calculate the expected number of steps from any node to any other node. If the initial node is at depth $a$, the final node is at depth $b$ and their lowest common ancestor is at depth $c$, then it takes

$$2^{h-c+1}\left(1-2^{c-a}\right)+3(c-a)=2^{h-c+1}-2^{h-a+1}+3(c-a)$$

steps to reach the common ancestor and

$$ \sum_{k=c}^{b-1}\left(2^{h+1}-2^{h-k}-1\right)=2^{h-b+1}-2^{h-c+1}+(b-c)\left(2^{h+1}-1\right) $$

steps to reach the final node, for a total of

$$ \left(2^{-b}-2^{-a}\right)2^{h+1}+(b-c)\left(2^{h+1}-1\right)+3(c-a)\;. $$

The case you were interested in was $c=0$ and $a=b=h-1$.