Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We have an infinite $3$-ary tree, with root $R$. In coloring $C(p)$ each edge is black with probability $p$ and white with probability $1 - p$, and edges are independent.

Show that there is a $p^*$ where $0 < p^* < 1$ such that the graph with coloring $C(p)$ where $p$ is greater than $p^*$ has an infinite black binary sub-tree with probability $1$ and a graph with coloring $C(p)$ where $p$ is less than $p^*$ has an infinite black binary sub-tree with probability $0$.

share|improve this question
    
The first "less than" should be "greater than"? (Also, please use $\TeX$ for math formatting by enclosing math in dollar signs; single dollar signs for inline formulas and double dollar signs for displayed equations.) –  joriki Sep 29 '12 at 7:50

1 Answer 1

The entire infinite tree contains an infinite binary tree iff at least one of the infinite trees rooted at the children of the root contains one. Thus the probability $q$ for the tree to contain an infinite binary tree satisfies

$$q=1-(1-q)^3\;,$$

with solutions $0$, $1$ and $2$. Thus the only solutions in $[0,1]$ are $0$ and $1$. It's clear that $q$ is monotonic in $p$. It follows that there must be some $p^*$ at which $q$ switches from $0$ to $1$.

share|improve this answer
    
Nice. Do you know whether anything is known about the magnitudes of $p^*$ and $\hat p$? –  Brian M. Scott Sep 29 '12 at 8:25
    
@Brian: I removed the part about $\hat p$; it was wrong since it didn't take into account that there need to be edges between the root and the children that are roots of infinite binary trees. I don't know anything about the magnitude of $p^*$, but I'm thinking about it. –  joriki Sep 29 '12 at 8:50

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.