Wie groß ist die Wahrscheinlichkeit, dass dieser Code beendet wird?

10

Ich habe diesen Python-Code geschrieben und mich gefragt, ob er manchmal einfach nicht endet (vorausgesetzt, wir hatten unendlich viel Speicher / Zeit und keine Rekursionstiefenbegrenzung).

Intuitiv würden Sie denken, dass es endet, da Sie irgendwann Glück haben müssen , und wenn es nicht endet, haben Sie unendlich viel Zeit, um Glück zu haben. Andererseits müssen Sie mit zunehmender Rekursionstiefe exponentiell mehr Glück haben.

import random

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

Wenn random_treenicht immer beendet wird, warum und wie hoch ist die Wahrscheinlichkeit, dass es beendet wird?

Ich habe versucht, es mit zu berechnen , was in seiner schrecklichen Nutzlosigkeit entweder ergibt die Antwort ~ oder ... .P=1(10.5)(1(P+P2+P3+P4+P5)/5)0.6841241

Wahrscheinlich komplizierter, aber auch faszinierend für mich, was ist die Kündigungsmöglichkeit für: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))]

Oder im Pseudocode:

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
quelle
1
@ DavidRicherby Unten hinzugefügt. Der Code oben ist einfach random_tree(0.5, 5).
Orlp
Dies ist als Verzweigungsprozess bekannt. Schlagen Sie nach, um die Antwort zu finden.
Yuval Filmus

Antworten:

8

Dies ist ein Beispiel für einen Verzweigungsprozess . Das Verhalten eines Verzweigungsprozesses hängt von der erwarteten Anzahl von Kindern ab, die in Ihrem Fall beträgt . Wenn diese Zahl höchstens 1 ist, erlischt der Prozess mit Wahrscheinlichkeit 1. Wenn die Zahl größer als 1 ist, hat er eine Chance, für immer zu überleben. Die Extinktionswahrscheinlichkeit ist genau das, was Sie berechnet haben - Sie müssen die Wurzel auswählen, die kleiner als 1 ist.1.25>1

Yuval Filmus
quelle
Warum ist die Wurzel von ungültig? 1
Orlp
So stellt sich heraus. Diese Wurzel drückt die Tatsache aus, dass der Prozess ausgestorben ist, wenn Sie nie starten. Ich schlage vor, Sie lesen etwas über dieses klassische Thema, das zum Beispiel von Feller behandelt wird.
Yuval Filmus