W tym rozdziale rozważamy jednorodny łańcuch Markowa X0,X1,…,Xn,… na skończonej przestrzeni stanów X=1,…,d. Będziemy posługiwać się wygodną i zwięzłą notacją wektorowo-macierzową. Macierz przejścia o wymiarach d×d oznaczamy P=P⁢x,yx,y∈X. Rozkład początkowy utożsamiamy z wektorem wierszowym ξ⊤=ξ⁢1,…,ξ⁢x,…,ξ⁢d. W dalszym ciągu, mówiąc o łańcuchu Markowa, będziemy mieli na myśli ustaloną macierz przejścia P i dowolnie wybrany rozkład początkowy ξ. Przyjmujemy oznaczenie Pξ(⋅). W szczególności, Px(⋅)=P(⋅|X0=x), dla x∈X. Analogicznie będziemy oznaczali wartość oczekiwaną: Eξ lub Ex. Zauważmy, że P(Xn+2=y|Xn=x)=∑zP(x,z)P(z,y)=P2(x,y). Ogólniej, macierz przejścia w m krokach jest m-tą potęgą macierzy P:

Rozkład brzegowy zmiennej losowej Xn jest wektorem ξ⊤⁢Pn:

Z macierzą stochastyczną P związany jest graf skierowany opisujący możliwe przejścia łańcucha. Jest to graf X,E, gdzie zbiorem wierzchołków jest przestrzeń stanów, zaś E⊆X×X jest zbiorem takich par x,y, że P⁢x,y>0. Pojęcia, o których teraz będziemy mówić, są związane tylko ze strukturą grafu, czyli z położeniem niezerowych elementów macierzy przejścia.

Mówimy, że stan y jest osiągalny ze stanu x, jeśli x=y lub istnieje liczba naturalna n≥1 i ciąg stanów x=x0,x1,x2,…,xn-1,xn=y taki, że P⁢xi-1,xi>0 dla i=1,…,n. Równoważnie, Pn⁢x,y>0 dla pewnego n≥0. Będziemy stosowali oznaczenie ,,x→y”.

Stany x i y komunikują się, co zapiszemy ,,x↔y”, jeśli x→y i y→x.

Stan x jest istotny, jeśli dla każdego y takiego, że x→y mamy y→x. W przeciwnym razie stan x nazywamy nieistotnym. Stan x jest więc nieistotny, jeśli istnieje stan y do którego można przejść z x, ale nie można wrócić do x. Zbiór stanów istotnych oznaczymy przez C, zaś zbiór stanów nieistotnych przez T. Zbiór C jest (dla łańcucha o skończonej przestrzeni stanów) zawsze niepusty. Zbiór T może być pusty.

Jeśli x↔y dla dowolnych x,y∈X, czyli wszystkie stany komunikują się, to łańcuch nazywamy nieprzywiedlnym. Oczywiście, wszystkie stany łańcucha nieprzywiedlnego są istotne, X=C. Łańcuch nieprzywiedlny nazywamy nieokresowym, jeśli dla dowolnych x,y∈X istnieje n0 takie, że dla każdego n≥n0 mamy Pn⁢x,y. Wspomnijmy, że przyjęta przez nas definicja nieokresowości bywa formułowana w nieco inny, ale równoważny sposób. Dla naszych potrzeb wystarczy następujące proste spostrzeżenie: jeśli łańcuch jest nieprzywiedlny i P⁢x,x>0 dla przynajmniej jednego stanu x, to łańcuch jest nieokresowy. Łatwo zauważyć, że dla łańcucha nieprzywiedlnego i nieokresowego, dla dostatecznie dużych n macierz Pn ma wszystkie elementy niezerowe. Wynika to z faktu, że rozważamy łańcuchy ze skończoną przestrzenią stanów.

Jeśli x↔y dla dowolnych x,y∈C, czyli wszystkie stany istotne komunikują się, to łańcuch nazywamy jednoklasowym. Łańcuch jednoklasowy może mieć niepusty zbiór stanów nieistotnych T. Łańcuch jednoklasowy możemy ,,przerobić” na nieprzywiedlny jeśli ograniczymy przestrzeń do stanów istotnych. Macierz P|C=P⁢x,yx,y∈C jest, jak łatwo widzieć, stochastyczna.

Interesują nas głównie łańcuchy, które ,,zmierzają w kierunku położenia równowagi”. Aby uściślić co to znaczy ,,równowaga”, przypomnijmy pojęcie stacjonarności. Rozkład π jest stacjonarny jeśli dla każdego stanu y,

W notacji macierzowej: π⊤=π⊤⁢P. Stąd oczywiście wynika, że π⊤=π⊤⁢Pn.

Poniższy prosty fakt można uzasadnić na wiele sposobów. W następnym podrozdziale przytoczymy, wraz z dowodem, piękne twierdzenie Kaca (Twierdzenie 14.2), które implikuje Twierdzenie 14.1.

Z Twierdzenia 14.1 łatwo wynika następujący wniosek.

Przedstawimy w tym podrozdziale konstrukcję, która prowadzi do łatwch i eleganckich dowodów twierdzeń granicznych. Podstawowa idea jest następująca. Wyróżnia się jeden ustalony stan, powiedzmy z∈X. W każdym momencie wpadnięcia w z, następuje ,,odnowienie” i dalsza ewolucja łańcucha jest niezależna od przeszłości.

Niech, dla z∈X,

