Non-asymptotic Equipartition Properties for Independent and Identically Distributed Sources

Abstract

Given an independent and identically distributed source $X=\{X_i{\}}_{i=1}^{\infty }$ with finite Shannon entropy or differential entropy (as the case may be) $H(X)$, the non-asymptotic equipartition property (NEP) with respect to $H(X)$ is established, which characterizes, for any finite block length $n$, how close $-\frac{1}{n}\ln p(X_1{X}_2...X_n)$ is to $H(X)$ by determining the information spectrum of $X_1{X}_2...X_n$, i.e., the distribution of $-\frac{1}{n}\ln p(X_1{X}_2...X_n)$. Non-asymptotic equipartition properties (with respect to conditional entropy, mutual information, and relative entropy) in a similar nature are also established. These non-asymptotic equipartition properties are instrumental to the development of non-asymptotic coding (including both source and channel coding) results in information theory in the same way as the asymptotic equipartition property to all asymptotic coding theorems established so far in information theory. As an example, the NEP with respect to $H(X)$ is used to establish a non-asymptotic fixed rate source coding theorem, which reveals, for any finite block length $n$, a complete picture about the tradeoff between the minimum rate of fixed rate coding of $X_1...X_n$ and error probability when the error probability is a constant, or goes to 0 with block length $n$ at a sub-polynomial, polynomial or sub-exponential speed. With the help of the NEP with respect to other information quantities, non-asymptotic channel coding theorems of similar nature will be established in a separate paper.

Submitted to IEEE Transaction on Information Theory