¿Cuál es la posibilidad de que este código termine?

10

Escribí este código de Python y me pregunté si a veces simplemente no termina (suponiendo que tengamos memoria / tiempo infinito y ningún límite de profundidad de recursión).

Intuitivamente pensarías que termina, ya que en algún momento debes tener suerte , y si no termina tienes una cantidad infinita de tiempo para tener suerte. Por otro lado, a medida que aumenta la profundidad de recursión, debes ser exponencialmente más afortunado.

import random

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

Si random_treeno siempre termina, ¿por qué y cuál es la probabilidad de que termine?

He intentado calcularlo usando , que en su inutilidad terrible da la respuesta ~ 0.684124 o ... 1 .P=1(10.5)(1(P+P2+P3+P4+P5)/5)0.6841241

Probablemente más complicado, pero también intrigante para mí, ¿cuál es la posibilidad de terminación 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))]

O en seudocó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
orlp
fuente
1
@DavidRicherby Agregado en la parte inferior. El código en la parte superior es simplemente random_tree(0.5, 5).
orlp
Esto se conoce como un proceso de ramificación. Búscalo para encontrar la respuesta.
Yuval Filmus

Respuestas:

8

1.25>1

Yuval Filmus
fuente
1
Entonces resulta. Esta raíz expresa el hecho de que si nunca comienzas, el proceso se extingue. Le sugiero que lea un poco sobre este tema clásico, que es tratado, por ejemplo, por Feller.
Yuval Filmus