Macierz stochastyczna - Stochastic matrix

W matematyce macierz stochastyczna jest macierzą kwadratową używaną do opisu przejść w łańcuchu Markowa . Każdy z jego wpisów jest nieujemną liczbą rzeczywistą reprezentującą prawdopodobieństwo . Nazywa się to również do macierzy prawdopodobieństwa , macierz transformacji , macierz podstawień lub Markowa matrycy . Macierz stochastyczna została po raz pierwszy opracowana przez Andreya Markowa na początku XX wieku i znalazła zastosowanie w wielu różnych dziedzinach nauki, w tym w teorii prawdopodobieństwa , statystyce, finansach matematycznych i algebrze liniowej , a także w informatyce i genetyce populacyjnej . Istnieje kilka różnych definicji i typów macierzy stochastycznych:

Prawo stochastyczny macierz jest macierzą kwadratową rzeczywistym, przy czym każdy rząd sumowania 1.

Opuścił matrycę stochastyczne jest prawdziwy kwadratowych macierzy, przy czym każda kolumna sumowania 1.

Podwójnie stochastyczny macierz jest macierzą kwadratową o nieujemne liczby rzeczywiste z każdego wiersza i kolumny zsumowanie 1.

W tym samym duchu można zdefiniować wektor stochastyczny (zwany także wektorem prawdopodobieństwa ) jako wektor, którego elementami są nieujemne liczby rzeczywiste, które sumują się do 1. Tak więc każdy wiersz prawej macierzy stochastycznej (lub kolumna lewej macierzy stochastycznej) jest wektor stochastyczny. Powszechną konwencją w anglojęzycznej literaturze matematycznej jest używanie wektorów rzędowych prawdopodobieństw i prawych macierzy stochastycznych zamiast kolumnowych wektorów prawdopodobieństw i lewych macierzy stochastycznych; ten artykuł jest zgodny z tą konwencją.

Historia

Andriej Markow w 1886 r.

Stochastyczny matryca została opracowana wzdłuż łańcucha Markowa przez Andriej Markow , a rosyjski matematyk i profesor na Uniwersytecie Petersburskim , którzy po raz pierwszy opublikowana na ten temat w 1906 roku swój początkowy zamierzonych zastosowań były do analizy językowej i innych przedmiotów matematycznych, takich jak tasowanie kart , ale zarówno Łańcuchy i matryce Markowa szybko znalazły zastosowanie w innych dziedzinach.

Macierze stochastyczne były dalej rozwijane przez uczonych, takich jak Andrey Kołmogorov , którzy rozszerzyli swoje możliwości, pozwalając na ciągłe procesy Markowa. W latach pięćdziesiątych w dziedzinie ekonometrii i teorii obwodów pojawiły się artykuły wykorzystujące macierze stochastyczne . W latach 60. macierze stochastyczne pojawiły się w jeszcze szerszej gamie prac naukowych, od nauk behawioralnych, przez geologię, po planowanie mieszkaniowe . Ponadto w ciągu tych dziesięcioleci wykonano również wiele prac matematycznych, aby poprawić zakres zastosowań i funkcjonalność macierzy stochastycznej i ogólnie procesów markowskich .

Od lat 70. do chwili obecnej macierze stochastyczne znalazły zastosowanie w prawie każdej dziedzinie wymagającej analizy formalnej, od nauk strukturalnych przez diagnostykę medyczną po zarządzanie personelem . Ponadto macierze stochastyczne znalazły szerokie zastosowanie w modelowaniu zmian gruntów , zwykle pod nazwą macierz Markowa.

Definicja i właściwości

Macierz stochastyczna opisuje łańcuch Markowa $X t$ nad skończoną przestrzenią stanów S o liczności $S$ .

Jeśli prawdopodobieństwo przejścia od $I$ do $j$ w jednym etapie czasu jest $P (J | I) = P I, J$ , stochastyczny macierz $P$ jest podany za pomocą $P ı, j$ jako $ı$ -tego wiersza i $j$ -tym elemencie kolumny , np,

