Let $X_1$ and $X_2$ be two independent tosses of a fair coin. Find the entropy $H(X_1)$ and the joint entropy $H(X_1\text{,}{X}_2)$. Why is $H(X_1\text{,}{X}_2)=H(X_1)+H(X_2)$?

Consider an unfair coin where the two outcomes, heads and tails, have probabilities $p(heads)=p$ and $p(tails)=1-p$.

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 $-2p{log}_2(p)-2(1-p){log}_2(1-p)$. How could this have been predicted without calculating the probabilities in part (a)?

A random variable $X$ takes the values $1\text{,}2\text{,}\cdots \text{,}n\text{,}\cdots$ with probabilities $\frac{1}{2}\text{,}\frac{1}{2^2}\text{,}\cdots \text{,}\frac{1}{2^n}\text{,}\cdots$. Calculate the entropy $H(X)$.

Let $X$ be a random variable taking on integer values. The probability is 1/2 that $X$ is in the range $[0\text{,}{2}^8-1]$, with all such values being equally likely, and the probability is 1/2 that the value is in the range $[2^8\text{,}{2}^{32}-1]$, with all such values being equally likely. Compute $H(X)$.

Let $X$ be a random event taking on the values $-2\text{,}-1\text{,}0\text{,}1\text{,}2$, all with positive probability. What is the general inequality/equality between $H(X)$ and $H(Y)$, where $Y$ is the following?

1. $Y=2^X$

2. $Y=X^2$

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

   $$\begin{array}{c}H(X\text{,}f(X))=H(X)+H(f(X)|X)=H(X)\text{,}\\ H(X\text{,}f(X))=H(f(X))+H(X|f(X))\ge H(f(X))\text{.}\end{array}$$

2. Letting $X$ take on the values $\pm 1$ and letting $f(x)=x^2$, show that it is possible to have $H(f(X))<H(X)$.

3. In part (a), show that you have equality if and only if $f$ is a one-to-one function (more precisely, $f$ is one-to-one on the set of outputs of $X$ 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 $X_1\text{,}{X}_2\text{,}\cdots \text{,}{X}_n$ are random variables that take the values $0$ or $1$. This sequence of random variables can be thought of as representing the output of a binary source. The run length coding of $X_1\text{,}{X}_2\text{,}\cdots \text{,}{X}_n$ is a sequence $L=(L_1\text{,}{L}_2\text{,}\cdots \text{,}{L}_k)$ that represents the lengths of consecutive symbols with the same value. For example, the sequence $110000100111$ has a run length sequence of $L=(2\text{,}4\text{,}1\text{,}2\text{,}3)$. Observe that L is a function of $X_1\text{,}{X}_2\text{,}\cdots \text{,}{X}_n$. Show that L and $X_1$ uniquely determine $X_1\text{,}{X}_2\text{,}\cdots \text{,}{X}_n$. Do L and $X_n$ determine $X_1\text{,}{X}_2\text{,}\cdots \text{,}{X}_n$? Using these observations and the preceding results, compare $H(X_1\text{,}{X}_2\text{,}\cdots \text{,}{X}_n)$, $H(L)$, and $H(L\text{,}{X}_1)$.

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.)

We often run into situations where we have a sequence of $n$ 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 $n$ increases. Define the entropy rate of a sequence $X=\left\{X_k\right\}$ 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 $H(X_1)$.

2. In general, there is dependence among the random variables. Assume that $X_1\text{,}{X}_2\text{,}\cdots X_n$ 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

   $$H(X_1\text{,}{X}_2\text{,}\cdots X_n)\le \sum _{k}H(X_k)$$

   and thus that

   $$H_{\mathrm{\infty }}(\text{X})\le H(X_1)$$

   (if the limit defining $H_{\mathrm{\infty }}$ exists).

Suppose we have a cryptosystem with only two possible plaintexts. The plaintext $a$ occurs with probability $1/3$ and $b$ occurs with probability $2/3$. There are two keys, $k_1$ and $k_2$, and each is used with probability $1/2$. Key $k_1$ encrypts $a$ to $A$ and $b$ to $B$. Key $k_2$ encrypts $a$ to $B$ and $b$ to $A$.

1. Calculate $H(P)$, the entropy for the plaintext.

2. Calculate $H(P|C)$, 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 $\{P\text{,}K\text{,}C\}$.

1. Explain why $H(P\text{,}K)=H(C\text{,}P\text{,}K)=H(P)+H(K)$.

2. Suppose the system has perfect secrecy. Show that

   $$H(C\text{,}P)=H(C)+H(P)$$

   and

   $$H(C)=H(K)-H(K|C\text{,}P)\text{.}$$

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 $H(C)=H(K)$.

Prove that for a cryptosystem $\{P\text{,}K\text{,}C\}$ we have

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

Let $X$ be a random event taking on the values $1\text{,}2\text{,}3\text{,}\dots \text{,}36$, all with equal probability.

1. What is the entropy $H(X)$?

2. Let $Y=X^{36}(\mathrm{m}\mathrm{o}\mathrm{d}37)$. What is $H(Y)$?

1. Show that the maximum of $-p{log}_{2}p-(1-p){log}_2(1-p)$ for $0\le p\le 1$ occurs when $p=1/2$.

2. Let $p_i\ge 0$ for $1\le i\le n$. Show that the maximum of

   $$-\sum _i{p}_i{log}_2{p}_i\text{,}$$

   subject to the constraint $\sum _i{p}_i=1$, occurs when $p_1=\cdots =p_n$. (Hint: Lagrange multipliers could be useful in this problem.)

1. Suppose we define $\tilde{H}(Y|X)=-\sum _{x\text{,}y}{p}_Y(y|x){log}_2{p}_Y(y|x)$. Show that if $X$ and $Y$ are independent, and $X$ has $|\mathit{X}|$ possible outputs, then $\tilde{H}(Y|X)=|\mathit{X}|H(Y)\ge H(Y)$.

2. Use (a) to show that $\tilde{H}(Y|X)$ is not a good description of the uncertainty of $Y$ given $X$.