Passeggiate casuali su alberi binari completi

Question

Permettere $ T $ essere un albero binario completo di altezza $ n $ e radice $ r $.

Inizia una passeggiata a caso $ r $, e ad ogni passaggio uniformemente a caso si muove su un vicino.

Ci sono $ m $ Walker casuali tutti a partire da $ r $ E lascia che denoti con $ H_1, dots, h_m $, le altezze raggiunte dai camminatori dopo $ n $ Passi.

Mostra che, per qualche costante $ C $ da cui non deve dipendere $ n $e $ m $, lo tiene

$ mathbb {p} left ( underset {i in [m]} max left | h_i - frac {n} {3} a destra | le c sqrt {n ln m} a destra ) ge 1 - frac {1} {m} $

Ho provato diverse strategie, per definire adeguatamente $ H_i $ come somma di variabili casuali e simili, ma nessuno si è rivelato funzionare. Hai idea/suggerimento per allegare questo problema?

Grazie in anticipo!