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