Typical Set

In information theory, the typical set is a set of sequences whose probability is close to two raised to the negative power of the entropy of their source distribution. That this set has total probability close to one is a consequence of the asymptotic equipartition property (AEP) which is a kind of law of large numbers. The notion of typicality is only concerned with the probability of a sequence and not the actual sequence itself.

This has great use in compression theory as it provides a theoretical means for compressing data, allowing us to represent any sequence Xn using nH(X) bits on average, and, hence, justifying the use of entropy as a measure of information from a source.

The AEP can also be proven for a large class of stationary ergodic processes, allowing typical set to be defined in more general cases.

Read more about Typical Set(Weakly) Typical Sequences (weak Typicality, Entropy Typicality), Strongly Typical Sequences (strong Typicality, Letter Typicality), Jointly Typical Sequences

Other articles related to "typical set, typical, set":

Entanglement Distillation - Entanglement Concentration - Pure States
... which is likely to occur with high probability, known as the typical set the new state is And renormalizing, Then the fidelity as ... Alice can perform a measurement onto the typical set subset of, converting the state with high fidelity ... The theorem of typical sequences then shows us that is the probability that the given sequence is part of the typical set, and may be made arbitrarily close to 1 for sufficiently large m, and therefore the ...
Noisy-channel Coding Theorem - Outline of Proof - Achievability For Discrete Memoryless Channels
... length strings of channel outputs, we can define a jointly typical set by the following We say that two sequences and are jointly typical if they lie in the ... A message W is chosen according to the uniform distribution on the set of codewords ... source sequence if there exists exactly 1 codeword that is jointly typical with Y ...
Asymptotic Equipartition Property
... It is fundamental to the concept of typical set used in theories of compression ... process, the one actually produced is most probably from a loosely defined set of outcomes that all have approximately the same chance of being the one actually realized ... a higher probability than any outcome in this set, the vast number of outcomes in the set almost guarantees that the outcome will come from the set ...

Famous quotes containing the words set and/or typical:

    Come, thou long-expected Jesus,
    born to set thy people free;
    from our fears and sins release us,
    let us find our rest in thee.
    Charles Wesley (1707–1788)

    A building is akin to dogma; it is insolent, like dogma. Whether or no it is permanent, it claims permanence, like a dogma. People ask why we have no typical architecture of the modern world, like impressionism in painting. Surely it is obviously because we have not enough dogmas; we cannot bear to see anything in the sky that is solid and enduring, anything in the sky that does not change like the clouds of the sky.
    Gilbert Keith Chesterton (1874–1936)