3
$\begingroup$

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})$?.

Improve this question
$\endgroup$
3
  • 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
    Commented Nov 19, 2017 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
    Commented Nov 19, 2017 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
    Commented Nov 19, 2017 at 22:25

2 Answers 2

Reset to default
4
$\begingroup$

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$.

Improve this answer
$\endgroup$
5
  • $\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
    Commented Nov 19, 2017 at 23:59
  • $\begingroup$ Where can I find the proof that the percolation probability of the 1-3-tree is 0? $\endgroup$
    – Or Meir
    Commented Nov 20, 2017 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
    Commented Nov 20, 2017 at 11:47
  • $\begingroup$ I just edited in a proof sketch which I think generalises to higher degrees. $\endgroup$
    – Florian Lehner
    Commented Nov 20, 2017 at 12:10
  • $\begingroup$ Note that the 1-3 tress has only countably many rays, so the percolation probability is zero by countable additivity $\endgroup$
    – Yuval Peres
    Commented Jun 24, 2021 at 1:44
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Nov 19, 2017 at 22:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .