10
$\begingroup$

I wrote this Python code, and wondered if it sometimes simply doesn't terminate (assuming we had infinite memory/time and no recursion depth limit).

Intuitively you'd think it terminates, since at some point you must get lucky, and if it doesn't terminate you have an infinite amount of time to get lucky. On the other hand, as the recursion depth increases you must become exponentially more lucky.

import random

def random_tree():
    if random.random() < 0.5:
        return 0
    return [random_tree() for _ in range(random.randint(1, 5))]

If random_tree doesn't always terminate, why, and what is the chance that it does terminate?

I've tried to calculate it using $P = 1 - (1 - 0.5)(1 - (P + P^2 + P^3 + P^4 + P^5)/5)$, which in it's terrific uselessness either gives the answer ~$0.684124$ or... $1$.

Probably more complicated, but also intriguing to me, what is the termination chance $P(a, b)$ for:

def random_tree(a, b):
    if random.random() < a:
        return 0
    return [random_tree(a, b) for _ in range(random.randint(1, b))]

Or in pseudo-code:

random_tree(a, b) is a function that either:
    - returns 0 with probability a
    - returns a list containing the results of 1 to b
      (uniformly chosen from this inclusive range) recursive calls

random_tree(a, b):
    if rand() < a # rand() is a random real on [0, 1)
        return 0
    list = []
    len = randint(1, b) # uniform random integer from 1 to b inclusive
    do len times
        append random_tree(a, b) to list
    return list
$\endgroup$
  • 1
    $\begingroup$ @DavidRicherby Added in the bottom. The code at the top is simply random_tree(0.5, 5). $\endgroup$ – orlp Mar 29 '16 at 2:22
  • $\begingroup$ This is known as a branching process. Look it up to find the answer. $\endgroup$ – Yuval Filmus Mar 29 '16 at 6:07
8
$\begingroup$

This is an example of a branching process. The behavior of a branching process depends on the expected number of children, which in your case is $1.25 > 1$. When this number is at most 1, the process gets extinct with probability 1. When the number is more than 1, it has a chance of surviving forever; the extinction probability is just what you calculated — you need to select the root which is smaller than 1.

$\endgroup$
  • $\begingroup$ Why is the root of $1$ invalid? $\endgroup$ – orlp Mar 29 '16 at 15:42
  • $\begingroup$ So it turns out. This root expresses the fact that if you never start then the process gets extinct. I suggest you do some reading on this classical topic, which is treated for example by Feller. $\endgroup$ – Yuval Filmus Mar 29 '16 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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