Completion time of a process on a tree

2013-01-24T11:02:16Z

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.

Answer by Kevin P. Costello for Completion time of a process on a tree

2013-01-24T22:33:18Z

It seems the $\log D$ is unnecessary. We can model the process as follows:

Let $v_1, \dots, v_j$ be the initial leaves of the tree, and let $p_1, \dots, p_j$ be the paths eminating from the leaves to the root vertex. At each step we perform the following:

-Delete the initial vertex of each $p_i$ independently with probability $1/2$.
-If any $p_j$ is a proper subset of some other $p_k$, delete it. If there are two or more identical paths, delete all but one.

Note that by construction after each step the leading vertex of $p_j$ is eligible (if it were not eligible, $p_j$ would be a proper subset of the path containing its eligible child) and the leading vertices are distinct. Furthermore, every unsuccessful vertex is in at least one path until it becomes successful. So the tree becoming successful is equivalent to all the paths either being deleted or becoming empty.

Now consider an alternative process where we do not perform the second step at all, always just reducing each list by $1$ with probability $1/2$ at each step (now a vertex may be deleted from one list but stay on other lists). This alternative process always takes at least as long to finish as the original process. But now it's easy to analyze. Each path has length at most $D$ initially, so the probability it lasts beyond $2D+c\sqrt{D}$ steps decays exponentially in $c^2$. There's at most $D^2$ paths initially, so if we take $c$ large enough to make this probability smaller than $\frac{\delta}{D^2}$, we'll have the desired probability.

I believe this should get you something like $2D+O(D^{1/2} \log(D/\delta))$, which is pretty much the best you can hope for (consider a tree consisting of $D$ disjoint paths of length $D$ from the root).

Completion time of a process on a tree - MathOverflow

Completion time of a process on a tree

Answer by Kevin P. Costello for Completion time of a process on a tree