Quelle est la chance que ce code se termine?

J'ai écrit ce code Python et je me suis demandé s'il ne se terminait pas simplement parfois (en supposant que nous avions une mémoire / temps infinie et aucune limite de profondeur de récursivité).

Intuitivement, vous penseriez qu'il se termine, car à un moment donné, vous devez avoir de la chance , et s'il ne se termine pas, vous avez un temps infini pour avoir de la chance. D'un autre côté, à mesure que la profondeur de récursivité augmente, vous devez devenir exponentiellement plus chanceux.

import random

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

Si random_treene se termine pas toujours, pourquoi et quelles sont les chances qu'il se termine?

J'ai essayé de le calculer en utilisant , ce qui, dans son formidable inutilité, donne la réponse ~ 0,684124 ou ... 1 .$P = 1 - (1 - 0.5)(1 - (P + P^2 + P^3 + P^4 + P^5)/5)$$0.684124$$1$

Probablement plus compliqué, mais aussi intrigant pour moi, quelle est la chance de terminaison pour:$P(a, b)$

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

Ou en 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

$1.25 > 1$