8. Markovské řetězce s diskrétním časem. Jejich limitní vlastnosti. (NI-VSM)

---

Základní pojmy

Important

• Náhodný process
  • Náhodný proces je systém náhodných veličin definovaný na pravděpodobnostním prostoru.
  • Buďte $(Ω, F, P)$ pravděpodobnostní prostor a $T ⊆ R$ indexová množina potom $X$ nazýváme reálný náhodný proces $$X = \{X_t \mid t \in T\}, \quad X_t: \Omega \to \mathbb{R}$$
    • $X_t$ je náhodná veličina pro každé $t \in T$
    • Každá $X_t$ mapuje elementární jev na reálné číslo
    • Celý systém $X$ popisuje vývoj náhodné veličiny
  • Množinu $T$ lze chápat jako čas, časová souslednost je dána uspořádáním množiny $T$ .
  • Je-li $T$ nejvýše spočetná, mluvíme o diskrétním čase, např. $\{X_n | n \in N_0\}$.
    • Je-li $T$ nespočetná, mluvíme o spojitém čase, např $\{X_t | t ≥ 0\}$.
  • Množina stavů $S$ je minimální podmnožina $R$, pro kterou platí, že $P(X_t \in S) = 1$ pro každé $t \in T$ . Jinými slovy $S$ je společná množina hodnot veličin Xt.
    • $S$ může být nejvýše spočetná (diskrétní)
    • $S$ může být nespočetná (kontinuum)
• Spočetná množina stavů
  • $S = N , \quad S = \{1, . . . , |S|\}$
• Diskrétní čas
  • $X = \{X_n | n = 0, 1, 2, . . . \}$
• Rozdělení v čase
  • Rozdělení v čase $n ∈ N_0$ charakterizované pravděpodobnostní funkcí, tj. pro $n ∈ N_0$ a $i ∈ S$: $p_i(n) := P(X_n = i) ,\quad p(n) := (p_1(n), p_2(n), . . . )$
• Matice pravděpodobností přechodu
  • $P_{ij} (n, m) := P(X_m = j|X_n = i) ,\quad P(n, m) := (P_{ij} (n, m))_{i,j\in S}$

Markovské řetězce

Important

• Náhodný proces $\{X_n | n ∈ N_0\}$ s nejvýše spočetnou množinou stavů $S$ nazýváme markovský řetězec s diskrétním časem, pokud splňuje markovskou podmínku, tj. pokud $∀n ∈ N$, a $∀s, s_0, . . . , s_{n−1} ∈ S$ platí: $$P(X_n=s|X_{n-1}=s_{n-1},...,X_1=s_1,X_0=s_0) = P(X_n=s|X_{n-1}=s_{n-1})$$
  • Markovský proces tedy zapomíná historii
• Chapman-Kolmogorova rovnice
  • Jedna se o vetu která říká ze pravděpodobnost přechodu z $n$ do $r$ je stejná jako pravděpodobnost přechodu z $n$ do $m$ a pak $m$ do $r$ pokud $n\leq m \leq r \in N_0$
    • $P(n,r) = P(n,m)\cdot P(m,r)$

Homogenní Markovský řetězec

Important

• Jedna se o markovský řetězec který ma stejné pravděpodobnosti přechodu mezi jakýmikoliv dvěma přechody při jakýmkoliv čase.
• Řekneme, že markovský řetězec je homogenní, pokud $\forall n ∈ N$ a $∀ i, j ∈ S$ platí: $$P(X_{n+1}=j|X_n=i) =P(x_1=j|X_0=i)$$
• Můžeme tak definovat jednokrokovou matici přechodů pro celý markovský řetězec: $$P:=P(0,1) = (P(X_1=j|X_0=i))_{ij \in S}$$
  • Můžeme pak definovat přechod jako $p(n)=p(0)\cdot P$
• Pro homogenní markovský řetězec platí $∀m, n ∈ N_0$: $P(m,m+n)=P(0,n)=P^n$

• Jednokroková matice přechodu je tak stochastická matice:
  • $P_{i,j}\geq 0\quad \forall i,j \in S$ to znamená ze $P$ ma nezáporné prvky
  • $\sum_{j\in S}P_{ij} = 1$ to znamená ze součet řádku v matici $P$ je roven 1
  • Součin stochastických matic je opět stochastická matice
• K libovolné čtvercové stochastické matici $P$ existuje homogenní markovský řetězec s diskrétním časem takový, že $P$ je jeho maticí přechodu

Important

Stacionární rozdělení

• Jedna se o vektor s počátečním stavem ze kterého už se nedostanu.
• Toto rozděleni popisuje dlouhodobé chovaní celého Markovského řetězce
• Jou-li všechny stavy přechodné nebo trvalé nulové, stacionární rozdělení neexistuje
• Jsou-li všechny stavy trvalé nenulové, stacionární rozdělení $π$ existuje a je jediné.
• Může byt vice stacionárních rozdělení
• Buď $\{X_n|n ∈ N_0\}$ homogenní markovský řetězec s maticí přechodu $P$. Vektor $\pi$ je stacionárním rozdělením pokud platí:
  • $\forall i \in S: \pi _i \geq 0$ tedy obsahuje pro všechny stavy nezáporné prvky
  • $\sum_{i\in S}\pi_i=1$ součet všech pravděpodobností pro jednotlivé stavy je roven $1$
  • $\pi\cdot P=\pi$

