1. Another way to define the typical set is through the empirical pmf of xn defined as
µ ( x | xn ) = | { i: xi = x } | / n, x € X
By the WLLN, the empirical pmf µ ( x | xn ) is close to the true pmf p(x). We then define the typical set as
Te(n) = { xn : | µ ( x | xn ) – p(x) | <= e p(x), x € X }
Show that for any nonnegative function g(x), and for xn: € Te(n)
(1-e) E { g(X) } <= [ g(x1 )+ …+ g(xn)] / n <= (1+e) E { g(X) }.
In the above inequality, letting g(x) = – log p(x) and assuming i.i.d. Xi, get the corresponding bound on p(xn).
https://web.stanford.edu/class/ee376b/hwset1sol.pdf extra problems的6
2. Consider a channel with binary input and output and transition probabilities p(y|x) given by
p ( 0 | 0 ) = 1, p ( 1 | 0) = 0
p ( 0 | 1 ) = 1/2, p ( 1 | 1 ) = 1/2
Compute the capacity of this channel and the capacity-achieving input distribution.
http://www.ee.bgu.ac.il/~haimp/rc10/HW/hw4sol2.pdf 的3
3. We wish to encode a Bernouli (q) process V1, V2, …, for transmission over a binary symmetric channel with crossover probability p. Find the condition on p and q so that the probability of error can be made to go to zero as the block size go to infinity.
http://www.ee.bgu.ac.il/~haimp/rc10/HW/hw6sol_max_entropy_side_info.pdf 的2
4. Let Y1 and Y2 be conditionally independent and conditionally identically distributed given X. Show that
I ( X; Y1, Y2 ) = 2 I ( X; Y1 ) – I ( Y1 ; Y2 )
Conclude that the channel X –> ( Y1, Y2 ) has a capacity that is less than twice the capacity of the channel X–> Y1.
http://www.ee.bgu.ac.il/~haimp/rc10/HW/hw4sol2.pdf 的5
5. Consider a BSC with crossover probability p represented by Yi = Xi + Zi mod 2, where Xi , Yi , and Zi are respectively the input, the output, and the noise at time i. Then
P ( Zi = 0 ) = 1-p and P ( Zi = 1 ) = p
for all i. We assume that {Xi } and {Zi} are independent, but we make no assumption that Zi are i.i.d. so that the channel may have memory.
(a) Prove that I ( Xn ; Yn ) <= n – H(p)
(b) Show that the upper bound in (a) can be achieved by letting Xi be i.i.d. fair bits and Z1 = Z2 =… Zn
(c) Show that with the condition in (b), I ( Xn ; Yn ) > n C, where C= 1-H(p) is the capacity of the BSC if it is memoryless. That is, memory can increase capacity.
https://documents.epfl.ch/groups/i/ip/ipg/www/2009-2010/Information_Theory_and_Coding/itc_sol08.pdf 的5