# Random walks on Complete Binary Trees

Let $$T$$ be a complete binary tree of height $$n$$ and root $$r$$.

A random walk starts at $$r$$, and at each step uniformly at random moves on a neighbor.

There are $$m$$ random walkers all starting at $$r$$ and let denote with $$H_1,\dots,H_m$$, the heights reached by the walkers after $$n$$ steps.

Show that, for some constant $$C$$ which do not have to depend on $$n$$ and $$m$$, it holds that

$$\mathbb{P}\left(\underset{i \in [m]}\max\left|H_i - \frac{n}{3}\right| \le C \sqrt{n\ln m}\right) \ge 1 - \frac{1}{m}$$

I have been trying several strategies, to appropriately define $$H_i$$ as sum of random variables and similar, but no one turned out to work. Do you have any idea/suggestion to attach this problem?

This answers the version of the question in which the goal is to show that with high probability, $$\max |H_i - \frac n 3| \leq C\sqrt{n\ln m}$$ for some constant $$C$$.

Since $$|H_{i+1}-H_i| \le 1$$, you can use Azuma's inequality (via Doob's martingale) to upper bound the probability of deviation from the mean, and so obtain your required bound, once we show that the expectation of $$H_n$$ is very close to $$\frac{n}{3}$$.

To this end, let $$X_i$$ be a random variable equal to $$+1$$ with probability $$2/3$$ and to $$-1$$ with probability $$1/3$$, and couple $$H_i - H_{i-1}$$ to the $$X_i$$: if $$H_{i-1} = 0$$ then $$H_i = 1$$, and otherwise $$H_i = H_{i-1} + X_i$$. Let $$Y_i$$ be a random variable equal to $$+2$$ if $$H_{i-1} = 0$$ and $$X_i = -1$$, and equal to $$0$$ otherwise, so that $$H_i = H_{i-1} + X_i + Y_i$$. In total, $$H_n = \sum_{i=1}^n (X_i + Y_i)$$.

In order to calculate $$\mathbb{E}[H_n]$$, notice first that $$\mathbb{E}[X_i] = \frac13$$. For calculating $$\mathbb{E}[Y_i]$$, let us notice that the event "$$H_{i-1}=0$$" is independent of the event "$$X_i=-1$$". Therefore, if we let $$Z_i$$ be the indicator of $$H_i = 0$$, then $$\mathbb{E}[Y_i] = \frac23 \mathbb{E}[Z_i]$$. Defining $$Z = \sum_{i=1}^\infty Z_i$$, we have $$\frac{n}{3} \leq \mathbb{E}[H_n] \leq \frac{n}{3} + \frac{2}{3} \mathbb{E}[Z].$$ Let $$a_k$$ be the expected number of visits to the root if starting at a node at depth $$k$$ (so $$a_0 = \mathbb{E}[Z]$$), let $$p = 1/3$$, and let $$q = 1-p = 2/3$$. Then $$a_k$$ satisfies the following recurrence: $$a_0 = 1 + a_1, \quad a_k = p a_{k-1} + q a_{k+1}.$$ Let us prove inductively that $$a_k = (p/q)^k + a_{k+1}$$. This holds for $$k = 0$$. Given that $$a_{k-1} = (p/q)^{k-1} + a_k$$, we have $$a_k = pa_{k-1} + qa_{k+1} = p(p/q)^{k-1} + pa_k + qa_{k+1}.$$ This implies that $$qa_k = p(p/q)^{k-1} + qa_{k+1}$$, and so $$a_k = (p/q)^k + a_{k+1}$$, as claimed.

When $$p < 1/2$$, we know that $$\mathbb{E}[H_n] \longrightarrow \infty$$, and so $$a_k \longrightarrow 0$$ (this requires proof). Therefore $$a_0 = \sum_{k=0}^\infty (p/q)^k = \frac{1}{1-p/q} = \frac{q}{q-p}.$$ (Similarly, $$a_k = (p/q)^k \frac{q}{q-p}$$.) In our case, $$a_0 = 2$$, and so $$\frac{n}{3} \leq \mathbb{E}[H_n] \leq \frac{n+4}{3}.$$

• Thanks a lot Yuval! There is still something which is not clear to me. In particular, I'm struggling to understand how to solve the recurrence. Why qa_k = (p/q)^(k-1) + qa_{k+1}? Also, I think there is a typo in the definition of the recurrence for a_k, from my understanding it should be a_k = pa_(k-1) + qa_(k+1). – Andrea Apr 25 at 10:40
• Right, the recurrence should be as you wrote. From there you get the other recurrence by substitution. – Yuval Filmus Apr 25 at 12:43
• Thanks Yuval your answer has been really helpful! As a side, I was thinking that, for finite n, a_k = 0 for any k > n since the walker only has n step in total and can't reach the root once it is on a leaf. So maybe there is no need to consider the limiting case for a_k. – Andrea Apr 26 at 11:54
• It won’t gain you much, but you can try it. – Yuval Filmus Apr 26 at 12:05

This answers a previous version of the question, in which the goal was to prove that with high probability, $$\max |H_i - \frac{n}{3}| \geq C\sqrt{n\ln m}$$ for some constant $$C > 0$$.

When a particular walker is not at the root, it has a probability of 2/3 to go down a step, and a probability of 1/3 to go up a step. This is where $$n/3$$ comes from. However, when it is at the root, it always goes down. This suggests comparing $$H_i$$ to a sum of $$n$$ i.i.d. variables whose distribution is $$+1$$ w.p. $$2/3$$ and $$-1$$ w.p. $$1/3$$. Indeed, if $$X_i$$ is a variable with that distribution, then $$H_i$$ stochastically dominates $$X_i$$. Hence it suffices to show that $$\mathbb{P}\left(\max_{i \in [m]} X_i \geq \tfrac{n}{3} + C\sqrt{n\ln m}\right) \geq 1-\frac{1}{m}.$$ (More formally, we can construct a coupling of the $$H_i$$ and $$X_i$$ in which $$H_i \geq X_i$$.)

Up to an affine transformation, the distribution of $$X_i$$ is binomial, so it should be easy to obtain whatever bound you wish. You can take a look at Lower bounds on binomial and Poisson tails: anapproach via tail conditional expectations by Pelekis, for example.

• Thanks for your reply! I corrected a typo in my formulation: the goal is to show that the heights are within the band not outide. This being said, notice that H_i is defined starting from the leafs so the X_i you defined is not dominated by H_i. However noticing that H_i = n - D_i, where D_i is the depth of the walker i, then X_i is dominated by D_i and H_i is then dominated by n - X_i. The problem with this argument is that it just leads me to a single side bound, while a two-side bound is needed. Trying to get a lower bound to D_i in the same way, does not seems to work! – Andrea Apr 21 at 20:19
• It’s hard to hit a moving target. I’m not planning on answering more than one version of the question. Next time try to spend as much time asking the question as potential responders would spend answering it. – Yuval Filmus Apr 21 at 20:23
• You can try using Azuma's inequality. – Yuval Filmus Apr 22 at 2:36