Limitní vlastnosti

Klasifikace stavů

Important

• Trvalý stav
  • Takový stav ve kterém když jsme se do něho určíte vrátíme za $n$ kroku:
  • $P(\exists n\in \mathbb{N}: X_n=i|x_0=i)=1$
    • Nenulový stav pokud střední doba návratu je $<\infty$
    • Nulový stav pokud střední doba návratu je $=\infty$ (Pri omezeném poctu stavu toto neexistuje)
• Přechodný Stav
  • Takový stav ve kterém když jsme se do něho určíte nevrátíme po $n$ krocích:
  • $P(\exists n\in \mathbb{N}: X_n=i|x_0=i)<1$
• V řetězci s konečně mnoha stavy :
  • nemohou být všechny stavy přechodné (tj. existuje alespoň jeden trvalý)
  • neexistují stavy trvalé nulové (tj. trvalé stavy jsou vždy nenulové)

Čas první návštěvy

• Čas první návštěvy
  • Jedna se o první čas kdy navštívím stav $i$
  • $\tau_i = \text{min}\{n\in N|X_n=i\}$
• Pravděpodobnost první návštěvy
  • Pravděpodobnost ze navštívím $j$ při startu z $i$ v n-tem kroku je.
  • $f_{ij}(n) := P (\tau_{ij}=n|X_0=i) \quad \quad n\geq 1,\quad f_{ij}(0) := 0$
• Pravděpodobnost ze někdy navštívím
  • Pravděpodobnost ze někdy navštívím $j$ při startu z $i$ je
  • $f_{ij} := P (\tau_{ij}<+\infty|X_0=i) =\sum_{n=1}^\infty f_{ij}(n)$
• Trvalý stav
  • $f_{ii} := P (\tau_{ij}<+\infty|X_0=i) = 1$
  • Nenulový stav pokud střední doba návratu je $<\infty$
  • Nulový stav pokud střední doba návratu je $=\infty$
• Přechodný Stav
  • $f_{ii} := P (\tau_{ij}<+\infty|X_0=i) < 1$

Střední doba návratu

• Střední dobu návratu do stavu $i ∈ S$ definujeme jako: $$\mu_i := E(\tau_i|X_0=i)= \begin{cases} \sum_{n=1}^\infty nf_{ii}(n) & \text{je-li } i \text{ trvaly} \\ +\infty & \text{je-li } i \text{ prechodny} \end{cases}$$

Periodicita

• Periodou stavu $i ∈ S$ nazveme číslo: $d(i) =\text{gcd}\{n \in N | P_{ii}(n)>0\}$
• Největšího společný dělitel časů, kdy se řetězec vrátí do stavu $i$.
• Periodický: $d(i)>1$
• Aperiodický: $d(i)=1$

Klasifikace stavů pomocí matice přechodu $P$

• Přechodný $\Longleftrightarrow \sum_{n=0}^{+\infty} P_{ii}(n) < +\infty$ potom $P_{ji}(n) \rightarrow 0$
• Trvalý nulový $\Longleftrightarrow \sum_{n=0}^{+\infty} P_{ii}(n) = +\infty \wedge \lim_{n\rightarrow \infty} P_{ii}=0$ potom $P_{ji}(n) \rightarrow 0$
• Trvalý nenulový aperiodický $\Longleftrightarrow \lim_{n\rightarrow \infty} P_{ii}=1/\mu_i$ potom $P_{ji}(n) \rightarrow f_{ji}/\mu_i$
• Trvalý nenulový periodický $\Longleftrightarrow \text{ma periodu } d(i) \text{ a }\lim_{k\rightarrow \infty} P_{ii}(k\cdot d(i))=d(i)/\mu_i>0$

Important

Rozklad množiny stavů

• Uzavřená množina stavů: Množina stavu ze kterých se nedostanu v libovolném čase
• Nerozložitelná množina: Množina stavu u kterých se dostanu libovolné z jednoho stavu do druhého stavu za spočitatelný čas
• Jednoznačný rozklad: Množinu stavů $S$ lze jednoznačně rozložit do tvaru: $$S = T \cup C_1 \cup C_2 \cup ...$$ Kde $T$ je množina všech přechodných stavů, $C_1, C_2,...$ jsou vzájemně disjunktní nerozložitelné uzavřené množiny trvalých stavů.

Matice přechodu stavů

Matice přechodu po uspořádání množiny stavů $S = (T, C_1, C_2, \ldots)$:

$$P = \begin{bmatrix} T & R_1 & R_2 & \cdots \\ 0 & C_1 & 0 & \cdots \\ 0 & 0 & C_2 & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix}$$

• $T$: Čtvercová matice přechodů mezi přechodnými stavy
• $C_i$: Čtvercová matice přechodů mezi trvalými stavy
• $R_i$: Matice přechodů z přechodných stavů do trvalých stavů $C_i$

Pohlceni

$$P = \begin{bmatrix} T & R \\ 0 & C \\ \end{bmatrix}$$

• Zjišťuji s jakou pravděpodobností se dostanu z množiny přechodových stavu do množiny trvalých stavu
• Čas absorpce – minimální čas, kdy se dostanu pryč z množiny $T$ do množiny $C$
• Máme na to matici $U$

Important

• Fundamentální matice nám ukazuje střední počet průchodu stavu $j$ pred pohlcením pokud začnu v $i$ v $N_{ij}$
  • $N = (I-T)^{-1}$