Przyjmujemy przy tym naturalną konwencję: Tz=∞, jeśli Xn≠z dla każdego n≥1. Zmienna losowa Tz jest więc czasem pierwszego dojścia do stanu z. Jeśli założymy, że łańcuch startuje z punktu z, to Tz jest czasem pierwszego powrotu.

Podamy teraz bardzo ciekawą interpretację rozkładu stacjonarnego, wykazując przy okazji jego istnienie (Twierdzenie 14.1). Ustalmy dowolnie wybrany stan z. Udowodnimy, że średni czas, spędzony przez łańcuch w stanie y pomiędzy wyjściem z z i pierwszym powrotem do z jest proporcjonalny do π⁢y, prawdopodobieństwa stacjonarnego.

Odnotujmy ważny wniosek wynikający z powyższego twierdzenia:

Zjawisko odnowienia, czyli regeneracji pozwala sprowadzić badanie łańcuchów Markowa do rozpatrywania niezależnych zmiennych losowych, a więc do bardzo prostej i dobrze znanej sytuacji. Aby wyjaśnić to bliżej, zauważmy następującą oczywistą równość. Na mocy własności Markowa i jednorodności,

Zatem warunkowo, dla Tz=n, łańcuch ,,regeneruje się w momencie n” i zaczyna się zachowywać dokładnie tak, jak łańcuch który wystartował z punktu z w chwili 0. Niezależnie od przeszłości! Ponieważ z jest ustalone, będziemy odtąd pomijali górny indeks przy T=Tz. Zdefiniujmy kolejne momenty odnowienia, czyli czasy odwiedzin stanu z:

Momenty 0<T1<⋯<Tk<⋯ dzielą trajektorię łańcucha na następujące ,,losowe wycieczki”, czyli losowej długości ciągi zmiennych losowych:

Wycieczka zaczyna się w punkcie z i kończy tuż przed powrotem do z. Oznaczmy k-tą wycieczkę symbolem Ξk:

Z tego, co powiedzieliśmy wcześniej wynika, że wszystkie ,,wycieczki” są niezależne. Co więcej wycieczki Ξk mają ten sam rozkład, z wyjątkiem być może początkowej, czyli Ξ1. Jeśli rozkład początkowy jest skupiony w punkcie z, to również wycieczka Ξ1 ma ten sam rozkład (0 jest wtedy momentem odnowienia).

Podejście regeneracyjne, czyli rozbicie łańcucha na niezależne wycieczki prowadzi do ładnych i łatwych dowodów PWL i CTG dla łańcuchów Markowa. Sformułujemy najpierw pewną wersję Mocnego Prawa Wielkich Liczb. Rozważmy funkcję f o wartościach rzeczywistych, określoną na przestrzeni stanów. Przypomnijmy, że Eπ⁢f=∑x∈Xπ⁢x⁢f⁢x.

Na podobnej idei oparty jest ,,regeneracyjny” dowód Centralnego Twierdzenia Granicznego (istnieją też zupełnie inne dowody).

Przytoczony powyżej rozumowanie daje ciekawe przedstawienie asymptotycznej wariancji:

Istnieje wiele wyrażeń na asymptotyczną wariancję, przy tym różne wzory wymagają różnych założeń. Najbardziej znany jest wzór (10.5). Sformułujemy w jawny sposób potrzebne założenia, i przepiszemy ten wzór w postaci macierzowej. Najpierw musimy wprowadzić jeszcze parę nowych oznaczeń. Wygodnie będzie utożsamić funkcję f z wektorem kolumnowym

Niech

gdzie π oznacza, jak zwykle, rozkład stacjonarny. Możemy teraz napisać

oraz

Podobnie,

W powyższym wzorze, I jest macierzą identycznościową, 1 oznacza kolumnę jedynek. Łatwo sprawdzić, że Pn-1⁢π⊤=P-1⁢π⊤n dla n>0 (ale nie dla n=0). Jeśli P jest macierzą przejścia nieprzywiedlnego i nieokresowego łańcucha Markowa, to Pn-1⁢π⊤→0 przy n→∞ na mocy Słabego Twierdzenia Ergodycznego. Stąd wynika zbieżność następujących szeregów:

Macierz Z nazywamy macierzą fundamentalną. Ponieważ P0-1⁢π⊤=I-1⁢π⊤ zaś P-1⁢π⊤0=I więc Z=A+1⁢π⊤.

Zauważmy, że ani CTG ani PWL nie wymagały założenia o nieokresowości ale w 14.1 to założenie jest potrzebne.

Jak widać, asymptotyczna wariancja wyraża się w postaci formy kwadratowej σas2⁢f=f⊤⁢C⁢f o współczynnikach

Okazuje się, że ,,asymptotyczne obiążenie” estymatora θ⌃n=1/n⁢∑i=0n-1f⁢Xi wartości oczekiwanej θ=Eπ⁢f można napisać w postaci formy dwuliniowej ξ⊤⁢A⁢f, gdzie ξ jest rozkładem początkowym. Podsumowując,

Uzasadnienie drugiej części powyższego wzoru pozostawiam jako ćwiczenie. Stąd z łatwością otrzymujemy ważny wzór (10.6) z Rozdziału 10 (wyrażenie na błąd średniokwadratowy).

Dowód Słabego Twierdzenia Ergodycznego, który przedstawimy, opiera się na tak zwanym sprzęganiu (ang. coupling), czyli metodzie ,,dwóch cząstek”. Ta metoda, jak się okaże, nie tylko pozwala udowodnić zbieżność rozkładów prawdopodobieństwa, ale daje w wielu przypadkach bardzo dobre oszacowania szybkości zbieżności.