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

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

There is $ m $ Random hikers from $ r $ and let denote with $ H_1, dots, H_m $, the heights reached by walkers after $ n $ not.

Show that for a constant $ C $ which should not depend on $ n $

and $ m $, he argues that

$ mathbb {P} ( underet {i in [m]} max left | H_i – frac {n} {3} right | ge C sqrt { n n}} ge 1 – frac {1} {n} $

I've tried several strategies to define correctly $ H_i $ as a sum of random variables and the like, but no one has turned out to work. Do you have an idea / suggestion to attach this problem?

Thanks in advance!