Markov chain

NAVIGATION

Home

Research

Bookshelf

Garden

FIND ME ON

GitHub

Home

Research

Bookshelf

Garden

#Probability #InfoTheory >[!def] Markov chain >Let $X_n, n\in\mathbb{Z^+}$ be a stochastic process with a countable state space $S$ . $X_n,n\ge0$ is a discrete time Markov Chain if for any $n\ge0$ and any states $i_0,\cdots,i_n,i_{n+1}\in S$ $P(X_{n+1}=i_{n+1}|X_o=i_o,\cdots,X_n=i_n)=P(X_{n+1}=i_{n+1}|X_n=i_n)$

Theorem (Joint distribution of Markov chain)

Denote $\lambda$ the probability mass function of $X_0$ , and $P$ the |transition matrix of a Markov Chain $X_n,n\ge 0$ . Then for any $N\ge0$ , and any states $i_0,\cdots,i_N\in S$ , $P(X_0=i_0,\cdots,X_N=i_N)=\lambda_{i_0}p_{i_0i_1}\cdots p_{i_{N-1}i_N}$

Definition ( $M$ ’th Order Markov Chain)

The source $\{X_i\}_{i=1}^{\infty}$ is called an $M$ ’th order Markov chain (or Markov source of memory M), where $M\ge1$ fixed integer if $P(X_i=a_{i}|X^{i-1}=a^{i-1})=P(X_{i}=a_{i}|X_{i-1}=a_{i-1},\cdots,X_{iM}=a_{iM}) \ \forall i>M, \ a^{i}\in \mathcal{X}^{i}$

Remark

If $\{X_i\}_{i=1}^{\infty}$ is an M’th order MC with alphabet $\mathcal{X}$ then it can be converted into a MC $\{Z_i\}_{i=1}^{\infty}$ with alphabet $\mathcal{X}^M$ where $Z_i:=(X_{i},X_{i+1},\cdots,X_{i+M-1}), \ i\ge1$

Markov chain

Linked from