Entropy Rates of a Stochastic Process

Markov Chains

Stationary process

A stochastic process is said to be stationary if the joint distribution of any subset of the sequence of random variables is invariant with respect to shifts in the time index; that is,

$$\begin{array}{rl}& \mathrm{P}\left\{X_1=x_1,X_2=x_2,\dots ,X_n=x_n\right\}\\ & =\mathrm{P}\left\{X_{1+l}=x_1,X_{2+l}=x_2,\dots ,X_{n+l}=x_n\right\}\end{array}$$

for every $n$ and every shift $l$ and for all $x_1,x_2,\dots ,x_n\in \mathcal{X}$.

Markov process

A discrete stochastic process $X_1,X_2,\dots ,$ is said to be a Markov chain or a Markov process if for $n=1,2,\dots$

$$\mathrm{P}(X_{n+1}\mid X_n,X_{n-1},\dots ,X_1)=\mathrm{P}(X_{n+1}|X_n)$$

In this case, the joint probability mass function of the random variables can be written as

$$p(x_1,x_2,\dots ,x_n)=p(x_1)p(x_2|x_1)p(x_3|x_2)\cdots p(x_n|x_{n-1})$$

Time invariance

The Markov chain is said to be time invariant if the conditional probability $p(x_{n+1}|x_n)$ does not depend on $n$; that is, for $n=1,2,\dots$

$$\mathrm{P}(X_{n+1}=b\mid X_n=a)=\mathrm{P}(X_2=b\mid X_1=a)$$

for all $a,b\in \mathcal{X}$.