Uniformizacja (teoria prawdopodobieństwa)

W teorii prawdopodobieństwa metoda uniformizacji (znana również jako metoda Jensena lub metoda randomizacji ) jest metodą obliczania przejściowych rozwiązań skończonych łańcuchów Markowa w czasie ciągłym , poprzez aproksymację procesu łańcuchem Markowa w czasie dyskretnym . Oryginalny łańcuch jest skalowany według najszybszej szybkości przejścia γ , tak że przejścia zachodzą z tą samą szybkością w każdym stanie, stąd nazwa. Metoda jest prosta do zaprogramowania i wydajnie oblicza przybliżenie rozkładu przejściowego w pojedynczym punkcie czasu (bliskim zeru). Metoda została po raz pierwszy wprowadzona przez Winfrieda Grassmanna w 1977 roku.

Opis metody

łańcucha Markowa w czasie ciągłym z macierzą szybkości przejść Q , zunifikowany łańcuch Markowa w czasie dyskretnym ma macierz przejść prawdopodobieństwa ${\ Displaystyle P: = (p_ {ij}) _ {i ,j}}$ , który jest zdefiniowany przez

${przypadki} q_ {ij} / \ gamma &{\text{ if }}i\neq j\\1-\suma _{j\neq i}q_{ij}/\gamma &{\text{ if }}i=j\end{przypadki}}}$

z γ , parametrem jednolitej szybkości, dobranym tak, że

${\ Displaystyle \ gamma \ geq \ max _ {i} | q_ {ii} |.}$

W notacji macierzowej:

${\ Displaystyle P = ja + {\ Frac {1} {\ gamma}} Q.}$

Dla początkowego rozkładu π (0), rozkład w czasie t , π ( t ) jest obliczany przez

${\ Displaystyle \ pi (t) = \ suma _ {n = 0} ^ {\ infty} \ pi (0) P ^ {n} {\ Frac {(\ gamma t) ^ {n}} {n!} }e^{-\gamma t}.}$

Ta reprezentacja pokazuje, że łańcuch Markowa w czasie ciągłym może być opisany przez dyskretny łańcuch Markowa z macierzą przejścia P , jak zdefiniowano powyżej, gdzie występują skoki zgodnie z procesem Poissona o intensywności γt .

W praktyce szereg ten kończy się po skończonej liczbie wyrazów.

Realizacja

Pseudokod algorytmu znajduje się w dodatku A do artykułu Reibmana i Trivediego z 1988 roku. Wykorzystując równoległą wersję algorytmu, przeanalizowano łańcuchy z przestrzeniami stanów większymi niż 10 ^{7 .}

Ograniczenia

Reibman i Trivedi twierdzą, że „uniformizacja jest metodą z wyboru w przypadku typowych problemów”, chociaż zauważają, że w przypadku sztywnych problemów niektóre dostosowane algorytmy prawdopodobnie będą działać lepiej.

Linki zewnętrzne

• Implementacja Matlaba