Zabawa wzorami dla ekspertów
Teraz zabierzemy się za drugą część. Na początek utrudnijmy sobie zadanie. Załóżmy, że Jaś rzucał monetą
razy i uzyskał wyniki
.
Jaki jest najbardziej prawdopodobny ciąg monet? Najprostszym sposobem, żeby go wyznaczyć jest następujący algorytm:
1
2
3
| Dla każdego ciągu ciągu monet o długości T:
Wyznacz prawdopodobieństwo tego ciągu
Zwróć najbardziej prawdopodobny ciąg |
Domyślamy się, że policzyć prawdopodobieństwo tego, że rzucano konkretnym ciągiem monet.
Niestety, wszystkich możliwych ciągów jest
(mamy
miejsc, na każde wstawiamy jedną z dwóch monet).
I wszystkie musimy sprawdzić. To zdecydowanie za dużo. Dlatego, zaraz zobaczymy dużo szybszy algorytm.
Nasz algorytm będzie tak dobry, że poradzi sobie nawet z trudniejszym zadaniem. Mianowicie takim, w którym Jaś ma do dyspozycji
monet zamiast dwóch. Dane wejściowe tego algorytmu to:
- Tablica w[i][k], mówiąca, jakie jest prawdopodobieństwo wrzucenia
monetą
:
,
- Tablica p[i][j], mówiąca, jakie jest prawdopodobieństwo tego, że Jaś w następnej turze będzie rzucał monetą
, jeżeli w tej turze rzuca monetą
.
Nasz algorytm będzie tworzył dwie tablice. Pierwsza z nich,
będzie przechowywała najbardziej prawdopodobny ciąg monet
kończący się monetą
(to znaczy
).
Innymi słowy, chodzi o ciąg, który maksymalizuje prawdopodobieństwo
.
Teraz zobaczymy coś ciekawego. Z właściwości prawdopodobieństwa warunkowego wiemy, że:
jest równe:
Zauważmy, że mianownik

jest niezależny od ciągu monet. To oznacza, że ciąg monet, który maksymalizuje

, maksymalizuje również

.
To drugie wyrażenie okaże się łatwiejsze do wyliczenie i dlatego w tablicy
będziemy przechowywali właśnie
,
gdzie
jest ciągiem monet, który trzymamy w tablicy
. Czyli maksymalizującym zarówno
jak i
.
Jeżeli uda nam się wyznaczyć wartości w tablicach
i
dla wszystkich wszystkich monet (a więc dla każdego
) oraz dla
(liczba wszystkich rzutów monetą), to nasze zadanie będzie skończone.
Wystarczy wybrać to
dla którego
jest największe i zwrócić
jako wynik. Pozostaje pytanie, jak wyznaczyć tablice Q i W?
Żeby to zrobić znowu trochę się pobawimy wzorami:
Załóżmy, że chcemy policzyć Q[j][n+1]. Ta wartość jest zdefiniowa jako maksimum z
po wszystkich ciągach
.
Przed chwilą pokazaliśmy, że jest to równe maksimum z
po wszystkich ciągach
. Zauważmy, że:
-
zależy tylko od j
-
zależy tylko od
i
nie zależy od
. Maksimum tego wyrażenia po
wynosi
Te trzy uwagi pozwalają nam zapisać
w nowy sposób. Otóż jest to maksimum z
po wszystkich możliwych monetach
.