{\ Displaystyle P = \ lewo [{\ zacząć {macierz} P_ {1,1} i P_ {1,2} i \ kropki i P_ {1, j} i \ kropki i P_ {1, S} \ \ P_ {2, 1}&P_{2,2}&\dots &P_{2,j}&\dots &P_{2,S}\\\vdots &\vdots &\ddots &\vdots &\ddots &\vdots \\P_{i ,1}&P_{i,2}&\dots &P_{i,j}&\dots &P_{i,S}\\\vdots &\vdots &\ddots &\vdots &\ddots &\vdots \\P_{ S,1}&P_{S,2}&\dots &P_{S,j}&\dots &P_{S,S}\\\end{matrix}}\right].}

Ponieważ całkowite prawdopodobieństwo przejścia ze stanu $i$ do wszystkich innych stanów musi wynosić 1,

{\ Displaystyle \ suma _ {j = 1} ^ {S} P_ {i, j} = 1; \,}

zatem ta macierz jest właściwą macierzą stochastyczną.

Powyższy suma elementwise przez każdy rząd $I$ z $P$ może być bardziej zwięzłego zapisać jako $P 1 = 1$ , gdzie $1$ jest $S$ -wymiarową wektor jedynkami. Korzystając z tego, można zauważyć, że iloczyn dwóch prawych macierzy stochastycznych $P'$ i $P''$ jest również prawo stochastyczny: $P' P'' 1 = P' (P'' 1) = P' 1 = 1$ . Ogólnie rzecz biorąc, $k-ta$ potęga $P k$ prawostronnej macierzy stochastycznej $P$ jest również prawostochastyczna. Prawdopodobieństwo przejścia od $i$ do $j$ w dwóch krokach jest wtedy podane przez $(i, j)$ -ty element kwadratu $P$ :

{\ Displaystyle \ lewo (P ^ {2} \ prawo) _ {i, j}.}

Ogólnie rzecz biorąc, prawdopodobieństwo przejścia z dowolnego stanu do innego stanu w skończonym łańcuchu Markowa dane przez macierz $P$ w $k$ kroków jest dane przez $P k$ .

Początkowy rozkład prawdopodobieństwa stanów, określający, gdzie system może być początkowo iz jakimi prawdopodobieństwami, jest podany jako wektor wierszowy .

Nieruchomy prawdopodobieństwo wektor $π$ jest określony jako rozkład programu, w postaci wektora rzędu, że nie zmienia się pod wpływem zastosowania macierzy transformacji; oznacza to, że jest zdefiniowany jako rozkład prawdopodobieństwa na zbiorze ${1, \dots, n},$ który jest również wierszowym wektorem własnym macierzy prawdopodobieństwa, skojarzonym z wartością własną 1:

{\boldsymbol {\pi}}p={\boldsymbol {\pi}}.

Można wykazać, że promień widmowy dowolnej macierzy stochastycznej jest jeden. Według twierdzenia Gershgorina o okręgu wszystkie wartości własne macierzy stochastycznej mają wartości bezwzględne mniejsze lub równe jeden. Dodatkowo każda prawa macierz stochastyczna ma "oczywisty" kolumnowy wektor własny powiązany z wartością własną 1: wektor $1$ , którego współrzędne są równe 1 (zauważ, że pomnożenie wiersza $A$ razy $1$ równa się sumie wpisów wiersza a zatem równa się 1). Ponieważ lewa i prawa wartości własnych macierzy kwadratowej są takie same, co stochastyczny matryca zawiera co najmniej rząd wektor własny związany z wartością własną 1 i największej wartości bezwzględnej wszystkich wartości własnych jest 1. Wreszcie Brouwer stałoprzecinkowe Twierdzenie ( zastosowane do zbioru zwartego wypukłego wszystkich rozkładów prawdopodobieństwa zbioru skończonego ${1, \dots, n}$ ) implikuje, że istnieje pewien lewy wektor własny, który jest również stacjonarnym wektorem prawdopodobieństwa.

