Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CO 739 Information Theory and Applications
Question 1. Let XY be jointly distributed random variables on the sample space X × Y. For x ∈ X , let p(x) denote the distribution of Y |(X = x). Let q be an arbitrary distribution over Y.
(a) Prove that
I(X : Y ) ≤ Ex←X S(p(x)∥q) .
(b) Let Y1, Y2, . . . , Yn be a sequence of jointly distributed random variables, distributed as q. Suppose that X1X2 · · · Xn ∼ (Y1Y2 · · · Yn)|E, for some event E with Pr(E) ≥ 2
−δn. Prove that S(X1X2 · · · Xn ∥ Y1Y2 · · · Yn) ≤ δn , and hence that there is an index i such that Xi ∼ q
′
, where q
′
is a distribution close to q in ℓ1 distance: ∥q
′ − q∥1 ∈ O(√
δ ).
Question 2. (a) Let XY and UV be two pairs of jointly distributed random variables with X, U ∈ X and Y, V ∈ Y. Prove that h(XY, UV ) ≥ h(X, U), i.e., Hellinger distance is monotonic under taking marginals.
(b) Let X := X1X2 · · · Xn be a random variable, with Xi being mutually independent. Let M be jointly distributed with X , and S ⊆ [n ] be a random variable independent of XM such that for every i ∈ [n], we have Pr(i ∈ S) ≤ p. Prove that I(XS : M|S) ≤p I(X : M) .
Question 3. Let ϵ ∈ (0, 1). Let d be an even positive integer, and
a ∈ {± 1 } d
with exactly d/2 coordinates equal to 1. Let p(a) be the distribution over [d] given by p(a)i
:= 1 d (1 + a i ϵ) for i ∈ [d].
(a) Let X(a) ∼ p(a). Show that H(X(a)) ≥ log d − cϵ2
for a universal constant c.
(b) Let δ ∈ [0, 1). Suppose there is an algorithm that learns a with probability at least 1 − δ given n independent samples from p(a).
(i) Describe a protocol by which a sender can encode a string a as above using only samples from p(a) so that the receiver can identify a with probability at least 1 −δ. What is the length of the encoding?
(ii) Derive as large a lower bound on n as you can.
Question 4. For ϵ ∈ (0, 1/2), we say a subset of strings C ⊆ {0, 1}
n
is an ϵ-cover if every n-bit string x is within Hamming distance ϵn from some element in C.
(a) Prove that any ϵ-cover C has cardinality |C| ≥ 2
n(1−h(ϵ))
.
(b) Prove that for large enough n, a uniformly random subset of {0, 1}
n
of size n
3 2 (1 − h( ϵ )) n is an ϵ -cover with probability at least 1 −2
−Ω(n)
. (You may use without proof the inequality