PHYSICS · Multi-part · Fermi University Physics · Quantum Information & Technology · Quantum information theory and communication · Quantum information theory and communication
Quantum Information and Technology, Ch Entropy and compression
Problem
A source emits symbols independently with P(1)=0.3, P(0)=0.7, giving binary entropy H=h(0.3)=0.881 bits per symbol. Someone argues: 'I can compress this source at rate R=0.7 bits per symbol, below H, and still keep the error small. For a block of n symbols I encode only the 2nR most probable sequences and declare a failure on the rest. Because the source is not perfectly random, its probability is concentrated on a small set of highly likely sequences, so as n grows the fraction of blocks that fall outside my encoded set keeps shrinking. A fixed rate below H with a small, stable error is therefore possible.'
((a)) Identify the error in this reasoning, referring to the size and probability of the typical set.
((b)) For a block of n=2000 symbols and ϵ=0.05 bits, use Chebyshev's inequality to bound the probability δ that a block is atypical, and use the size of the typical set to bound the fraction of its probability that 2nR sequences can cover. Hence bound the probability that the scheme above succeeds, and say what happens to that bound as n→∞.