Z drugiej strony twierdzenie Perrona-Frobeniusa zapewnia również, że każda nieredukowalna macierz stochastyczna ma taki stacjonarny wektor, a największa wartość bezwzględna wartości własnej wynosi zawsze 1. Jednak tego twierdzenia nie można zastosować bezpośrednio do takich macierzy, ponieważ wymagają one nie być nieredukowalnym.

Ogólnie może być kilka takich wektorów. Jednak dla macierzy ze ściśle dodatnimi wpisami (lub ogólniej dla nieredukowalnej aperiodycznej macierzy stochastycznej) wektor ten jest unikalny i można go obliczyć, obserwując, że dla dowolnego $i$ mamy następujące ograniczenie:

{\ Displaystyle \ lim _ {k \ rightarrow \ infty} \ lewo (P ^ {k} \ prawej) _ {i, j} = {\ pogrubienie {\ pi}} _ {j}}

gdzie $π$ $j$ jest $j$ -tym elementem wektora wierszowego $π$ . Mówi to między innymi, że długoterminowe prawdopodobieństwo przebywania w stanie $j$ jest niezależne od stanu początkowego $i$ . To, że oba te obliczenia dają ten sam wektor stacjonarny, jest formą twierdzenia ergodycznego , co generalnie jest prawdziwe w wielu różnych rozproszonych układach dynamicznych : układ ewoluuje z czasem do stanu stacjonarnego .

Intuicyjnie macierz stochastyczna reprezentuje łańcuch Markowa; zastosowanie macierzy stochastycznej do rozkładu prawdopodobieństwa powoduje redystrybucję masy prawdopodobieństwa pierwotnego rozkładu przy zachowaniu jego masy całkowitej. Jeśli ten proces jest powtarzany, dystrybucja zbiega się z dystrybucją stacjonarną dla łańcucha Markowa.

Przykład: kot i mysz

Załóżmy, że jest zegar i rząd pięciu sąsiednich pudełek, z kotem w pierwszym pudełku i myszą w piątym pudełku w czasie zero. Kot i mysz przeskakują do losowego sąsiedniego pola, gdy licznik czasu przesuwa się do przodu. Np. jeśli kot jest w drugim pudełku, a mysz w czwartym, prawdopodobieństwo, że kot będzie w pierwszym, a mysz w piątym, po przesunięciu się licznika wynosi jedną czwartą . Jeśli kot znajduje się w pierwszym pudełku, a mysz w piątym, prawdopodobieństwo jest takie, że kot będzie w drugim, a mysz w czwartym po przesunięciu się licznika. Kot zjada mysz, jeśli obie trafią do tego samego pudełka, w którym to momencie gra się kończy. Zmienną losową K daje ilość czasu kroki pobyty myszy w grze.

Łańcuchów Markowa , który reprezentuje gry zawiera pięć następujących stanów określonych przez połączenie zaworu (kot, mysz). Należy zauważyć, że chociaż naiwne wyliczenie stanów zawierałoby 25 stanów, wiele z nich jest niemożliwych albo dlatego, że mysz nigdy nie może mieć niższego indeksu niż kot (co oznaczałoby, że mysz zajęła pudełko kota i przetrwała, aby przejść obok niego), albo dlatego, że suma obu indeksów zawsze będzie miała parzystość . Ponadto 3 możliwe stany, które prowadzą do śmierci myszy, są połączone w jeden:

Stan 1: (1,3)
Stan 2: (1,5)
Stan 3: (2,4)
Stan 4: (3,5)
Stan 5: koniec gry: (2,2), (3,3) i (4,4).

Używamy macierzy stochastycznej (poniżej), aby przedstawić prawdopodobieństwa przejścia tego systemu (wiersze i kolumny w tej macierzy są indeksowane według możliwych stanów wymienionych powyżej, ze stanem przed przejściem jako wierszem i stanem po przejściu jako kolumna). Np. począwszy od stanu 1 – 1 wiersz – nie jest możliwe, aby system pozostał w tym stanie, więc ; system nie może również przejść do stanu 2 – ponieważ kot zostałby w tym samym pudełku – tak i podobnie jak mysz, . Dozwolone są przejścia do stanów 3 lub 5, a więc . $P$ ${\ Displaystyle P_ {11} = 0}$ ${\ Displaystyle P_ {12} = 0}$ ${\ Displaystyle P_ {14} = 0}$ ${\ Displaystyle P_ {13}, P_ {15} \ neq 0}$

