Return to Question

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

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

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() for _ in range(random.randint(1, b))]

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