Path cardinality for random $(a+b)$-ary infinite trees

Question

Consider a random infinite binary tree $T(a,b)$, so that $a$ denotes the probability of a left edge branching from any root-connected node,and $b$ denotes the probability of a right edge branching from any root-connected node. We establish an inductive base case, so that $T(0,0)$ contains the root node only.

$T(1,0)$ and $T(0,1)$ trivially has path cardinality $\aleph_0$ (*) . $T(1,1)$, the infinite complete binary tree, trivially has Continuum path cardinality.

$T(a,b)$ is finite for $a+b<1$.

$T(a,b)$ has path cardinality $\aleph_0$ for any $a+b=1$.

Now, is it then true that, $T(a,b)$ has Continuum path cardinality for $a+b>1$?

Intuitively this seems to be the case; Consider for example $T(1,\epsilon )$, for an infinitesimal probability $\epsilon$. On average for every $1/ \epsilon$ left-most nodes there is a right-branch. For each occurrence of a right branching node, we contract the graph, deleting all intermittent nodes which produced no right branch, constructing a new graph node, which branches both left and right. By induction we can then show that $T(1,\epsilon)$ is isomorphic to $T(1,1)$, and therefore has Continuum path cardinality. It seems a similar argument can be used for any $T(a,b)$ with $a+b>1$. Apologies if this is trivial. Does anyone know of any relevant references on path cardinality for random sub-graphs of the infinite complete binary tree?

(*) path cardinality of $T$ is short for the cardinality of the set of all paths in $T$.

Answer 1

Yes, $T(a,b)$ has continuum cardinality when $a+b>1$... with positive probability. Of course there is also positive probability that $T(a,b)$ has no infinite paths, if $a<1$ and $b<1$.

$T(1,0)$ has only one infinite path, so ``path'' means finite-or-infinite path.

Background

The relevant result, the Extinction Criterion below, was first stated by Bienaymé in 1845; see Heyde and Seneta (I. J. Bienaymé. Statistical theory anticipated) pp. 116--120 and Lyons and Peres (Probability on Trees and Networks, Cambridge University Press, in preparation. Current version available at http://mypage.iu.edu/~rdlyons/), Proposition 5.4. The first published proof of Bienaymé's theorem appears in Cournot (1847, De l'Origine et des Limites de la Correspondance entre l'Algèbre et la Géométrie, Hachette, Paris) pp. 83--86.

Extinction Criterion

Given numbers $p_{k}\in [0,1]$ with $p_{1}\ne 1$ and $\sum_{k\ge 0}p_{k}=1$, let $Z_{0}=1$, let $L$ be a random variable with $\mathbb P(L=k)=p_{k}$, let

$ \{ L^{(n)}_i \},\quad n,i\ge 1 $

be independent copies of $L$, and let $$ Z_{n+1}=\sum_{i=1}^{Z_{n}}L_{i}^{(n+1)}. $$ Let $q=\mathbb P((\exists n)\, Z_{n}=0)$. Then $q=1$ iff $\mathbb E(L)=\sum_{k\ge 0}kp_{k} \le 1$. Moreover, $q$ is the smallest fixed point of $f(s)=\sum_{k\ge 0}p_{k}s^{k}$.

Solution sketch

As stated the Extinction Criterion only shows that with positive probability there is at least one infinite path. Now consider, along this path, the possibility of branching off to create another infinite path. You get infinitely many independent events, so the probability that they all fail to happen is 0. Continuing this way, we get a positive probability of continuum many infinite paths.