Drzewko probabilistyczne

Wyobraź sobie rozgałęziający się korytarz. Przy każdym rozwidleniu wybierasz jedną możliwość, a na końcu ścieżki znajduje się pełny wynik doświadczenia. Drzewko probabilistyczne działa dokładnie tak samo: pokazuje wszystkie kolejne etapy i ich prawdopodobieństwa.

Konkret: gałęzie jako możliwe drogi

• Początek drzewka oznacza start doświadczenia.
• Każda gałąź oznacza jeden możliwy wynik danego etapu.
• Przy gałęzi zapisujemy prawdopodobieństwo przejścia tą drogą.
• Końcowa ścieżka opisuje pełny wynik, na przykład czerwona kula, a potem niebieska.

Reprezentacja: jak czytać drzewko

• Prawdopodobieństwa wychodzące z jednego węzła powinny sumować się do 1.
• Prawdopodobieństwo całej ścieżki obliczamy przez mnożenie wartości na jej gałęziach.
• Jeśli zdarzeniu sprzyja kilka ścieżek, dodajemy ich prawdopodobieństwa.
• Przy losowaniu bez zwracania wartości na drugim poziomie mogą być inne niż na pierwszym.

Abstrakcja: mnożenie po ścieżce, dodawanie między ścieżkami

Najważniejsza zasada brzmi:

Wzdłuż jednej ścieżki mnożymy, a między różnymi ścieżkami prowadzącymi do tego samego zdarzenia dodajemy.

Dla ścieżki A→B zapisujemy:

P(A i B)=P(A)·P(B po A)

Jeśli zdarzenie może zajść ścieżką A→B albo C→D, to:

P=(P(A)·P(B po A))+(P(C)·P(D po C))

FAJNY TRIK EDUKACYJNY

Zapamiętaj akronim G-A-Ł-Ą-Z-K-A: Generuj etapy, Anotuj prawdopodobieństwa, Łącz wyniki w ścieżki, Ąż do końca prowadź każdą drogę, Zlicz iloczyny, Kumuluj sprzyjające ścieżki, Analizuj sumę. W pałacu pamięci gigantyczne drzewo wyrasta z podłogi. Na każdej gałęzi siedzi liczba, która przy dotknięciu mnoży się z kolejną. Na końcach gałęzi wiszą świecące wyniki, a te sprzyjające wpadają do jednego koszyka i się dodają.

Przykład krok po kroku: dwa rzuty monetą

Rzucamy monetą dwa razy. Oblicz prawdopodobieństwo otrzymania dokładnie jednego orła.

• Krok 1: z początku wychodzą gałęzie O i R, każda z prawdopodobieństwem 1/2.
• Krok 2: z każdej gałęzi ponownie wychodzą O i R, również po 1/2.
• Krok 3: dokładnie jeden orzeł występuje na ścieżkach O→R oraz R→O.
• Krok 4: każda ścieżka ma prawdopodobieństwo 1/2·1/2=1/4.
• Krok 5: P=1/4+1/4=1/2.

Przykład krok po kroku: kule bez zwracania

W urnie są 2 kule czerwone i 1 niebieska. Losujemy dwie bez zwracania. Oblicz prawdopodobieństwo wylosowania dwóch kul różnych kolorów.

• Krok 1: pierwsza czerwona ma prawdopodobieństwo 2/3, a niebieska 1/3.
• Krok 2: po czerwonej zostaje 1 czerwona i 1 niebieska, więc P(N po C)=1/2.
• Krok 3: po niebieskiej zostają tylko 2 czerwone, więc P(C po N)=1.
• Krok 4: ścieżka C→N ma prawdopodobieństwo 2/3·1/2=1/3.
• Krok 5: ścieżka N→C ma prawdopodobieństwo 1/3·1=1/3.
• Krok 6: P(różne kolory)=1/3+1/3=2/3.

Przykład krok po kroku: zdarzenie przeciwne

Rzucamy monetą trzy razy. Jakie jest prawdopodobieństwo, że przynajmniej raz wypadnie orzeł?

• Krok 1: łatwiej policzyć zdarzenie przeciwne, czyli brak orła.
• Krok 2: brak orła oznacza ścieżkę R→R→R.
• Krok 3: P(RRR)=1/2·1/2·1/2=1/8.
• Krok 4: P(przynajmniej jeden orzeł)=1−1/8=7/8.

Najczęstsze błędy

• Dodawanie prawdopodobieństw wzdłuż jednej ścieżki zamiast ich mnożenia.
• Mnożenie prawdopodobieństw różnych ścieżek zamiast ich dodawania.
• Niezmienianie prawdopodobieństw po losowaniu bez zwracania.
• Pomijanie jednej z możliwych gałęzi.
• Brak kontroli, czy gałęzie wychodzące z jednego punktu sumują się do 1.

Kontrola wyniku

• Sprawdź, czy suma prawdopodobieństw gałęzi przy każdym węźle wynosi 1.
• Policz wszystkie końcowe ścieżki i upewnij się, że żadnej nie brakuje.
• Suma prawdopodobieństw wszystkich końcowych ścieżek powinna wynosić 1.
• Każdy wynik końcowy musi mieścić się w przedziale od 0 do 1.
• Przy losowaniu bez zwracania sprawdź, czy liczba obiektów na kolejnych etapach maleje.

Najczęstsze pytania