{\ Displaystyle P = {\ zacząć {bmatrix} 0 i 0 i 1/2 i 0 i 1/2 \ \ 0 i 0 i 1 i 0 i 0 \ \ 1/4 i 1/4 i 0 i 1/4 i 1/4 \ \ 0 i 0 i 1/2 i 0 i 1/2 \ \ 0 i 0 i 0 i 0 i 1 \ koniec {bmatrix}}.}

Średnie długoterminowe

Bez względu na stan początkowy kot w końcu złapie mysz (z prawdopodobieństwem 1), a stan stacjonarny π = (0,0,0,0,1) jest traktowany jako granica. Aby obliczyć długoterminową średnią lub oczekiwaną wartość zmiennej stochastycznej , dla każdego stanu i czasu występuje udział . Przeżycie można traktować jako zmienną binarną ze stanem przetrwania i stanem zakończonym. Państwa z nie wnoszą wkładu do średniej długoterminowej. ${\ Displaystyle Y}$ $S_{j}$ $t_{k}$ ${\ Displaystyle Y_ {j, k} \ cdot P (S = S_ {j}, t = t_ {k})}$ ${\ Displaystyle Y = 1}$ ${\ Displaystyle Y = 0}$ ${\ Displaystyle Y = 0}$

Reprezentacja typu fazy

Funkcja przetrwania myszy. Mysz przetrwa przynajmniej pierwszy krok w czasie.

Ponieważ Stan 5 jest stanem absorbującym, rozkład czasu do absorpcji jest dyskretnym rozkładem fazowym . Załóżmy, że system startuje w stanie 2, reprezentowanym przez wektor . Stany, w których zginęła mysz, nie przyczyniają się do średniej przeżywalności, więc stan piąty można zignorować. Stan początkowy i macierz przejścia można sprowadzić do: ${\ Displaystyle [0,1,0,0,0]}$

{\boldsymbol {\tau}}=[0,1,0,0],\qquad T={\rozpocznij {bmatrix}0&0&{\frac{1}{2}}&0\\0&0&1&0\\{ \frac {1}{4}}&{\frac {1}{4}}&0&{\frac {1}{4}}\\0&0&{\frac {1}{2}}&0\end{bmatrix} },

oraz

{\ Displaystyle (IT) ^ {-1} {\ pogrubienie {1}} = {\ zacząć {bmatrix} 2,75 \ \ 4,5 \ \ 3,5 \ \ 2,75 \ koniec {b macierzy}}}

gdzie jest macierzą jednostkową i reprezentuje macierz kolumnową wszystkich jedynek, która działa jako suma po stanach. ${\ Displaystyle I}$ ${\ Displaystyle \ mathbf {1} }$

Ponieważ każdy stan jest zajęty przez jeden krok czasu, oczekiwany czas przeżycia myszy jest po prostu sumą prawdopodobieństwa zajętości wszystkich stanów i kroków w czasie, które przeżyły,

{\ Displaystyle E [K] = {\ boldsymbol {\ tau}} \ lewo (I + T + T ^ {2} + \ cdots \ prawej) {\ boldsymbol {1}} = {\ boldsymbol {\ tau}} (IT)^{-1}{\boldsymbol {1}}=4.5.}

Momenty wyższego rzędu są podane przez

{\ Displaystyle E [K (K-1) \ kropki (K-n + 1)] = n! {\ boldsymbol {\ tau}} (I- {T}) ^ {-n} {T} ^ {n -1}\mathbf {1} \,.}

Zobacz też

Matryca gęstości
Jądro Markowa , odpowiednik macierzy stochastycznej nad ciągłą przestrzenią stanów
Równanie różnicowe macierzowe
Modele ewolucji DNA
Nierówność Muirheada
Automat probabilistyczny

Languages

In other projects