CS3236: Tutorial 3
(Block Source Coding)
1. [Typical Set Calculations]
(a) Suppose a discrete memoryless source (DMS) emits h (heads) and t (tails) with probability 1/2
each, i.e., PX (h) = PX (t) = 12 . For ϵ = 0.01 and n = 5, what is the typical set Tn (ϵ)?
(Hint: This part can be answered in one line)
(b) Repeat part (a) with PX (h) = 0.2, PX (t) = 0.8, n = 5, and ϵ = 0.0001.
(Hint: Try taking logs in the definition of typicality, applying the definition of entropy, and sim-
plifying as much as possible.)
(c) Your answer to part (b) should come down to showing that the proportion of heads (or tails)
is close to the average. Your answer to part (a) could in fact also be interpreted similarly, but
instead requiring the sum of the number of heads and tails to be close to its average (which is
trivially true, since this sum is n).
For sources with more than two symbols, it turns out that we shouldn’t expect an equivalence
between being in Tn (ϵ) and certain counts (or sums of counts) being close to their average. Find
an example that supports this claim.
2. [Strong Typicality]
Consider a source distribution PX such that PX (x) > 0 for all x ∈ X , where X is a finite alphabet.
The strongly typical set is defined as
n o
Tn (ϵ) = x ∈ X n : nPX (x)(1 − ϵ) ≤ nx (x) ≤ nPX (x)(1 + ϵ), ∀x ∈ X ,
Pn
where nx (x) = i=1 1{xi = x} is the number of times x occurs in the sequence x = (x1 , . . . , xn ). This
is a bit easier to interpret than the definition of typicality from the lecture: It just states that the
observed proportion of occurrences of each symbol is roughly equal to the probability of that symbol.
(a) Show that for X = (X1 , . . . , Xn ) distributed i.i.d. on PX , it holds that P[X ∈ Tn (ϵ)] → 1 as
n → ∞ for fixed ϵ > 0.
(b) Show that for any non-negative valued function a(x), and any sequence x = (x1 , . . . , xn ) ∈ Tn (ϵ),
it holds that
n
1X
E[a(X)](1 − ϵ) ≤ a(xi ) ≤ E[a(X)](1 + ϵ).
n i=1
(c) Show that for any sequence x = (x1 , . . . , xn ) ∈ Tn (ϵ), it holds that
n
1X 1
H(X)(1 − ϵ) ≤ log2 ≤ H(X)(1 + ϵ).
n i=1 PX (xi )
Notice that this means that strongly typical sequences are also typical according to the definition
in the lecture (up to the replacement of ϵ by ϵH(X), which essentially changes nothing since ϵ
can be chosen arbitrarily).
1
(d) Show that the the size of the typical set satisfies
2nH(X)(1−ϵ) (1 − o(1)) ≤ |Tn (ϵ)| ≤ 2nH(X)(1+ϵ)
where o(1) is a quantity that tends to zero as n → ∞.
3. [Equality in Fano’s Inequality]
Fano’s inequality states that for two random variables X and X̂ on a common alphabet X , it holds
that
H(X|X̂) ≤ H2 (Pe ) + Pe log2 (|X | − 1),
where H2 (·) is the binary entropy function, and Pe = P[X̂ ̸= X].
Suppose that X = {1, 2, 3, 4, 5} and that Pe = 0.2. Describe (in words or mathematically) a joint
distribution on (X, X̂) that makes Fano’s inequality hold with equality.
4. [Asymptotic Equipartition Principle]
Consider X1 , X2 , . . . , Xn , . . . , an infinite sequence iid random variables, each Q
with probability distri-
n
bution PX . Let X = (X1 , . . . , Xn ), and let its (joint) distribution be PX (x) = i=1 PX (xi ).
1
(a) Find an expression for limn→∞ PX (x) n that holds with high probability.
(b) Let f (x) be an arbitrary function from X to the interval (0, 1]. Find an expression for
" n
# n1
Y
lim f (Xi )
n→∞
i=1
that holds with high probability.
Hints
1. (a) is straightforward because all sequences are equally likely. In (b) try to simplify the property in
the typical set’s definition by taking the log and simplifying.
2. In (a) use the law of large numbers and the union bound. In (b) write the summation in terms of
nx (x) and then apply the bounds in the definition of Tn (ϵ). (c) is a special case of part b.
1
3. In (a), apply 2(·) to both sides of the equation limn→∞ n log2 PX (X) = −H(X). In (b) argue similarly
with f (·) replacing PX (·).