# markov Chain Definitions

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Practical application for estimation: The general concept for the application of this lies within having a set of generated $x_i$ which approach a distribution $f(x)$ so that a variation of importance estimation can be used to estimate an integral in the form
$I = \displaystyle\int^\ h(x)f(x)\,dx$ by $\hat{I} = \frac{1}{N}\displaystyle\sum_{i=1}^Nh(x_i)$
All that is required is a Markov chain which eventually converges to $f(x)$.

In the previous example, the entries $p_{ij}$ in the transition matrix $P$ represent the probability of reaching state $j$ from state $i$ after one step. For this reason, the sum over all entries j in a particular column sum to 1, as this itself must be a pmf if a transition from $i$ is to lead to a state still within the state set for $X_t$.

Homogeneous Markov Chain
The probability matrix $P$ is the same for all indicies $n\in T$. $Pr(X_n=j|X_{n-1}=i)= Pr(X_1=j|X_0=i)$

If we denote the pmf of X_n by a probability vector $\frac{}{}\mu_n = [P(X_n=x_1),P(X_n=x_2),..,P(X_n=x_i)]$
where $i$ denotes an ordered index of all possible states of $X$.
Then we have a definition for the
marginal probabilty $\frac{}{}\mu_n(i) = P(X_n=i)$
where we simplify $X_n$ to represent the ordered index of a state rather than the state itself.

From this definition it can be shown that, $\frac{}{}\mu_{n-1}P=\mu_0P^n$

Proof:

$\mu_{n-1}P=[\sum_{\forall i}(\mu_{n-1}(i))P_{i1},\sum_{\forall i}(\mu_{n-1}(i))P_{i2},..,\sum_{\forall i}(\mu_{n-1}(i))P_{ij}]$ and since

$\sum_{\forall i}(\mu_{n-1}(i))P_{ij}=\sum_{\forall i}P(X_n=x_i)Pr(X_n=j|X_{n-1}=i)=\sum_{\forall i}P(X_n=x_i)\frac{Pr(X_n=j,X_{n-1}=i)}{P(X_n=x_i)}$ $=\sum_{\forall i}Pr(X_n=j,X_{n-1}=i)=Pr(X_n=j)=\mu_{n}(j)$

Therefore,
$\frac{}{}\mu_{n-1}P=[\mu_{n}(1),\mu_{n}(2),...,\mu_{n}(i)]=\mu_{n}$

With this, it is possible to define $P(n)$ as an n-step transition matrix where $\frac{}{}P_{ij}(n) = Pr(X_n=j|X_0=i)$
Theorem: $\frac{}{}\mu_n=\mu_0P^n$
Proof: $\frac{}{}\mu_n=\mu_{n-1}P$ From the previous conclusion
$\frac{}{}=\mu_{n-2}PP=...=\mu_0\prod_{i = 1}^nP$ And since this is a homogeneous Markov chain, $P$ does not depend on $i$ so
$\frac{}{}=\mu_0P^n$

From this it becomes easy to define the n-step transition matrix as $\frac{}{}P(n)=P^n$

### Summary

• transition matrix $( P )$ is an NxN when $N=|X|$ matrix with $P_{ij}=Pr(X_1=j|X_0=i)$ where $i,j \in X$
• n-step transition matrix $( P_n )$ also NxN with $P_{ij}(n)=Pr(X_n=j|X_0=i)$
• marginal (probability of X) $\mu_n(i) = Pr(X_n=i)$
• Theorem: $P_n=P^n$
• Theorem: $\mu_n=\mu_0P^n$

---

### Definitions of different types of state sets

Define $i,j \in$ State Space
If $P_{ij}(n) \gt 0$ for some $n$ , then we say $i$ reaches $j$ denoted by $i\longrightarrow j$
This also mean j is accessible by i $j\longleftarrow i$
If $i\longrightarrow j$ and $j\longrightarrow i$ then we say $i$ and $j$ communicate, denoted by $i\longleftrightarrow j$

Theorems
1) $i\longleftrightarrow i$
2) $i\longleftrightarrow j,j\longleftrightarrow k\Rightarrow i\longleftrightarrow k$
3) The set of states of $X$ can be written as a unique disjoint union of subsets $X=X_1 \bigcup X_2\bigcup... \bigcup X_k,k\gt 0$ where two states $i$ and $j$ communicate $IFF$ they belong to the same subset

More Definitions
A set is Irreducible if all states communicate with each other ($\Leftrightarrow k=1$)
A subset of states (Class) is Closed if once you enter it, you can never leave. Alternatively, a subset of states (Class) is Open if it is possible to leave the Class.
An Absorbing set is a closed set with only 1 element