Pergunta

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!

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top