Prawdopodobieństwo warunkowe i algorytm, który zadziwi Twoją panią od polskiego

15.06.2010 - Krzysztof Dryś

Zabawa wzorami dla ekspertów

Teraz zabierzemy się za drugą część. Na początek utrudnijmy sobie zadanie. Załóżmy, że Jaś rzucał monetą $T$ razy i uzyskał wyniki $x_1, x_2 \ldots x_T$ . 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 $2^T$ (mamy $T$ 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 $k$ monet zamiast dwóch. Dane wejściowe tego algorytmu to:

Tablica w[i][k], mówiąca, jakie jest prawdopodobieństwo wrzucenia $k \in \{ \mbox{orzeł, reszka} \}$ monetą $i$ : $w[i][k] = P( \mbox{ Jaś wyrzuci k} | \mbox{ Jaś rzuca monetą i} )$ ,
Tablica p[i][j], mówiąca, jakie jest prawdopodobieństwo tego, że Jaś w następnej turze będzie rzucał monetą $j$ , jeżeli w tej turze rzuca monetą $j$ .

Nasz algorytm będzie tworzył dwie tablice. Pierwsza z nich, $L[i][n]$ będzie przechowywała najbardziej prawdopodobny ciąg monet $m_1 \ldots m_n$ kończący się monetą $i$ (to znaczy $m_n = i$ ). Innymi słowy, chodzi o ciąg, który maksymalizuje prawdopodobieństwo $P( \mbox{Jaś użył monet } m_1 \ldots m_n = i \mbox{| Jaś wyrzucił } x_1 \ldots x_n)$ .

Teraz zobaczymy coś ciekawego. Z właściwości prawdopodobieństwa warunkowego wiemy, że:

$P( \mbox{Jaś użył monet } m_1 \ldots m_n |\mbox{ Jaś wyrzucił } x_1 \ldots x_n)$

jest równe:

${ P( \mbox{Jaś użył monet } m_1 \ldots m_n \mbox{oraz Jaś wyrzucił } x_1 \ldots x_n) \over P(\mbox{Jaś wyrzucił } x_1 \ldots x_n)$

Zauważmy, że mianownik $P(\mbox{Jaś wyrzucił } x_1 \ldots x_n)$ jest niezależny od ciągu monet. To oznacza, że ciąg monet, który maksymalizuje $P( \mbox{Jaś użył monet } m_1 \ldots m_n \mbox{| Jaś wyrzucił } x_1 \ldots x_n)$ , maksymalizuje również $P( \mbox{Jaś użył monet } m_1 \ldots m_n \mbox{oraz Jaś wyrzucił } x_1 \ldots x_n)$ .

To drugie wyrażenie okaże się łatwiejsze do wyliczenie i dlatego w tablicy $Q[j][n]$ będziemy przechowywali właśnie $P( \mbox{Jaś użył monet } m_1 \ldots m_n \mbox{oraz Jaś wyrzucił } x_1 \ldots x_n)$ , gdzie $m_1 \ldots m_n$ jest ciągiem monet, który trzymamy w tablicy $W[j][n]$ . Czyli maksymalizującym zarówno $P( \mbox{Jaś użył monet } m_1 \ldots m_n |\mbox{ Jaś wyrzucił } x_1 \ldots x_n)$ jak i $P( \mbox{Jaś użył monet } m_1 \ldots m_n \mbox{oraz Jaś wyrzucił } x_1 \ldots x_n)$ .

Jeżeli uda nam się wyznaczyć wartości w tablicach $Q[j][n]$ i $W[j][n]$ dla wszystkich wszystkich monet (a więc dla każdego $j$ ) oraz dla $n=T$ (liczba wszystkich rzutów monetą), to nasze zadanie będzie skończone. Wystarczy wybrać to $j$ dla którego $Q[j][T]$ jest największe i zwrócić $W[j][T]$ jako wynik. Pozostaje pytanie, jak wyznaczyć tablice Q i W?

Żeby to zrobić znowu trochę się pobawimy wzorami:

$\begin{array}{rcl} P( \mbox{Jaś użył monet } m_1 \ldots m_{n+1} \mbox{ oraz Jaś wyrzucił } x_1 \ldots x_{n+1}) & & = \\ P( \mbox{Jaś użył monet } m_1 \ldots m_n \mbox{oraz Jaś wyrzucił } x_1 \ldots x_{n} ) & \times & \\ P( \mbox{Jaś użył w (n+1)-wszym rzucie monety } m_{n+1} | \mbox{ Jaś użył w n-tym rzucie monety } m_n) & \times & \\ P( \mbox{Ja wyrzucił } x_{n+1} \mbox{ na monecie } m_{n+1} ) & & = \\ P( \mbox{Jaś użył monet } m_1 \ldots m_n \mbox{oraz Jaś wyrzucił } x_1 \ldots x_{n} ) \cdot p[m_n][m_{n+1}] \cdot w[x_{n+1}][m_{n+1}] & & \\ \end{array}$

Załóżmy, że chcemy policzyć Q[j][n+1]. Ta wartość jest zdefiniowa jako maksimum z $P( \mbox{Jaś użył monet } m_1 \ldots m_{n+1} = j \mbox{ oraz Jaś wyrzucił } x_1 \ldots x_{n+1})$ po wszystkich ciągach $m_1 \ldots m_n$ . Przed chwilą pokazaliśmy, że jest to równe maksimum z $P( \mbox{Jaś użył monet } m_1 \ldots m_n \mbox{oraz Jaś wyrzucił } x_1 \ldots x_{n} ) \cdot p[m_n][m_{n+1}] \cdot w[x_{n+1}][m_{n+1}]$ po wszystkich ciągach $m_1 \ldots m_n$ . Zauważmy, że:

$w[x_{n+1}][m_{n+1}] = P( \mbox{Ja wyrzucił } x_{n+1} \mbox{ na monecie } m_{n+1} )$ zależy tylko od j
$p[m_n][m_{n+1}] = %P( \mbox{Jaś użył w (n+1)-wszym rzucie monety } m_{n+1} \mbox{ | Jaś użył w n-tym rzucie monety } m_n)$ zależy tylko od $m_n$ i $j$
$$P( \mbox{Jaś użył monet } m_1 \ldots m_n \mbox{oraz Jaś wyrzucił } x_1 \ldots x_{n} )$ nie zależy od $j$ . Maksimum tego wyrażenia po $m_1 \ldots m_{n-1}$ wynosi $Q[m_{n}][n]$

Te trzy uwagi pozwalają nam zapisać $Q[j][n+1]$ w nowy sposób. Otóż jest to maksimum z $Q[m_n][n] \cdot p[m_n][m_{n+1}] \cdot w[x_{n+1}][m_{n+1}]$ po wszystkich możliwych monetach $w_n$ .