A source emits independent

PHYSICS · Subjective · 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 independent, identically distributed symbols x∈{0,1}x\in\{0,1\} with p(1)=0.30p(1)=0.30 and p(0)=0.70p(0)=0.70. For a length-nn sequence xnx^n with probability p(xn)=∏i=1np(xi)p(x^n)=\prod_{i=1}^n p(x_i), define Yn=−1nlog⁡2p(xn).Y_n = -\frac{1}{n}\log_2 p(x^n). (a) Show that YnY_n has mean H=h(0.30)H=h(0.30) and that its variance is σ2/n\sigma^2/n, where σ2\sigma^2 is the variance of the single-symbol quantity −log⁡2p(xi)-\log_2 p(x_i). Using Chebyshev's inequality, derive P(∣Yn−H∣>ϵ)≤σ2nϵ2.P(|Y_n-H|>\epsilon)\le \frac{\sigma^2}{n\epsilon^2}. (b) Compute HH and σ2\sigma^2 for this source. (c) Evaluate the bound for n=400n=400, ϵ=0.05\epsilon=0.05, and use it to give the resulting two-sided bound on the size ∣Tϵn∣|T_\epsilon^n| of the ϵ\epsilon-typical set.

Browse the problem library