Some elementary combinatorics/probability theory leading to a simple coding theorem

A certain fair coin is tossed n times. Each time it is tossed, the result is independent of the previous toss. This is an example of an i.i.d. binary random variable.

Q1: (Worst-case "compression") (a) If the coin described above is tossed n times, how many distinct length-n sequences of coin tosses are possible?

(b) Given N possible outcomes of a random variable, how many bits (elements from {0,1}) are required to assign a unique length-N bit-sequence to each possible outcome?

(c) Describe a method based on binary trees, to assign a length-N bit-sequence to an outcome, based on a binary tree, and a corresponding method to reconstruct the coin-toss sequence from the bit-sequence.

(d) If the encoding alphabet is ternary (eg: {0,1,2}) instead of binary, how does your answer to (b) change? How about your answer to (c), if ternary trees are allowed? What if you were tossing a six-sided dice instead of a coin? How do your answers change? What is the time-complexity of your assignment schemes?

Key concepts in Question 1: Random variables, independence, input alphabet, output alphabet, encoder/encoding, decoder/decoding, trees, prefix-free codes, rounding-off, space complexity, computational complexity (notation) 

A second coin is biased with probability p, i.e., it comes up Heads with probability p and Tails with probability 1-p. Each time it is tossed, the result is independent of the previous toss. This is an example of an i.i.d. binary random variable, also called a Bernoulli(p) random variable.

Q2: (Average-case compression) (a) How do your answers to Q1 differ in this case?

(b) What is the probability of observing a particular coin-toss sequence with Heads?

(c) What is the size of the type-class T(k,n) of all coin-toss sequences with exactly k Heads? What is therefore the probability of observing the type-class T(k,n)?

(d) Use Stirling's approximation  to show that , where H(p) is the binary entropy function . Use this to simplify (c). In what sense are the approximations true? (Check out the link to this derivation of Stirling's approximation to find the answer, and try deriving it yourself to get some practice).

(e) For what value of k is your answer in (c) maximized?

(f) For any type-class T(k,n) that is -strongly atypical, i.e., for which , use the Taylor series expansion of the binary entropy function to prove that the probability of observing any element of T(k,n) is "small".

(g) How many type classes are there? Use the union bound and your answer from (f) to obtain an upper bound of observing an element from an -strongly atypical set.

(h) (Achievability) Does the answer of (g) suggest a "better" encoding scheme for biased coins? What is the expected encoding length (average rate) of your scheme? How does this compare with your answers in Q1? (To obtain a better "feel" for your answer, plot the binary entropy function using some mathematical software, such as SCILAB, which is like MATLAB, but is freeware).

(i) (Converse) Is it possible for any other scheme to "substantially" improve on your scheme in (h)? Can your prove your assertion? (Hint: Note that each element in the -strongly typical set has "nearly equal" probability of being observed.) 

(j) (Errors) Suppose we relax our requirement, to say that we only require that an -fraction of the observed sequences must be reconstructed correctly the the decoder, and we don't care about the others. Do your answers in (h) and (i) change substantially? Prove your assertions.

(j) (Binary Source Coding Theorem) Summarize your conclusions from solving this question in the form of a Binary Source Coding Theorem.

(j) (Source Coding Theorem) Can you state and prove a general source coding theorem (for arbitrary finite input and output alphabets, with arbitrary distributions over them?)

Key concepts in Question 2: Blocklength, Probability of an i.i.d. sequence, type class, size of type class, probability of a type class, number of type classes, Stirling's approximation, binary entropy function, asymptotic equality in exponent, strong typicality (properties), strong atypicality (properties), average rate, achievability, converse, errors.

Q3: (Computational complexity)^[1] Can you describe an algorithm, with running time that is polynomial in n, that implements the scheme of Q2(h)?

Comments/Discussion

Sid: This is where you can ask questions from each other/the instructor/tutor about this particular problem set. Please remember to enter your name in boldface before your comment, as I just did.

Any material that we don't cover in class, you should attempt at home.

Note that some text is underlined. This corresponds to exercises that you really should attempt at home.