Qual é a chance de esse código terminar?

Eu escrevi esse código Python e me perguntei se às vezes simplesmente não terminava (supondo que tivéssemos memória / tempo infinitos e nenhum limite de profundidade de recursão).

Intuitivamente, você acha que termina, já que em algum momento você deve ter sorte e, se não terminar, terá um tempo infinito para ter sorte. Por outro lado, à medida que a profundidade da recursão aumenta, você deve se tornar exponencialmente mais sortudo.

import random

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

Se random_treenem sempre termina, por que e qual a chance de terminar?

Eu tentei calculá-lo usando , o que, em sua incrível inutilidade, dá a resposta ~ ou ... .0,684124 $P = 1 - (1 - 0.5)(1 - (P + P^2 + P^3 + P^4 + P^5)/5)$$0.684124$$1$

Provavelmente mais complicado, mas também intrigante para mim, qual é a chance de rescisão para:$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 no pseudo-código:

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

Este é um exemplo de um processo de ramificação . O comportamento de um processo de ramificação depende do número esperado de filhos, que no seu caso é . Quando esse número é no máximo 1, o processo se extingue com probabilidade 1. Quando o número é maior que 1, ele tem chance de sobreviver para sempre; a probabilidade de extinção é exatamente o que você calculou - é necessário selecionar a raiz menor que 1.$1.25 > 1$