Given is a constant degree rooted tree of depth $D$. It is also known that the total number of nodes in the tree is at most $D^2$. There is a probabilistic process with discrete time steps on the nodes that work as follows:

- A node becomes
**eligible**to participate in the process when all of its children have**succeded**. - Once eligible, the node
**succeeds**in each time step with iid probably $\frac12$. Once successful, it is "done", i.e. stays succeeded.

I would like a bound on how many steps it requires for all nodes to succeed with probability $1 - \delta$ where $\delta$ is potentially much smaller than $\frac1{D^2}$.

I can see a bound of $O((D + \log{\frac{1}{\delta}})\log D)$ as outlined below. I was wondering if the $\log D$ is necessary?

Outline of argument for $O((D + \log{\frac{1}{\delta}})\log D)$: Consider to be the number of steps required for the depth of tree of unsuccessful nodes to reduce by 1. Since there are at most $D^2$ leaves at any given time, the expected time for this reduction is $\log D$ steps. The situations for different depths are essentially independent (can be written as martingale), and then a concentration inequality would give us the required bound.