 Typical set

For an IID source, the epsilon-typical set consists of words $u^n$ satisfying $|-(1/n)\log p(u^n)-H(U)|\le \epsilon$. Its probability tends to one, and its cardinality is at most $2^{n(H(U)+\epsilon )}$.

In information theory, the concept of a "typical set" is a fundamental idea introduced by Claude Shannon in his work on data compression and communication theory. The typical set is used to describe a subset of sequences from a larger set of possible sequences that exhibit certain "typical" properties in terms of probability and information. ### Definition 1. **Source and Sequences**: Consider a discrete memoryless source that can produce sequences of symbols from a finite alphabet.