Promenades aléatoires sur des arbres binaires complets

Question

Laisser $ T $ être un arbre binaire complet de hauteur $ n $ et root $ r $.

Une marche aléatoire commence à $ r $, et à chaque étape uniformément au hasard se déplace sur un voisin.

Il y a $ m $ Des marcheurs aléatoires à partir de $ r $ et laisser dénouer avec $ H_1, DOTS, H_M $, les hauteurs atteintes par les marcheurs après $ n $ pas.

Montrez que, pour une constante $ C $ qui n'a pas à dépendre $ n $et $ m $, il tient que

$ mathbb {p} Left ( Underme ) ge 1 - frac {1} {m} $

J'ai essayé plusieurs stratégies, pour définir de manière appropriée $ H_i $ À titre de somme de variables aléatoires et similaires, mais personne ne s'est avéré fonctionner. Avez-vous une idée / suggestion pour attacher ce problème?

Merci d'avance!