Jaka jest szansa, że ​​ten kod się zakończy?

10

Napisałem ten kod w Pythonie i zastanawiałem się, czy czasami po prostu się nie kończy (zakładając, że mamy nieskończoną pamięć / czas i nie ma ograniczenia głębokości rekurencji).

Intuicyjnie myślisz, że kończy się, ponieważ w pewnym momencie musisz mieć szczęście , a jeśli się nie skończy, masz nieskończoną ilość czasu na szczęście. Z drugiej strony, wraz ze wzrostem głębokości rekurencji, musisz mieć wykładniczo więcej szczęścia.

import random

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

Jeśli random_treenie zawsze się kończy, dlaczego i jaka jest szansa, że ​​się zakończy?

P=1(10.5)(1(P+P2+P3+P4+P5)/5)0.6841241

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

Lub w pseudokodzie:

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
źródło
1
@DavidRicherby Dodano na dole. Kod u góry jest po prostu random_tree(0.5, 5).
orlp
Jest to znane jako proces rozgałęziania. Sprawdź, aby znaleźć odpowiedź.
Yuval Filmus

Odpowiedzi:

8

1.25>1

Yuval Filmus
źródło
1
Okazuje się. Ten rdzeń wyraża fakt, że jeśli nigdy nie zaczniesz, proces wyginie. Sugeruję, abyś poczytał trochę na ten klasyczny temat, który jest traktowany na przykład przez Fellera.
Yuval Filmus