Consider a rooted tree of height $h$, such that all the leaves are at last layer. We perform the following random process: each edge is deleted with probability $0.5$, and otherwise it is retained. We are interested in the probability that after the process ends, there remains a path from the root to one of the leaves. In particular, we are interested in whether the probability goes to zero as $h$ goes to infinity or not.

It is known that if the tree is a complete $d$-ary tree for $d > 2$ then this probability is greater than $0$ regardless of $h$. However, I am interested in the case where the graph is irregular, and in particular may have internal vertices with a large number of children and may have internal vertices with only one or two children.

Suppose that we know that the average degree in each layer is large: Say, there is some large constant $d$ such that in every layer, the average number of children of vertices in that layer is at least $d$. Suppose that we also know that the maximal degree of a vertex is bounded, i.e., the number of children that a vertex can have is at most some constant $D$ which is independent of $h$ (and may be significantly larger than $d$, e.g., $D= 2^d$). Can we prove that, the probability that there is a path from the root to a leaf does not go to $0$ when $h$ goes to infinity (assuming $d$ is sufficiently large)? If not, can we say something about the rate of convergence (e.g., the probability is at least $\frac{1}{\log h})$?.

  • 1
    $\begingroup$ No. That’s definitely not enough information. One such tree is that you make every vertex have a single child except for one very productive vertex on the left side of each level (so each productive node is the child of another productive node). The probability that there’s a path from the root to a leaf is extremely low. $\endgroup$ – Anthony Quas Nov 19 '17 at 21:31
  • $\begingroup$ @AnthonyQuas: I was thinking about my answer before hitting the "answer" button, and only saw your comment afterward. We agree (but I wonder what would happen if the leftmost vertex has sufficiently many children. $\endgroup$ – Benoît Kloeckner Nov 19 '17 at 21:37
  • $\begingroup$ Thanks, there is definitely some information I forgot to mention (namely, that there is also a bound on the maximal degree). I am adding it now. $\endgroup$ – Or Meir Nov 19 '17 at 22:25

You still need more information on the structure of the tree. The 1-3-tree (Example 1.2 in Lyons & Peres: Probability on trees and networks) shows that the probability can go to 0, even if the maximum degree is bounded.

Here is a quick proof sketch: It is not hard to see that the subtree hanging off of any other than the rightmost vertex in every layer only contains finitely many rays. Simply observe that there are $\theta(3^n)$ vertices at level $n$ of the rightmost subtree and only $2^n$ vertices at this level in total. Thus eventually all vertices with 3 descendents will be contained in the rightmost subtree.

So the probability for percolation in any subtree except the rightmost one is $0$. If percolation happens, then all edges of the rightmost branch must be open, which of course happens with probability $0$.

Analogously one can construct a $1$-$n$-tree with an average number of $n-1$ successors and see that the probability for percolation is $0$.

  • $\begingroup$ Thanks! The 1-3-tree is a good example. I cannot think of a reason for my trees not to have a similar structure. However, the average degree of the 1-3-tree is 2, which is rather small, whereas the average degree in my trees can be an arbitrary large constant. In order to get my question fully answered, I still need to check if the 1-3-tree can be changed to have a larger average degree. $\endgroup$ – Or Meir Nov 19 '17 at 23:59
  • $\begingroup$ Where can I find the proof that the percolation probability of the 1-3-tree is 0? $\endgroup$ – Or Meir Nov 20 '17 at 8:09
  • $\begingroup$ I think the first proof of this can be found in R. Lyons, Random Walks and Percolation on Trees, Ann. Probab. 18 (3): 931-958, 1990. $\endgroup$ – Florian Lehner Nov 20 '17 at 11:47
  • $\begingroup$ I just edited in a proof sketch which I think generalises to higher degrees. $\endgroup$ – Florian Lehner Nov 20 '17 at 12:10

It seems to me the worst case should be the following: assume your tree is drawn on the plane so that each layer is ordered from left to right, and assume that in each layer the leftmost vertex has very many children and all others have exactly one child. Then at each layer, there is a $1/2$ chance to cut off all the "rich" part of the tree, leaving a bunch of branchless trees being ripped apart by the removing of half the edges. I did not do the computation but assuming the rich vertex at layer $k$ has $d^k$ children, the probability of a path from the root to a leaf should still go to zero exponentially fast.

  • $\begingroup$ Thanks for the answer. Indeed, I forgot to mention that I am interested in a special case in which the maximal degree is bounded. I corrected my question accordingly. $\endgroup$ – Or Meir Nov 19 '17 at 22:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.