Ich habe einen Fibonaci-Baum Fn der zu den Knoten Fn-1 und Fn-2 mit der Wahrscheinlichkeit p = 1/2 fĂŒhrt (zufĂ€llige Auswahl des Wegs). Es sind auĂerdem F1 und F0 BlĂ€tter. Ich soll zeigen, dass die Wahrscheinlichkeit, vom Wurzelknoten Fn zu einem F1 Blatt zu kommen,
2/3 * (1 - (-1/2)^n)
entspricht.
Ich bin hier recht ĂŒberfragt, wie man auf so eine Lösung kommt. Ich kann nur fĂŒr einfache FĂ€lle wie n = 3 meinen eigenen Lösungsweg manuell aufzeigen:
Bei F3 gibt es einen Teilbaum F2 und F1. F1 ist schonmal mit der Wahrscheinlichkeit p = 1/2 erreichbar. um von F3 ĂŒber F2 auf F1 zu kommen, muss ich zwei mal mit der Wahrscheinlichkeit 1/2 "den Weg entlanglaufen". Somit ergibt sich fĂŒr F3 also die Gesamtwahrscheinlichkeit
1/2 + (1/2)^2 = 3/4
Zur Selbstkontrolle mit der gegebenen Formel:
2/3 * (1 - (-1/2)^3) = 2/3 * 9/8 = 18/24 = 3/4
Hat jemand einen Tipp wie ich das angehen sollte?