5
$\begingroup$

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?

full binary tree of depth 3

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.

$\endgroup$
4
  • $\begingroup$ What are the transition probabilities? $\endgroup$ May 11, 2016 at 5:34
  • $\begingroup$ Equal probability distributed among neighboring nodes. At a leaf node, always step to the parent. At the root node, step to the left child with $1/2$ probability and to the right child with $1/2$ probability. At an internal node, step to the left child with $1/3$ probability, to the right child with $1/3$ probability, and to the parent with $1/3$ probability. $\endgroup$
    – Tom Tseng
    May 11, 2016 at 5:39
  • 2
    $\begingroup$ When you divide by 4, you can find this sequence oeis.org/A066524 So we can guess the general term to be $4(h-1)(2^{h-1}-1)$ $\endgroup$
    – BGM
    May 11, 2016 at 5:43
  • $\begingroup$ Nice find! That formula definitely does fit all the data points I gave. The next question is whether there's a nice way to prove it.... $\endgroup$
    – Tom Tseng
    May 11, 2016 at 6:07

1 Answer 1

5
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Fantastic! This makes sense to me. Question: how did you find $t_k=c_1+c_22^{-k}-3k$? I can see that it works, but is there a general way to solve equations of that form? (Also, minor typo: the sign is missing in "$c_2 = -c_1.$") $\endgroup$
    – Tom Tseng
    May 11, 2016 at 7:17
  • $\begingroup$ @TomTseng: The general solution of linear recurrences with constant coefficients is analogous to the general solution of linear differential equations with constant coefficients. The general solution is the sum of a special solution of the inhomogeneous equation and the general solution of the homogeneous equation. In a recurrence for expected times in a random walk, the coefficients on both sides sum to one, which allows a linear ansatz $t_k=mk$ to solve for the constant inhomegeneity; substituting that into the recurrence yields $m=-3$. $\endgroup$
    – joriki
    May 11, 2016 at 7:39
  • $\begingroup$ @TomTseng: The homogeneous equation is solved using the geometric ansatz $t_k=c\lambda^k$, which yields the characteristic equation $\lambda=\frac23\lambda^2+\frac13$, with solutions $\lambda=1$ and $\lambda=\frac12$. For more on all this, see Wikipedia. $\endgroup$
    – joriki
    May 11, 2016 at 7:41
  • $\begingroup$ @TomTseng: I added a solution for the general case from any node to any other node. $\endgroup$
    – joriki
    May 11, 2016 at 8:50

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.