Next:Entropy SeriesUp:Entropy Rate and Entropy
Previous:Entropy Rate and Entropy 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 

$\displaystyle 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.,

$\displaystyle 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
$\displaystyle H(X_{N+k}\vert X_{k+1},...,X_{k+N-1})=H(X_N\vert X_1,X_2...,X_{N-1}).$

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.,

$\displaystyle 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
$\displaystyle H(X_{N+1}\vert X_1,X_2,...,X_N)=H(X_{N+1}\vert X_1,X_2,...,X_{N-1}).$

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 

$\displaystyle 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

$\displaystyle 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".

Inder Jeet Taneja
Departamento de Matemática - UFSC
88.040-900 Florianópolis, SC - Brazil