3
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ en.wikipedia.org/wiki/Birth%E2%80%93death_process $\endgroup$ Commented Nov 28, 2014 at 22:30
  • $\begingroup$ I just realized that my problem can be reformulated as the following. You begin with the state $n=1$ and have a process that either decrements $n$ by 1 or increments it by 2, with equal probability. While this is not exactly the birth-death process as you've linked since it only allows incrementing $n$ by 1, it is similar to the case where the birth probability is twice as likely as the death case. This interpretation doesn't solve the problem directly, but it makes it easier to search for answers for similar problems. $\endgroup$
    – Vortico
    Commented Nov 28, 2014 at 23:06
  • $\begingroup$ I wonder, is there a method in terms of the birth-death problem documented somewhere that handles this case exactly? $\endgroup$
    – Vortico
    Commented Nov 28, 2014 at 23:07
  • $\begingroup$ Maybe this like is better: en.wikipedia.org/wiki/Galton%E2%80%93Watson_process $\endgroup$ Commented Nov 28, 2014 at 23:20

5 Answers 5

5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ $p=1$ also solves it, as in @Leo163's answer. $\endgroup$
    – Vortico
    Commented Nov 28, 2014 at 21:37
  • $\begingroup$ Yes, you are right! $\endgroup$
    – Chas Brown
    Commented Nov 28, 2014 at 21:41
4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ So the probability is actually the fixed point $a = \frac{\sqrt{5}-1}{2}$, since it is on $(0, 1)$? I'll read into Galton-Watson processes, thanks! $\endgroup$
    – Vortico
    Commented Nov 28, 2014 at 23:40
  • $\begingroup$ Yes, that is correct. $\endgroup$
    – TriSSSe
    Commented Nov 29, 2014 at 0:09
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ "First, observe $p_n$ are increasing..." is the key observation - it's not just any sequence. An increasing sequence implies $p_n <= \phi - 1$. $\endgroup$
    – Chas Brown
    Commented Nov 29, 2014 at 3:57
1
$\begingroup$

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.

$\endgroup$
16
  • 1
    $\begingroup$ The answer seems correct, but I don't believe the stopping probability on the $n$th step. Can you explain the reasoning behind it? $\endgroup$
    – Vortico
    Commented Nov 28, 2014 at 20:31
  • $\begingroup$ I have expanded the answer to your request, if I understood the problem correctly. Hope it helps. $\endgroup$
    – carlosayam
    Commented Nov 28, 2014 at 21:28
  • 1
    $\begingroup$ I'm not sure your argument matches the following interpretation of the problem : at each step, there are only 2 choices, each occurring at probability 1/2 : we stop, or we create 3 nodes. So there are two outcomes per newly created nodes. $\endgroup$ Commented Nov 28, 2014 at 21:42
  • $\begingroup$ Hum, it does not, I understood that 3 new nodes and no node were all equiprobable, not as you say. But the outcome is the same, $(1/2) \frac{1}{1-(1/2)}$ = 1. $\endgroup$
    – carlosayam
    Commented Nov 28, 2014 at 21:48
  • 1
    $\begingroup$ I also don't think this matches the problem since each iteration should create "either three subvertices or none". However, this seems like a good general method if it could be repaired, but I've been working out the probability for halting on the $n$th step and keep getting expressions which grow exponentially in complexity for each iteration. $\endgroup$
    – Vortico
    Commented Nov 28, 2014 at 21:52
0
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ There are actually two real roots between $[0, 1]$: 1 and $\frac{\sqrt{5}-1}{2}$. $\endgroup$
    – Vortico
    Commented Nov 28, 2014 at 20:30
  • $\begingroup$ You're right. I hope it works now. I'm sorry. $\endgroup$
    – Leo163
    Commented Nov 28, 2014 at 20:54
  • $\begingroup$ So in the second expression, $p = 1/2 + 1/2 ((1/2 + 1/2p)^3)$. Can you explain why ? $\endgroup$ Commented Nov 28, 2014 at 21:10
  • $\begingroup$ If this works, it is the most elegant method, but I'm also having trouble seeing how you approached the second expression. $\endgroup$
    – Vortico
    Commented Nov 28, 2014 at 21:55
  • $\begingroup$ It should be the same way of reasoning applied to the first step. $\endgroup$
    – Leo163
    Commented Nov 28, 2014 at 22:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .