Editing Arithmetic coding (section)

==== Asymptotic equipartition ====
We can understand this intuitively. Suppose the source is ergodic, then it has the [[asymptotic equipartition property]] (AEP). By the AEP, after a long stream of <math>n</math> symbols, the interval of <math>(0, 1)</math> is almost partitioned into almost equally-sized intervals.

Technically, for any small <math>\epsilon > 0</math>, for all large enough <math>n</math>, there exists <math>2^{nH(X)(1+O(\epsilon))}</math> strings <math>x_{1:n}</math>, such that each string has almost equal probability <math>Pr(x_{1:n}) = 2^{-nH(X)(1+ O(\epsilon))} </math>, and their total probability is <math>1-O(\epsilon)</math>.

For any such string, it is arithmetically encoded by a binary string of length <math>k</math>, where <math>k</math> is the smallest <math>k</math> such that there exists a fraction of form <math>\frac{?}{2^k}</math> in the interval for <math>x_{1:n}</math>. Since the interval for <math>x_{1:n}</math> has size <math>2^{-nH(X)(1+ O(\epsilon))} </math>, we should expect it to contain one fraction of form <math>\frac{?}{2^k}</math> when <math>k = nH(X)(1+O(\epsilon))</math>.

Thus, with high probability, <math>x_{1:n}</math> can be arithmetically encoded with a binary string of length <math>nH(X) ( 1 + O(\epsilon))</math>.