1
$\begingroup$

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

  • 0
    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.)2012-09-29

1 Answers 1

3

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

  • 0
    @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.2012-09-29