Random walks on Complete Binary Trees

Question

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?

Thanks in advance!

Answer 1

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

Answer 2

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.