Let's consider the following building process of a binary tree $T$: We start with one vertex - root of the tree T. Next, we choose $n$ times a leaf $v$ in tree $T$ and we add two children to that leaf. A leaf $v$ at depth $d$ has probability $\frac{1}{2^d}$ of being chosen. We assume that the root is at depth $0$.
Let $H$ be the depth $T$ at the end of the process. Prove that $$\exists c > 0. \quad P(H \ge c \cdot \log(n)) = O\left(\frac{1}{n^{2016}}\right)$$
Hint: Described building process is equivalent to the following one: Consider a complete binary tree $T'$ with depth $n$ and root $r$. Let $T$ be a subtree of $T'$. In every step we choose (with uniform distribution) a leaf $w$ in $T'$. Note that $v$ in the original algorithm is the only leaf of $T$ on the path from $r$ to $w$.
This is an exercise from a test I'm preparing for. I wanted to use Markov inequality, so I tried to count $EH$. I thought that $H$ = $H_1 + ... + H_n$, where $H_i$ are Bernoulli's random variables and $H_i = 1$ if there is a vertex at depth $i$. I wasn't able to finish that, though.
For $1 \le i \le n$, let $A_i$ be the event that, on step $i$ of the algorithm, a leaf at depth $2018 \lg n$ is chosen.
The probability of $A_i$ depends on $i$ and also on the tree built up until that point (for example, when there are no such leaves to choose, $\Pr[A_i] = 0$) but we always have $$ \Pr[A_i] \le n \cdot 2^{-2018 \lg n} = n^{-2017}. $$ Whatever the tree looks like at step $i$, there are at most $n$ leaves at depth $2018 \lg n$ (because there are at most $n$ leaves in the tree) and each such leaf has probability $2^{-2018 \lg n}$ of being chosen.
Next, by the union bound, $$ \Pr[A_1 \lor A_2 \lor \dots \lor A_n] \le n \cdot n^{-2017} = n^{-2016}. $$ Therefore $$ \Pr[H > 2018 \lg n] \le n^{-2016} $$ because, in order for the final depth to exceed $2018 \lg n$, at some point a leaf at that depth must be chosen.