Macierz stochastyczna

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 . Nazywana jest również macierzą prawdopodobieństwa , macierzą przejścia , macierzą podstawienia lub macierzą Markowa . Macierz stochastyczna została po raz pierwszy opracowana przez Andrieja Markowa na początku XX wieku i znalazła zastosowanie w wielu różnych dziedzinach nauki, w tym teoria prawdopodobieństwa , statystyka, finanse matematyczne i algebra liniowa , a także informatyka i genetyka populacji . Istnieje kilka różnych definicji i typów macierzy stochastycznych:

Prawa macierz stochastyczna to rzeczywista macierz kwadratowa, w której każdy wiersz sumuje się do 1.

Lewa macierz stochastyczna to rzeczywista macierz kwadratowa, w której każda kolumna sumuje się do 1.

Macierz podwójnie stochastyczna to kwadratowa macierz nieujemnych liczb rzeczywistych z każdym wierszem i sumowanie kolumn do 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. Zatem każdy wiersz prawej macierzy stochastycznej (lub kolumny 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 wektorów kolumnowych prawdopodobieństw i lewych macierzy stochastycznych; ten artykuł jest zgodny z tą konwencją. Dodatkowo macierz substochastyczna jest rzeczywistą macierzą kwadratową, której wszystkie sumy wierszy wynoszą ${\ Displaystyle \ leq 1.}$

Historia

Andrieja Markowa w 1886 r

Macierz stochastyczna została opracowana wraz z łańcuchem Markowa przez Andrieja Markowa , rosyjskiego matematyka i profesora Uniwersytetu w Petersburgu, który po raz pierwszy opublikował na ten temat w 1906 roku. Jego początkowe zamierzenia dotyczyły analizy lingwistycznej i innych zagadnień matematycznych, takich jak tasowanie kart , ale zarówno Łańcuchy i macierze Markowa szybko znalazły zastosowanie w innych dziedzinach.

Macierze stochastyczne były dalej rozwijane przez uczonych, takich jak Andriej Kołmogorow , który rozszerzył ich możliwości, dopuszczając procesy Markowa w czasie ciągłym. W latach pięćdziesiątych XX wieku w dziedzinie ekonometrii i teorii obwodów pojawiły się artykuły wykorzystujące macierze stochastyczne . W latach sześćdziesiątych 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 bardziej ogólnie procesów Markowa .

Od lat 70. XX wieku 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 terminem macierz Markowa.

Definicja i właściwości

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

Jeżeli prawdopodobieństwo przejścia od $i$ do $j$ w jednym kroku czasowym wynosi $Pr(j | i) = P i, j$ , to macierz stochastyczna $P$ jest dana przy użyciu $P i, j$ jako elementu $i$ -tego rzędu i $j$ -tej kolumny , np,

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

Ponieważ suma prawdopodobieństwa przejścia ze stanu $i$ do wszystkich innych stanów musi wynosić 1,

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

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

Powyższą sumę elementarną w każdym wierszu $i P1 = 1$ $zbioru$ P $można$ bardziej zwięźle zapisać jako , gdzie $1$ jest $α$ -wymiarowym wektorem kolumnowym wszystkich jedynek. Korzystając z tego, można zauważyć, że iloczyn dwóch prawych macierzy stochastycznych $P'$ i $P''$ jest również prawostochastyczny: $P' P'' 1 = P' (P'' 1) = P' 1 = 1$ . Ogólnie rzecz biorąc, $Pk k$ $-$ ta potęga prawej stochastycznej macierzy $P$ jest również prawostochastyczna. Prawdopodobieństwo przejścia z $i$ do $j$ w dwóch krokach jest wtedy dane 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$ krokach, jest określone przez $P k$ .

Początkowy rozkład prawdopodobieństwa stanów, określający, gdzie układ może się początkowo znajdować iz jakim prawdopodobieństwem, jest podawany jako wektor wierszowy .

Stacjonarny wektor prawdopodobieństwa $π$ definiuje się jako rozkład, zapisany jako wektor wierszowy, który nie zmienia się pod wpływem zastosowania macierzy przejść ; to znaczy jest zdefiniowany jako rozkład prawdopodobieństwa na zbiorze ${1, \dots, n}$ , który jest również wierszowym wektorem własnym macierzy prawdopodobieństwa, powiązanym z wartością własną 1:

{\ Displaystyle {\ boldsymbol {\ pi}} P = {\ boldsymbol {\ pi}}.}

Można wykazać, że promień widmowy dowolnej macierzy stochastycznej wynosi jeden. Zgodnie z twierdzeniem Gershgorina o okręgu wszystkie wartości własne macierzy stochastycznej mają wartości bezwzględne mniejsze lub równe jeden. Dodatkowo, każda prawostronna macierz stochastyczna ma „oczywisty” kolumnowy wektor własny powiązany z wartością własną 1: wektor $1$ , którego wszystkie współrzędne są równe 1 (wystarczy zauważyć, że pomnożenie wiersza $A$ razy $1$ jest równa sumie wpisów w wierszu, a zatem równa się 1). Ponieważ lewe i prawe wartości własne macierzy kwadratowej są takie same, każda macierz stochastyczna ma co najmniej wierszowy wektor własny powiązany z wartością własną 1, a największa wartość bezwzględna wszystkich jej wartości własnych również wynosi 1. Wreszcie twierdzenie Brouwera o punkcie stałym ( zastosowany do zwartego wypukłego zbioru wszystkich rozkładów prawdopodobieństwa skończonego zbioru ${1, \dots, n}$ ) implikuje, że istnieje jakiś 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 i że największa wartość bezwzględna wartości własnej wynosi zawsze 1. Twierdzenia tego nie można jednak zastosować bezpośrednio do takich macierzy, ponieważ potrzebują nie być nieredukowalny.

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

{\ Displaystyle \ lim _ {k \ rightarrow \ infty} \ lewo (P ^ {k} \ prawo) _ {i, j} = {\ pogrubiony symbol { \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 , które jest generalnie prawdziwe w szerokiej gamie dyssypatywnych układów dynamicznych : system ewoluuje z czasem do stanu stacjonarnego .

Intuicyjnie macierz stochastyczna reprezentuje łańcuch Markowa; zastosowanie macierzy stochastycznej do rozkładu prawdopodobieństwa redystrybuuje masę prawdopodobieństwa pierwotnego rozkładu, zachowując jednocześnie jego całkowitą masę. Jeśli ten proces jest stosowany wielokrotnie, rozkład zbiega się do rozkładu stacjonarnego dla łańcucha Markowa.

Przykład: kot i mysz

Załóżmy, że istnieje licznik czasu i rząd pięciu sąsiednich pól. W czasie zero kot jest w pierwszym pudełku, a mysz w piątym pudełku. Kot i mysz przeskakują do losowego sąsiedniego pudełka, gdy czas mija. Np. jeśli kot jest w drugim pudełku, a mysz w czwartym, prawdopodobieństwo, że kot będzie w pierwszym pudełku , a mysz w piątym, po upływie czasu wynosi jedną czwartą. Jeśli kot jest w pierwszym pudełku, a mysz w piątym, prawdopodobieństwo, że kot będzie w pudełku drugim, a mysz w pudełku czwartym po upływie czasu jest jeden. Kot zjada mysz, jeśli oba trafią do tego samego pudełka, w którym to momencie gra się kończy. Niech zmienną losową K będzie czas, przez jaki mysz pozostaje w grze.

Łańcuch Markowa reprezentujący tę grę zawiera pięć następujących stanów określonych przez kombinację pozycji (kot, mysz). Zauważ, że chociaż naiwne wyliczenie stanów obejmowałoby 25 stanów, wiele z nich jest niemożliwych, ponieważ mysz nigdy nie może mieć niższego indeksu niż kot (ponieważ oznaczałoby to, że mysz zajmowała pudełko kota i przeżyła, aby przejść obok niego), lub dlatego, że suma dwóch 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 przez możliwe stany powyżej, ze stanem przed przejściem jako wiersz i P {\ displaystyle P} stan po przejściu jako kolumna). Na przykład, zaczynając od stanu 1 - 1. rząd - system nie może pozostać w tym stanie, więc ${\ displaystyle P_ {11} = 0}$ ; system również nie może przejść do stanu 2 – ponieważ kot zostałby w tym samym pudełku – więc ${\ displaystyle P_ {12} = 0}$ i przez podobny argument dla myszy ${\ displaystyle P_ {14} = 0}$ . Przejścia do stanów 3 lub 5 są dozwolone, a zatem ${\ Displaystyle P_ {13}, P_ {15} \ neq 0}$ .

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

Średnie długoterminowe

Bez względu na stan początkowy kot ostatecznie złapie mysz (z prawdopodobieństwem 1), a stan stacjonarny π = (0,0,0,0,1) jest traktowany jako granica. Aby $k}}$ długoterminową średnią lub oczekiwaną wartość zmiennej stochastycznej $,$ dla każdego stanu istnieje wkład $t$ z ${\ Displaystyle Y_ {j, k} \ cdot P (S = S_ {j}, t = t_ {k})}$ . $Przeżycie$ jako zmienną binarną z $i$ przetrwania zakończonym Stany z ${\ displaystyle Y = 0}$ nie mają wpływu na średnią długoterminową.

Reprezentacja typu fazowego

Funkcja przetrwania myszy. Mysz przeżyje przynajmniej pierwszy krok.

Ponieważ stan 5 jest stanem pochłaniającym, rozkład czasu do absorpcji jest dyskretny z rozkładem fazowym . Załóżmy, że system zaczyna się w stanie 2, reprezentowanym przez wektor. ${\ Displaystyle [0,1,0,0,0]}$ . Stany, w których mysz zginęła, nie mają wpływu na średnią przeżywalności, więc stan piąty można zignorować. Macierz stanu początkowego i przejścia można zredukować do:

{\ Displaystyle {\ boldsymbol {\ tau}} = [0,1,0,0] \ qquad T ={\begin{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}},}

I

{\ Displaystyle (IT) ^ {- 1} {\ boldsymbol {1}} = {\ rozpocząć {bmatrix} 2,75 \\ 4,5 \\ 3,5 \\ 2,75\end{bmacierz}},}

gdzie jest macierzą tożsamości $i$ reprezentuje macierz $kolumnową wszystkich jedynek$ działa jako suma stanów.

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

{\ Displaystyle E [K] = {\ boldsymbol {\ tau}} \ lewo (I + T + T ^ {2} + \ cdots \ prawo) {\ 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ż

Macierz gęstości
Jądro Markowa , odpowiednik macierzy stochastycznej w ciągłej przestrzeni stanów
Macierzowe równanie różnicowe
Modele ewolucji DNA
Nierówność Muirheada
Automat probabilistyczny
Macierz współczynnika przejścia , używana do uogólnienia macierzy stochastycznej na czas ciągły

Klasy macierzy
Jawnie ograniczone wpisy	Alternant antydiagonalny Antyhermitowski Antysymetryczny Grot Zespół Dwukątny Bisymetryczny Przekątna bloku Blok Blok trójprzekątny logiczne Cauchy'ego Centrosymetryczny Konferencja Złożony Hadamard kopozytywny Dominujący po przekątnej Przekątna Dyskretna transformata Fouriera Podstawowy Równowartość Frobeniusa Uogólniona permutacja Hadamarda Hankla hermitowski Hessenberga Dziurawy Liczba całkowita Logiczny Jednostka matrycy Metzlera Moore'a Nieujemne pięciokątny Permutacja Persymetryczny Wielomian czwartorzędowy Podpis Skośno-hermitowski Skośno-symetryczny Sylwetka na tle nieba Rzadki Sylwester Symetryczny Toeplitz Trójkątny Trójkątny Vandermonde'a Walsha Z
Stały	Giełda Hilberta Tożsamość Lehmera z jedynek Pascala Pauli Redheffer Zmiana Zero
Warunki dotyczące wartości własnych lub wektorów własnych	Towarzysz Zbieżny Wadliwy Określony Diagonalizowalny Hurwitza Pozytywnie określony Stieltjes
Spełniające warunki na iloczynach lub odwrotnościach	Przystający, zgodny Idempotentne lub projekcyjne Odwracalny mimowolne nilpotentny Normalna Prostokątny Jednomodułowe Unipotentny Jednolity Całkowicie jednomodułowy Ważenie
Z konkretnymi aplikacjami	osądzać Znak naprzemienny Rozszerzony Bezout Carlemana Kartan obiegowy Kofaktor Komutacja Dezorientacja Coxeter Dystans Duplikacja i eliminacja Odległość euklidesowa Podstawowe (liniowe równanie różniczkowe) Generator Gram heski Gospodarz Jakobian Za chwilę Opłacać się Wybierać Losowy Obrót Seiferta Ścinanie Podobieństwo Symplektyczny Całkowicie pozytywne Transformacja
Stosowany w statystyce	Krążyna Korelacja Kowariancja Projekt Podwójnie stochastyczny Informacje Fishera Kapelusz Precyzja stochastyczny Przemiana
Używany w teorii grafów	Przyleganie dwustronność Stopień Edmondowie Zakres Laplace'a Sąsiedztwo Seidela Tutte
Używany w nauce i inżynierii	Cabibbo – Kobayashi – Maskawa Gęstość Podstawowe (wizja komputerowa) Rozmyte asocjacyjne Gamma Gell-Mann Hamiltonian Nieregularny Zachodzić na siebie S Przejście stanu Podstawienie Z (chemia)
Terminy pokrewne	Normalna forma Jordana Niezależność liniowa Wykładnicza macierz Macierzowa reprezentacja przekrojów stożkowych Idealna matryca Pseudoodwrotność Forma schodkowa wiersza Wroński
Portal matematyczny Lista macierzy Kategoria: Macierze