# 20.6 Exercises

1. Let  and  be two independent tosses of a fair coin. Find the entropy  and the joint entropy . Why is ?

2. Consider an unfair coin where the two outcomes, heads and tails, have probabilities  and .

1. If the coin is flipped two times, what are the possible outcomes along with their respective probabilities?

2. Show that the entropy in part (a) is . How could this have been predicted without calculating the probabilities in part (a)?

3. A random variable  takes the values  with probabilities . Calculate the entropy .

4. Let  be a random variable taking on integer values. The probability is 1/2 that  is in the range , with all such values being equally likely, and the probability is 1/2 that the value is in the range , with all such values being equally likely. Compute .

5. Let  be a random event taking on the values , all with positive probability. What is the general inequality/equality between  and , where  is the following?

1. 

2. 

1. In this problem we explore the relationship between the entropy of a random variable  and the entropy of a function  of the random variable. The following is a short proof that shows . Explain what principles are used in each of the steps.


2. Letting  take on the values  and letting , show that it is possible to have .

3. In part (a), show that you have equality if and only if  is a one-to-one function (more precisely,  is one-to-one on the set of outputs of  that have nonzero probability).

4. The preceding results can be used to study the behavior of the run length coding of a sequence. Run length coding is a technique that is commonly used in data compression. Suppose that  are random variables that take the values  or . This sequence of random variables can be thought of as representing the output of a binary source. The run length coding of  is a sequence  that represents the lengths of consecutive symbols with the same value. For example, the sequence  has a run length sequence of . Observe that L is a function of . Show that L and  uniquely determine . Do L and  determine ? Using these observations and the preceding results, compare , , and .

6. A bag contains five red balls, three white balls, and two black balls that are identical to each other in every manner except color.

1. Choose two balls from the bag with replacement. What is the entropy of this experiment?

2. What is the entropy of choosing two balls without replacement? (Note: In both parts, the order matters; i.e., red then white is not the same as white then red.)

7. We often run into situations where we have a sequence of  random events. For example, a piece of text is a long sequence of letters. We are concerned with the rate of growth of the joint entropy as  increases. Define the entropy rate of a sequence  of random events as


1. A very crude model for a language is to assume that subsequent letters in a piece of text are independent and come from identical probability distributions. Using this, show that the entropy rate equals .

2. In general, there is dependence among the random variables. Assume that  have the same probability distribution but are somehow dependent on each other (for example, if I give you the letters TH you can guess that the next letter is E). Show that



and thus that



(if the limit defining  exists).

8. Suppose we have a cryptosystem with only two possible plaintexts. The plaintext  occurs with probability  and  occurs with probability . There are two keys,  and , and each is used with probability . Key  encrypts  to  and  to . Key  encrypts  to  and  to .

1. Calculate , the entropy for the plaintext.

2. Calculate , the conditional entropy for the plaintext given the ciphertext. (Optional hint: This can be done with no additional calculation by matching up this system with another well-known system.)

9. Consider a cryptosystem .

1. Explain why .

2. Suppose the system has perfect secrecy. Show that



and



3. Suppose the system has perfect secrecy and, for each pair of plaintext and ciphertext, there is at most one corresponding key that does the encryption. Show that .

10. Prove that for a cryptosystem  we have


11. Consider a Shamir secret sharing scheme where any five people of a set of 20 can determine the secret , but no fewer can do so. Let  be the entropy of the choice of , and let  be the conditional entropy of , given the information supplied to the first person. What are the relative sizes of  and ? (Larger, smaller, equal?)

12. Let  be a random event taking on the values , all with equal probability.

1. What is the entropy ?

2. Let . What is ?

1. Show that the maximum of  for  occurs when .

2. Let  for . Show that the maximum of



subject to the constraint , occurs when . (Hint: Lagrange multipliers could be useful in this problem.)

1. Suppose we define . Show that if  and  are independent, and  has  possible outputs, then .

2. Use (a) to show that  is not a good description of the uncertainty of  given .