Go to:Table of Contents

Entropy Rate

Let $X_1,X_2,...,X_N,...$ be a sequence of discrete finite random variables. The entropy rate is defined as 

$$H_0= \lim_{N \to \infty}{H(X_1,X_2,...,X_N)\overN}.$$

In general $H_0$ doesn't exist. Here we shall give conditions for evaluating its value. This is based on well known statistical concepts famous as stationary random variables and Markov Chain.

Definition 1.1. (Stationary). A sequence of RV's $X_1,X_2,...,X_N,...$ is said to be stationary if the joint probability distributions are invariant under the transition of time origin i.e.,

$$p(x_{i_1},x_{i_2},...,x_{i_N})=p(x_{i_1+k},x_{i_2+k},...,x_{i_N+k}),$$ where $k$ is a nonnegative integer. As an obvious consequence we have

$$H(X_{N+k}\vert X_{k+1},...,X_{k+N-1})=H(X_N\vert X_1,X_2...,X_{N-1}).$$ (1.10)

Definition 1.2. (Markov Chain) A sequence of random variables $X_1,X_2,...,X_N,...$ is said to be Markov Chain if for every N, the RV $X_{N+1}$ is conditionally independent of $(X_1,X_2,...,X_{N-1})$ given $X_N$ i.e.,

$$p(x_{i_{N+1}}\vert x_{i_1},x_{i_2},...,x_{i_N})=p(x_{i_{N+1}}\vert x_{i_1},x_{i_2},...,x_{i_{N-1}}).$$ As an obvious consequence, we have

$$H(X_{N+1}\vert X_1,X_2,...,X_N)=H(X_{N+1}\vert X_1,X_2,...,X_{N-1}).$$ (1.11)

Based on the above definitions the following property holds.

Property 1.62. If the sequence of random variables is stationary, we have

(i) $0 \leq H(X_N\vert X_1,...,X_{N-1}) \leq H(X_{N-1}\vert X_2,...,X_{N-2})\leq ... \leq H(X_2\vert X_1) \leq H(X_1).$

(ii) $H(X_N\vert X_1,...,X_{N-1}) \leq {H(X_1,...,X_N)\over N} \leqH(X_1).$

(iii) ${1\over N} H(X_1,...,X_N) \leq {1\over N-1} H(X_1,...,X_{N-1}).$

(iv) $\lim_{N\to \infty}{1\over N}H(X_1,...,X_N)=\lim_{N\to \infty}H(X_N\vert X_1,...,X_{N-1}).$

In case of stationary Markov sequence we have 

$$H_0=\lim_{N\to\infty}H(X_N\vert X_{N-1}).$$

Moreover, the following property holds.

Property 1.63. The entropy rate of a stationary Markov sequence $(X_1,X_2,...,X_N,...)$ is given by

$$H_0=-\sum_{i=1}^n{p_i\sum_{j=1}^m{ p_{j\vert i} \log p_{j\vert i}}},$$ where $P=(p_1,p_2,...,p_n)\ \in\ \Delta_n$ is the equilibrium distribution.

Note 1.5. The expression $H_0$ given in the property 1.63 is famous as "Markov Entropy".