Teorie Řetězce s diskrétním časem

Markovské řetězce s diskrétním časem

Náhodný proces

Máme nejvýše spočetnou množinu stavů $S \subset \mathbb{R}$
$$S = \{1, 2, \dots, |S|\}, \quad S = \{1, 2, \dots \}.$$
Náhodný proces $\{X_n | n \in \mathbb{N}_0\}$ je soubor diskrétních náhodných veličin
$$X_n : \Omega \rightarrow S, \quad X_n \sim p(n) = (p_i^{(n)})_{i \in S}, \quad p_i^{(n)} := P(X_n = i).$$
Diskrétní čas $n \in \mathbb{N}_0$. Moment $n$ předchází $n + 1$ a následuje po $n - 1$.

Definice (Markovský řetězec s diskrétním časem)

Proces $\{X_n | n \in \mathbb{N}_0\}$ je označován jako markovský řetězec s diskrétním časem, pokud splňuje markovskou vlastnost:
$$\forall n \in \mathbb{N}, \forall s, s_0, \dots, s_{n-1} \in S \quad P(X_n = s | X_{n-1} = s_{n-1}, \dots, X_1 = s_1, X_0 = s_0) = P(X_n = s | X_{n-1} = s_{n-1}).$$

Homogenní markovské řetězce

Homogenní markovské řetězce

Markovský řetězec je homogenní, pokud
$$\forall n \in \mathbb{N} \text{ a } \forall i, j \in S \quad P(X_{n+1} = j | X_n = i) = P(X_1 = j | X_0 = i).$$
Matice přechodů mezi stavy
$$P = (P_{ij})_{i,j \in S}, \quad P_{ij} := P(X_1 = j | X_0 = i).$$
Pro rozdělení $p(n)$ v čase $n \in \mathbb{N}_0$ platí:
$$p(n) = p(n - 1) \cdot P = p(0) \cdot P^n.$$

Stacionární rozdělení

Vektor $\pi = (\pi_1, \pi_2, \dots)$ je stacionárním rozdělením, pokud řeší soustavu
$$\pi \cdot P = \pi \ \ \ \ \text{\&} \ \ \ \ \sum_{i \in S} \pi_i = 1.$$
Podmínky detailní rovnováhy: pokud jsou splněny, $\pi$ je stacionární rozdělení:
$$\pi_i P_{ij} =\pi_j P_{ji} \ \ \ \text{ pro všechny } \ \ \ i, j \in S$$

Klasifikace stavů

Mějme $X_n$ jako homogenní markovský řetězec s diskrétním časem a množinou stavů $S$.

Definice - Perioda stavu

Periodou stavu $i \in S$ označujeme číslo
$$d(i) := \gcd\{n \in \mathbb{N} | (P^n)_{ii} > 0\}.$$
Stav $i$ s $d(i) > 1$ označujeme jako periodický, stav s $d(i) = 1$ označujeme jako aperiodický.

Definice (Klasifikace stavů)

Stav $i \in S$ je trvalý (rekurentní), pokud
$$P\left(\exists n \in \mathbb{N} : X_n = i | X_0 = i\right) = 1.$$
Stav $i$ je přechodný (transientní), pokud
$$P\left(\exists n \in \mathbb{N} : X_n = i | X_0 = i\right) < 1.$$
Stav $j$ označujeme jako dosažitelný ze stavu $i$ ($i \to j$), pokud $\exists n \in \mathbb{N} : (P^n)_{ij} > 0$.

V konečné množině stavů $S$ platí:

• $i \in S$ je trvalý $\Leftrightarrow \forall j \in S (i \to j \Rightarrow j \to i)$,
• $i \in S$ je přechodný $\Leftrightarrow \exists j \in S (i \to j \land j \nrightarrow i)$.

Rozklad množiny stavů

Můžeme rozložit množinu stavů na
$$S = T \cup C_1 \cup C_2 \cup \dots$$
kde

• $T$ je soubor všech přechodných stavů.
• $C_i$ jsou uzavřené, neredukovatelné soubory trvalých stavů.

Stacionárním rozdělením je konvexní kombinace stacionárních rozdělení podřetězců $C_i$.

Nechť $C := C_1 \cup C_2 \cup \dots$ je soubor všech trvalých stavů. Matici přechodu $P$ lze zapsat jako
$$P = \begin{pmatrix} T & R \\ 0 & C \\ \end{pmatrix},$$
kde sloupce a řádky jsou uspořádány podle množin $T$ a $C$.

Pravděpodobnosti pohlcení

$$U_{ij} := P(\text{být pohlcen přes stav } j | X_0 = i) \text{ pro } i \in T, j \in C,$$

$$N_{ik} := E(\text{počet průchodů stavem } k | X_0 = i) \text{ pro } i, k \in T,$$

$$N_{i \cdot} := E(\text{doba do pohlcení} | X_0 = i) \text{ pro } i \in T.$$ Kde $i$ je radek a $j$ a $k$ je sloupec

Platí
$$N = (I - T)^{-1} \ \ \ \text{;} \ \ \ U = N \cdot R \ \ \ \text{;} \ \ \ N_{\cdot} = N \cdot 1,$$ kde $N$ se nazývá fundamentální matice řetězce.