Information, rate of generation of

A quantity characterizing the amount of information (cf. Information, amount of) emanating from an information source in unit time. The rate of generation of information of an information source $ u $ with discrete time generating the communication $ \xi = ( . . . , \xi _ {-} 1 , \xi _ {0} , \xi _ {1} , . . . ) $, formed by a sequence of random variables $ \{ {\xi _ {k} } : {k = . . . , - 1, 0, 1 , . . . } \} $ taking values from some discrete set $ X $, is defined by the equation

$$ \tag{* } \overline{H}\; ( u) = \ \lim\limits _ {n - k \rightarrow \infty } \ { \frac{1}{n - k } } H ( \xi _ {k} ^ {n} ), $$

if this limit exists. Here $ H ( \xi _ {k} ^ {n} ) $ is the entropy of the random variable $ \xi _ {k} ^ {n} = ( \xi _ {k} \dots \xi _ {n} ) $. The variable $ \overline{H}\; ( u) $, defined by (*), is also called the entropy (in a symbol) of the information source.

In certain cases one can successfully prove the existence of the limit in (*) and calculate it explicitly, e.g. in the case of stationary sources. Explicit formulas for $ \overline{H}\; ( u) $ have been obtained for stationary Markov sources and Gaussian sources. The concept of a rate of generation of information is closely related to that of redundancy of an information source.

If $ u $ is a stationary ergodic information source with finite number of states, then the following property of asymptotic uniform distribution (the McMillan theorem, [1]) holds. Let $ P ( x ^ {L} ) = {\mathsf P} \{ \xi ^ {L} = x ^ {L} \} $, where $ x ^ {L} = ( x _ {1} \dots x _ {L} ) $ are the values of $ \xi ^ {L} = ( \xi _ {1} \dots \xi _ {L} ) $ in an information interval of length $ L $. For any $ \epsilon , \delta > 0 $, there is an $ L _ {0} ( \epsilon , \delta ) $ such that for all $ L \geq L _ {0} ( \epsilon , \delta ) $,

$$ {\mathsf P} \left \{ \left | { \frac{- \mathop{\rm log} P ( x ^ {L} ) }{L} } - \overline{H}\; ( u) \right | > \delta \right \} < \epsilon . $$

References

[1]	J. Wolfowitz, "Coding theorems of information theory" , Springer (1961)
[2]	R. Gallagher, "Information theory and reliable communication" , Wiley (1968)
[3]	A.A. Feinstein, "Foundations of information theory" , McGraw-Hill (1958)

References

[a1]	I. Csiszar, J. Körner, "Information theory. Coding theorems for discrete memoryless systems" , Akad. Kiado (1981)
[a2]	A. Rényi, "A diary on information theory" , Akad. Kiado & Wiley (1987)