Stationary & Ergodic Source

NAVIGATION

Home

Research

Bookshelf

Garden

FIND ME ON

GitHub

Home

Research

Bookshelf

Garden

ℹ

Stationary & Ergodic Source

Definition (Ergodic source)

An ergodic source has the property that all its convergent sample averages (of the form $\frac{1}{n}\sum\limits_{i=1}^{n}f(x_{i})$ , for all functions $f$ with $|E[f(x_{n})]<\infty \ \forall n$ ) converge to a constant (as $n\to\infty$ ).

Definition (Stationary & ergodic source)

A stationary ergodic source is a generalization of a DMS such that the WLLN holds which consequently provides a generalization of the AEP such that for a stationary ergodic source $\{X_i\}_{i=1}^\infty$ with pmf $p_X$ and alphabet $\mathcal{X}$ we have $-\frac{1}{n}\log_2(p_{X^n}(X^n))\xrightarrow{n\to\infty}H(\mathcal{X})\mbox{ in probability}$

Theorem (Cesaro-Mean)

If $a_{n}\to a$ as $n\to\infty$ and $b_{n}= \frac{1}{n}\sum\limits_{i=1}^{n}a_{i}$ , then $b_{n}\to a\mbox{ as }n\to\infty$

Proposition (Properties)

For a stationary and ergodic source

Its sample averages converge to a constant given by the expected value almost surely $\frac{1}{n}\sum\limits_{i=1}^{n}f(X_{i})\xrightarrow{n\to\infty}E[f(X_{1})] \ \ a.s.$ .
This shows that the WLLN holds for stationary ergodic sources.
A generalized AEP then holds for such sources with the source entropy replaced with entropy rate.

Theorem (Generalized Shannon Coding Theorem Theorem)

Given a stationary ergodic source then the entropy rate is as follows $H_{D}(\mathcal{X})=\inf\{R: \ R\mbox{ achievable}\}$

Remark

A DMS is stationary ergodic
An irreducible stationary MC is ergodic

Linked from

Redundancy

Kac's Lemma (Stationary Ergodic)

Lempel-Ziv Coding

Lossless Joint Source-Channel Coding Theorem

Asymptotic Equipartition Property

Stationary & Ergodic Source