Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
If you're satisfied with the answer you could "accept" it... thanks! –  Bjørn Kjos-Hanssen Oct 3 '10 at 6:32
    
Absolutely! Thanks again. –  Halfdan Faber Oct 3 '10 at 6:47

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
    
Answering your question in paranthesis: the set of finite-or-infinite paths from the root, in the one infinite path of T(1,0) is countably infinite. So, yes. Thanks for the answer; very enlightening! –  Halfdan Faber Sep 27 '10 at 6:46
    
@Halfdan: You're welcome. It's quite a useful result. –  Bjørn Kjos-Hanssen Sep 27 '10 at 6:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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