Halting probability of random tree-generating algorithm

Question

Suppose I have a tree-generating algorithm as follows.

Begin with one root vertex. With equal probability, create either three subvertices or none. Recurse and repeat for each of the subvertices (if any).

What is the probability that this algorithm will halt?

Answer 1

Let there be $1$ vertex at time $0$. At time $n$, take all vertices that currently exist and either replace them with three new vertices or delete them, with equal probability. We are interested in the probability that all vertices die out at some point.

Let $p_n$ be the probability that all vertices die out in $n$ or less steps. As has been observed by Chas, $$ p_{n+1} = \tfrac12 +\tfrac12\left(p_n\right)^3 $$ and we are interested in the limit as $n \to \infty$ of $p_n$.

First, observe $p_n$ are increasing, by definition since if all vertices are dead after $n-1$ steps then they are also dead after $n$ steps. Second, I claim that $p_n \le \alpha$ for all $n$, where $\alpha = \frac{-1 + \sqrt{5}}{2}$ is a root of $x = \tfrac12 + \tfrac12 x^3$. To prove this, since $p_{n-1} \le p_{n}$, we have $$ p_{n} = \tfrac12 + \tfrac12 \left( p_{n-1} \right)^3 \le \tfrac12 + \tfrac12 \left( p_{n} \right)^3 $$ so $$ p_n^3 - 2p_n + 1 \ge 0 $$ Factoring, $$ (p_n - 1)(p_n - \alpha)(p_n + \alpha + 1) \ge 0 $$ So either $p_n \in [-\alpha - 1, \alpha] = [-1.618033\ldots, 0.618033\ldots]$ or $p_n \in [1, \infty)$. But $p_n \in [0,1]$. And $p_n \neq 1$ because there is a positive probability that all vertices so far have split and not halted. So $p_n \in [0, \alpha]$, i.e. $p_n \le \alpha$ as claimed.

Since $p_n$ is an increasing sequence of probabilities, the sequence converges. But it also converges to a root of $x^3 - 2x + 1$. Since $0 \le p_n \le \alpha$ for all $n$, it must converge to something in this range. So it must converge to $\alpha$.

Answer 2

Probability of stopping in exactly n steps is the probability of $n-1$ no-stopping events times probability of last stopping event, as they are independent. Hence the probability of stopping exactly at step n is $(1/2)^{n-1} (1/2)$ = $(1/2)^n$ for n = 1,.... Then add all of those $\sum^\infty_1 (1/2)^k$ = $1/2 + 1/4 + 1/8 + ...$ = 1, so it will stop almost surely.

If one wants a recursive approach, this is what one would do. Let $p_n$ be the probability of stopping in n or less steps. Then the probability of stopping in $n+1$ or less steps is $$p_{n+1} = p_n + \frac{1}{2}(1-p_n)$$ This is, either you stopped already in less than n steps, or if you haven't (with probability $1-p_n$), then you stop now with independent probability 1/2.

As we are interested in the limit $\lim_{n->\infty} p_n$, by continuity it must obey the equation $$p = p + 1/2(1-p)$$ which has as unique solution $p=1$.

I stand corrected

The algorithm is, in pseudo code:

def make-tree
  if random < 0.5
    then Leaf
  else
    Tree of [make-tree, make-tree, make-tree]
end

The question is whether this algorithm ever returns or not, and if not, with which probability - as it has a randomness attached to it.

As others said: let p be the probability of finishing, then for any run $\omega$ (the use of this will be apparent next) of the algorithm, $p(\omega) = 1/2 + 1/2 (p(\omega_1) p(\omega_2) p(\omega_3))$, as the algorithm needs to either finish with a Leaf or finish 3 full trees before returning the answer, and those 3 runs are independent.

As there is nothing special or distinguishing any of the subsequent runs, we conclude that $p(\omega)$ = $p(\omega_1)$ = $p(\omega_2)$ = $p(\omega_3)$ = P, and this leads to the equation $$P = \frac{1}{2} + \frac{1}{2} P^3$$

This has two solutions in [1,0]. $P = 0$ and $P = \frac{\sqrt{5}-1}{2}$. Why?

Here my thoughts about this.

Inspecting the argument, one finds that above there is an implicit "if it finishes". There, we automatically introduced $P=1$ as assumption in the argument. Inspecting the argument little closer, one can actually see $\omega$ (a particular run up-to-a node) as a finite digit sequence in base 3: $0,d_1d_2d_3...$ If one stops in a Leaf, you could store in the leaf the corresponding finite sequence up to that point. This turns a stoping run of the algorithm into a finite set of finite base 3 sequences. However, this algorithm could run into a cousin of the Cantor set, which has measure 0, hence the probability 1 in the answer. Paradoxical.

Answer 3

I think you could proceed recursivelly. Call $p$ such a probability, than $$p= \frac{1}{2} + \frac{1}{2}p^3,$$ and $$p = \frac{1}{2} + \frac{1}{2}\biggl( \frac{1}{8} +\frac{3}{8}p + \frac{3}{8}p^2 + \frac{1}{8}p^3\biggr).$$ $1$ is the only common root of the two polynomials.

Answer 4

If we let $p$ be the probability that the algorithm stops, then note that at step 1 (i.e., after one iteration), then half the time it has stopped; and half the time it has three new nodes; in which case the original node stops if and only if all three subnodes stop.

In the latter case, the chance that that all three subnodes will stop is $p^3$; so we can write:

$$p = 1/2 + 1/2(p^3)$$ $$2p = 1 + p^3$$ $$p^3 - 2p + 1 = 0$$

This gives a value of $p \approx 0.61803...$ (I'm too lazy to solve the cubic right now!).

EDIT: This is not enough; I forgot that $p=1$ is also a root.

Here's another approach: let $p_n$ be the probability that the algorithm stops at or before step $n$. Then

$$p_1 = 1/2$$ $$p_2 = 1/2 + 1/2(p_1)^3$$

and more generally,

$$p_n = 1/2 + 1/2(p_{n-1}^3)$$

As $n \rightarrow \infty$, the sequence $\{p_n\}$ converges from below to the root $\frac{\sqrt{5}-1}{2}$ (well, this seems obvious by simulation, but I don't quite have a proof yet.)

Answer 5

While I believe that Chas Brown has essentially given the correct answer plus an intuitive derivation, I just want to point out that you can link this question to a standard result about Galton-Watson branching processes. A Galton-Watson branching process is a discrete-time stochastic process describing the evolution of a population and it is characterized by a so-called offspring distribution. Basically you start with one individual which gives birth to a random number of children. Each of those children (if there are any) gives birth to a random number of children, independently of the others, and so on.

Let $g(s)$ denote the probability generating function of this distribution, i.e., in your example $g(s) = (s^3+1)/2$. Then, we have the following. If there is a positive chance of having zero offsprings, and the expected number of offsprings is greater than one, then the probability of extinction (or in your case, the probability that the algorithm halts), is the unique fixed point of $g(a) = a$ over $0 < a < 1$.