Entropy Rate

NAVIGATION

Home

Research

Bookshelf

Garden

FIND ME ON

GitHub

Home

Research

Bookshelf

Garden

ℹ

Definition (Entropy Rate)

The entropy rate of a source $\{X_{i}\}^{\infty}_{i=1}$ with alphabet $\mathcal{X}$ is denoted by $H(\mathcal{X})$ and defined by $H(\mathcal{X}):=\lim_{n\to\infty} \frac{1}{n}H(X^{n})$ provided that the limit exists.

Remark

If source $\{X_{i}\}^{\infty}_{i=1}$ is a DMS (i.e. iid), then $H(\mathcal{X})=\lim_{n\to\infty} \frac{1}{n}H(X_{1},\cdots,X_{n})=\lim_{n\to\infty} \frac{1}{n}(nH(X_{1}))=H(X_{1})$

Lemma

For a stationary source $\{X_{i}\}^{\infty}_{i=1}$ , the sequence of conditional entropies $\{H(X_{i}|X^{i-1})\}^{\infty}_{i=1}$ is decreasing in $i$ and has a limit denoted by $\tilde H(\mathcal{X}):=\lim_{i\to\infty}H(X_{i}|X^{i-1})$

Theorem

For a stationary source $\{X_{i}\}^{\infty}_{i=1}$ , its entropy rate $H(\mathcal{X})$ always exists and is equal to $\tilde H(\mathcal{X})$ : $H(\mathcal{X})=\tilde H(\mathcal{X})=\lim_{n\to\infty}H(X_{n}|X^{n-1})$

Remark

Since $\tilde H(\mathcal{X})=H(\mathcal{X})$ and $H(X_{n}|X^{n-1})\downarrow\tilde H(\mathcal{X})$ by lemma 1, then we have $H(\mathcal{X})\le H(X_{n}|X^{n-1}) \ \forall n\ge 1$
Can also be shown that $\frac{1}{n}H(X^{n})$ is decreasing in $n$ $H(\mathcal{X})\le \frac{1}{n}H(X^{n}) \ \forall n\ge1$

Linked from

Shannon Coding Theorem

Lempel-Ziv Coding

Lossless Joint Source-Channel Coding Theorem

Stationary & Ergodic Source