Let and be two independent tosses of a fair coin. Find the entropy and the joint entropy . Why is ?
Consider an unfair coin where the two outcomes, heads and tails, have probabilities and .
If the coin is flipped two times, what are the possible outcomes along with their respective probabilities?
Show that the entropy in part (a) is . How could this have been predicted without calculating the probabilities in part (a)?
A random variable takes the values with probabilities . Calculate the entropy .
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 .
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?
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.
Letting take on the values and letting , show that it is possible to have .
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).
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 .
A bag contains five red balls, three white balls, and two black balls that are identical to each other in every manner except color.
Choose two balls from the bag with replacement. What is the entropy of this experiment?
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.)
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
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 .
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).
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 .
Calculate , the entropy for the plaintext.
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.)
Consider a cryptosystem .
Explain why .
Suppose the system has perfect secrecy. Show that
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 .
Prove that for a cryptosystem we have
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?)
Let be a random event taking on the values , all with equal probability.
What is the entropy ?
Let . What is ?
Show that the maximum of for occurs when .
Let for . Show that the maximum of
subject to the constraint , occurs when . (Hint: Lagrange multipliers could be useful in this problem.)
Suppose we define . Show that if and are independent, and has possible outputs, then .
Use (a) to show that is not a good description of the uncertainty of given .