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

15.06.2010 - Krzysztof Dryś
TrudnośćTrudnośćTrudność

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 $.

5
Twoja ocena: Brak Ocena: 5 (1 ocena)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com