<jupyter_start><jupyter_text>Shanon Information ContentFirst, let's consider storing an integer that isn't random. Let's say we have an integer that is from $0,1,\dots ,63$. Then the number of bits needed to store this integer is $\log _{2}(64)=6$ bits: you tell me $6$ bits and I can tell you exactly what the integer is.A different way to think about this result is that we don't a priori know which of the $64$ outcomes is going to be stored, and so each outcome is equally likely with probability $\frac{1}{64}$. Then the number of bits needed to store an event $\mathcal{A}$ is given by what's called the “Shannon information content" (also called self-information):$$\log _{2}\frac{1}{\mathbb {P}(\mathcal{A})}.$$ In particular, for an integer $x\in \{ 0,1,\dots ,63\}$, the Shannon information content of observing $x$ is$$\log _{2}\frac{1}{\mathbb {P}(\text {integer is }x)}=\log _{2}\frac{1}{1/64}=\log _{2}64=6\text { bits}.$$ If instead, the integer was deterministically $0$ and never equal to any of the other values $1,2,\dots ,63,$ then the Shannon information content of observing integer $0$ is$$\log _{2}\frac{1}{\mathbb {P}(\text {integer is }0)}=\log _{2}\frac{1}{1}=0\text { bits}.$$ This is not surprising in that a outcome that we deterministically always observe tells us no new information. Meanwhile, for each integer $x\in \{ 1,2,\dots ,63\},$$$\log _{2}\frac{1}{\mathbb {P}(\text {integer is }x)}=\log _{2}\frac{1}{0}=\infty \text { bits}.$$ How could observing one of the integers $\{ 1,2,\dots ,63\}$ tell us infinite bits of information?! Well, this isn't an issue since the event that we observe any of these integers has probability $0$ and is thus impossible. An interpration of Shannon information content is how surprised we would be to observe an event. In this sense, observing an impossible event would be infinitely surprising.It is possible to have the Shannon information content of an event be some fractional number of bits (e.g., $0.7$ bits). The interpretation is that from many repeats of the underlying experiment, the average number of bits needed to store the event is given by the Shannon information content, which can be fractional.  Exercise: Shannon Information ContentI have an integer in mind, uniformly distributed between $0$ and $127$. You can keep guessing what my number is until you get it right (and each time you guess, I tell you whether you got it right). Each time you guess a number wrong, you discard that number so as to not guess it again.For example, if you guess wrong the first time, then the Shannon information content of guessing wrong is$$\log _2\frac{1}{\frac{127}{128}}=\log _{2}\frac{128}{127}=0.0113\dots \text { bits}.$$ If you guess wrong the second time, then the Shannon information content of the second guess is$$\log _2\frac{1}{\frac{126}{127}}=\log _{2}\frac{127}{126}=0.0114\dots \text { bits}.$$ If you guess right on the third time, then the Shannon information content of the third guess is$$\log _2\frac{1}{\frac{1}{126}}=\log _{2}\frac{126}{1}=6.9772\dots \text { bits}.$$ **Question:** For the above example where the third guess is right, what is the sum of the Shannon information content of the three guesses? **Solution:**$$\begin{eqnarray}&&\log_2 \frac1{\frac{127}{128}}+\log_2 \frac1{\frac{126}{127}}+\log_2 \frac1{\frac{1}{126}} \\&&=\log_2 \frac{128}{127}+\log_2 \frac{127}{126}+\log_2 126 \\&&=\log_2 128 - \log_2 127+ \log_2 127 - \log_2 126+ \log_2 126 \\&&=\log_2 128 \\&&=\boxed{7\text{ bits}}.\end{eqnarray}$$**Question:** Suppose you guessed right only after 5 tries. What is the sum of the Shannon information content of these 5 guesses? **Solution:**$$\begin{eqnarray}&&\log_2 \frac1{\frac{127}{128}}+\log_2 \frac1{\frac{126}{127}}+\log_2 \frac1{\frac{125}{126}}+\log_2 \frac1{\frac{124}{125}}+\log_2 \frac1{\frac{1}{124}} \\&&=\log_2 \frac{128}{127}+\log_2 \frac{127}{126}+\log_2 \frac{126}{125}+\log_2 \frac{125}{124}+\log_2 124 \\&&=\log_2 128 - \log_2 127+ \log_2 127 - \log_2 126+ \log_2 126 \\&&\quad- \log_2 125+ \log_2 125 - \log_2 124+ \log_2 124 \\&&=\log_2 128 \\&&=\boxed{7\text{ bits}}.\end{eqnarray}$$ **Question:** Suppose you guess right after $k$ tries $(k \in \{ 1, 2, \dots , 128\})$. If you sum up the Shannon information content for all the guesses up and including the one in which you guess right, does this total number of bits depend on $k$? (While we aren't asking for you to justify your answer, we encourage you to be able to do so! For example, if your answer is "Yes" then you should be able to come up with two specific cases for two different number of tries before guessing right that yield different number of total bits, and if your answer is "No" then you should be able to show why the total number of bits gained is always the same.)**Solution:** The answer is no. The previous two parts provide a clue: the sum we're computing is a telescoping sum where all the terms cancel out except for the first one: $\log _2 128 = 7.$In general, if we guess right after $k$ tries, then the total amount of information “learned" is:$$\begin{eqnarray}&&\left[\sum_{i=1}^{k-1}  \log_2 \frac1{\frac{128 - i}{128 - (i - 1)}}\right]+ \log_2 (128 - (k - 1)) \\&&=\left[\sum_{i=1}^{k-1}  \log_2 \frac{128 - (i - 1)}{128 - i}\right]+ \log_2 (128 - (k - 1)) \\&&=\left[\sum_{i=1}^{k-1}  \log_2 (128 - (i - 1)) - \log_2(128 - i)\right]+ \log_2 (128 - (k - 1)) \\&&= \log_2 128 - \log_2 127 + \log_2 127 - \cdots \\&&\quad- \log_2 (128 - (k - 1)) + \log_2 (128 - (k - 1)) \\&&= \log_2 128 \\&&= 7\text{ bits}.\end{eqnarray}$$Put another way, $7$ bits of information are needed before you know the number, and with wrong guesses, you learn very few bits of information (although as the number of possibilities shrinks, wrong guesses provide more and more bits of information).  Shanon EntropyTo go from the number of bits contained in an event to the number of bits contained in a random variable, we simply take the expectation of the Shannon information content across the possible outcomes. The resulting quantity is called the entropy of a random variable:$$H(X)=\sum _{x}p_{X}(x)\underbrace{\log _{2}\frac{1}{p_{X}(x)}}_{\text {Shannon information content of event }X=x}.$$ The interpretation is that on average, the number of bits needed to encode each i.i.d. sample of a random variable X is $H(X)$. In fact, if we sample n times i.i.d. from $p_{X}$, then two fundamental results in information theory that are beyond the scope of this course state that: (a) there's an algorithm that is able to store these n samples in $nH(X)$ bits, and (b) we can't possibly store the sequence in fewer than $nH(X)$ bits!**Example:** If $X$ is a fair coin toss “heads" or “tails" each with probability $1/2$, then$$\begin{eqnarray}H(X)&=& p_X(\text{heads}) \log_2 \frac1{p_X(\text{heads})}+ p_X(\text{tails}) \log_2 \frac1{p_X(\text{tails})} \\&=& \frac12 \cdot \underbrace{\log_2 \frac1{\frac{1}{2}}}_1+ \frac12 \cdot \underbrace{\log_2 \frac1{\frac{1}{2}}}_1 \\&=& 1 \text{ bit}.\end{eqnarray}$$**Example:** If $X$ is a biased coin toss where heads occurs with probability $1$ then$$\begin{eqnarray}H(X)&=& p_X(\text{heads}) \log_2 \frac1{p_X(\text{heads})}+ p_X(\text{tails}) \log_2 \frac1{p_X(\text{tails})} \\&=& 1 \cdot \underbrace{\log_2 \frac11}_0+ 0 \cdot \cdot \underbrace{\log_2 \frac10}_1 \\&=& 0 \text{ bits},\end{eqnarray}$$where $0 \log _2 \frac10 = 0 \log _2 1 - 0 \log _2 0 = 0$ using the convention that $0 \log _2 0 \triangleq 0$. (Note: You can use l'Hopital's rule from calculus to show that $\lim _{x\rightarrow 0} x \log x = 0 and \lim _{x\rightarrow 0} x \log \frac1x = 0$.)Notation: Note that entropy $H(X) = \sum _ x p_ X(x) \log _2 \frac{1}{p_ X(x)}$ is in the form of an expectation! So in fact, we can write an expectation:$$H(X) = \mathbb {E}\left[\log _2 \frac{1}{p_ X(X)}\right].$$<jupyter_code>def H(pX):
    """
    Retrun Shanon entropy of given probability.
    >>> pX = {-1: 999999/1000000, 999   : 1/1000000}
    >>> H(pX)
    2.137426288890686e-05
    
    >>> coin = {'H': 1/2, 'T': 1/2}
    >>> H(coin)
    1.0
    """
    from math import log
    return - sum([value * log(value,2) for key, value in pX.items()]) 

if __name__ == "__main__":
    import doctest
    doctest.testmod()<jupyter_output><empty_output><jupyter_text>Exercise: Shannon EntropyEntropy gives a very different measure for uncertainty than variance, which we saw previously. Whereas variance $\text {var}(X) = \mathbb {E}[(X-\mathbb {E}[X])^2]$ measures how far a random variable is expected to deviate from its expected value $\mathbb {E}[X]$, entropy measures how many bits are needed on average to store each i.i.d. sample of a random variable $X$.Let's return to the three lotteries from earlier. Here, random variables $L_1, L_2,$ and $L_3$ represent the amount won (accounting for having to pay \$1):|$L_1$      |            $p$           |        $L_2$ |            $p$           |   $L_3$ |       $p$      ||----------:|:------------------------:|-------------:|:------------------------:|--------:|:--------------:||        -1 | $\frac{999999}{1000000}$ |           -1 | $\frac{999999}{1000000}$ |      -1 | $\frac{9}{10}$ ||   -1+1000 |    $\frac{1}{1000000}$   |   -1+1000000 |    $\frac{1}{1000000}$   |   -1+10 | $\frac{1}{10}$ |Compute the following entropies in bits. Please input just the number and do not include the text "bits" at the end. (Please be precise with at least $7$ decimal places, unless of course the answer doesn't need that many decimal places. You could also put a fraction.)- $H(L_1) =$ {{H_1}}    - $H(L_2) =$ {{H_2}}- $H(L_3) =$ {{H_3}}<jupyter_code>p_L1 = {-1: 999999/1000000, 999   : 1/1000000}
p_L2 = {-1: 999999/1000000, 999999: 1/1000000}
p_L3 = {-1:      9/10     , 9     : 1/10     }

H_1 = '{0:0.7f}'.format(H(p_L1))
H_2 = '{0:0.7f}'.format(H(p_L2))
H_3 = '{0:0.7f}'.format(H(p_L3))<jupyter_output><empty_output><jupyter_text>Now that you've computed some entropies, let's answer some general questions about entropy.**Question:** In computing the entropy of a random variable $X$, we look at the probabilities in the probability table of $X.$ Did we have to look at the labels in the probability table (note that the labels correspond to the alphabet of $X$)?[$\times    $] Yes[$\checkmark$] No**Solution:** The answer is no. You can see this in the Python code: we don't need to look at the alphabet $\mathcal{X}$.Suppose for a random variable $X$, we take its probability table and shuffle the ordering of the probabilities (but otherwise keep the labels the same). For example, if $X$ is a biased coin flip with probability of heads $3/4$, suppose we took its table and instead have the probability of tails be $3/4$ and the probability of heads be $1/4$.**Question:** By shuffling the ordering of the probabilities, does the entropy of the random variable change?[$\times    $] Yes[$\checkmark$] No**Solution:** The answer is no. Since what the labels are does not actually matter (of course, we cannot have the same label appear twice in the table though), we can permute the labels (or the probabilities) and get the same entropy.Finally, let's think about how small and large entropy could be.**Question:** We've seen an example where the entropy is $0$ bits. Can entropy be negative? (While there is an intuitive answer for this, see if you can show it mathematically.)[$\times    $] Yes[$\checkmark$] No**Solution:** The answer is no. First, note that for any probability $p\in [0,1]$, the Shannon information content corresponding to this probability is $\log_2 (1/p)$, which has a value from $0$ to infinity, i.e., Shannon information content is always nonnegative. Shannon entropy is just a weighted average of Shannon information content, where the weights are nonnegative. A nonnegative weighted sum of a collection of nonnegative numbers remains nonnegative.**Question:** For a random variable $X$ that takes on one of two values, one with probability $p$ and the other with probability $1-p$, plot the entropy $H(p)$ as a function of $p$ in Python. For what value of $p$ is the entropy maximized (i.e., what value of $p$ yields the largest $H(X))$? Please provide an exact answer.<jupyter_code>%matplotlib inline
import numpy as np
# Ignore divide by zero error
# Ref: http://stackoverflow.com/questions/14861891/runtimewarning-invalid-value-encountered-in-divide
np.seterr(divide='ignore', invalid='ignore')
import matplotlib.pyplot as plt

entropy = lambda p: np.sum(p * np.log2(1 / p))

p_list = np.linspace(0, 1, 50)
plt.figure()
plt.plot(p_list,
         [entropy(np.array([p, 1-p])) for p in p_list])
plt.xlabel('p')
plt.ylabel('H(Ber(p))')
plt.show()<jupyter_output><empty_output><jupyter_text>Information divergence Information divergence (also called “Kullback-Leibler divergence" or “KL divergence" for short, or also “relative entropy") is a measure of how different two distributions $p$ and $q$ (over the same alphabet) are. To come up with information divergence, first, note that entropy of a random variable with distribution $p$ could be thought of as the expected number of bits needed to encode a sample from $p$ using the information content according to distribution $p$:$$\underbrace{\sum _{x}p(x)}_{\begin{matrix}\text {expectation } \\ \text{using }p\end{matrix} }\underbrace{\log _{2}\frac{1}{p(x)}}_{\begin{matrix}\text { information content } \\ \text{ according to }p \end{matrix}}\triangleq \mathbb {E}_{X \sim p}\Big[\log _{2}\frac{1}{p(X)}\Big].$$ Here, we have introduced a new notation: $\mathbb {E}_{X \sim p}$ means that we are taking the expectation with respect to random variable $X$ drawn from the distribution $p$. If it's clear which random variable we are taking the expectation with respect to, we will often just abbreviate the notation and write $\mathbb {E}_ p$ instead of $\mathbb {E}_{X \sim p}$.If instead we look at the information content according to a different distribution $q$, we get$$\underbrace{\sum _{x}p(x)}_{\begin{matrix}\text {expectation } \\ \text{using }p\end{matrix} }\underbrace{\log _{2}\frac{1}{p(x)}}_{\begin{matrix}\text { information content } \\ \text{ according to }p \end{matrix}}\triangleq \mathbb {E}_{X \sim p}\Big[\log _{2}\frac{1}{p(X)}\Big].$$ It turns out that if we are actually sampling from p but encoding samples as if they were from a different distribution $q$, then we always need to use more bits! This isn't terribly surprising in light of the fundamental result we alluded to that entropy of a random variable with distribution $p$ is the minimum number of bits needed to encode samples from $p$.Information divergence is the price you pay in bits for trying to encode a sample from $p$ using information content according to $q$ instead of according to $p$:$$D(p\parallel q)=\mathbb {E}_{X \sim p}\Big[\log _{2}\frac{1}{q(X)}\Big]-\mathbb {E}_{X \sim p}\Big[\log _{2}\frac{1}{p(X)}\Big].$$ Information divergence is always at least $0$, and when it is equal to $0$, then this means that $p$ and $q$ are the same distribution (i.e., $p(x) = q(x)$ for all $x$). This property is called Gibbs' inequality.Gibbs' inequality makes information divergence seem a bit like a distance. However, information divergence is not like a distance in that it is not symmetric: in general, $D(p \parallel q) \ne D(q \parallel p).$Often times, the equation for information divergence is written more concisely as$$D(p\parallel q) = \sum _ x p(x) \log \frac{p(x)}{q(x)},$$ which you can get as follows:$$\begin{eqnarray}D(p\parallel q)&=&  \mathbb{E}_{X \sim p}\Big[\log_{2}\frac{1}{q(X)}\Big]- \mathbb{E}_{X \sim p}\Big[\log_{2}\frac{1}{p(X)}\Big] \\&=&  \sum_x p(x) \log_2 \frac{1}{q(x)}- \sum_x p(x) \log_2 \frac{1}{p(x)} \\&=&  \sum_x p(x)  \Big[ \log_2 \frac{1}{q(x)} - \log_2 \frac{1}{p(x)} \Big] \\&=&  \sum_x p(x)  \log_2 \frac{p(x)}{q(x)}.\end{eqnarray}$$Example: Suppose $p$ is the distribution for a fair coin flip:$$\begin{eqnarray}p(x)&=&\begin{cases}\frac12 & \text{if }x=\text{heads}, \\\frac12 & \text{if }x=\text{tails}. \\\end{cases}\end{eqnarray}$$Meanwhile, suppose q is a distribution for a biased coin that always comes up heads (perhaps it's double-headed):$$\begin{eqnarray}q(x)&=&\begin{cases}1 & \text{if }x=\text{heads}, \\0 & \text{if }x=\text{tails}. \\\end{cases}\end{eqnarray}$$Then$$\begin{eqnarray}D(p \parallel q)&=&  p(\text{heads}) \log_2 \frac{p(\text{heads})}{q(\text{heads})}+ p(\text{tails}) \log_2 \frac{p(\text{tails})}{q(\text{tails})} \\&=&  \frac12\log_2 \frac{\frac12}1+ \underbrace{\frac12\log_2 \frac{\frac12}0}_{\infty} \\&=&  \infty\text{ bits}.\end{eqnarray}$$This is not surprising: If we are sampling from $p$ (for which we could get tails) but trying to encode the sample using $q$ (which cannot possibly encode tails), then if we get tails, we are stuck: we can't store it! This incurs a penalty of infinity bits.Meanwhile,$$\begin{eqnarray}D(q \parallel p)&=&  q(\text{heads}) \log_2 \frac{q(\text{heads})}{p(\text{heads})}+ q(\text{tails}) \log_2 \frac{q(\text{tails})}{p(\text{tails})} \\&=&  1 \log_2 \frac1{\frac12}+ \underbrace{0 \log_2 \frac0{\frac12}}_0 \\&=&  1\text{ bit}.\end{eqnarray}$$When we sample from $q$, we always get heads. In fact, as we saw previously, the entropy of the distribution for an always-heads coin flip is $0$ bits since there's no randomness. But here we are sampling from $q$ and storing the sample using distribution $p$. For a fair coin flip, encoding using distribution $p$ would store each sample using on average $1$ bit. Thus, even though a sample from $q$ is deterministically heads, we store it using $1$ bit. This is the penalty we pay for storing a sample from $q$ using distribution $p$.Notice that in this example, $D(p \parallel q) \ne D(q \parallel p)$. They aren't even close — one is infinity and the other is finite!  Exercise: Information DivergenceWe now look at a different way to think of Shannon entropy for a random variable $X$ with alphabet $\mathcal{X}.$Let random variable $U$ have what's called a uniform distribution over alphabet $\mathcal{X}$, meaning that$$p_ U(x) = \frac{1}{|\mathcal{X}|} \qquad \text {for all }x\in \mathcal{X}.$$ Notationally, we can write $U \sim \text {Uniform}(\mathcal{X})$.In the following problems, suppose the number of labels in $\mathcal{X}$ is given by $k$, i.e., $k = |\mathcal{X}|.$**Question:** What is $H(U)$ in terms of $k$?**Solution:**$$\begin{eqnarray}H(U)&=& \sum_{x\in\mathcal{X}} p_U(x) \log_2 \frac1{p_U(x)} \\&=& \sum_{x\in\mathcal{X}} \frac1k \log_2 \frac1{\frac1k} \\&=& \sum_{x\in\mathcal{X}} \frac1k \log_2 k \\&=& (\log_2 k)\Big(\frac1k\Big)    \underbrace{\sum_{x\in\mathcal{X}} 1}_k \\&=& \log_2 k.\end{eqnarray}$$ So using “log" to mean log base 2, the answer is $log(k)$.Next, we examine the divergence between $p_X$ and the uniform distribution. Show that $D(p_ X \parallel p_ U)$ can be written of the form$$D(p_ X \parallel p_ U) = f(k) - H(X),$$ for a function $f$ that you will determine:**Question:** What is $f$? **Solution:**$$\begin{eqnarray}D(p_X \parallel p_U)&=& \sum_{x\in\mathcal{X}} p_X(x) \log_2 \frac{p_X(x)}{p_U(x)} \\&=& \sum_{x\in\mathcal{X}} p_X(x) \log_2 \frac{p_X(x)}{1/k} \\&=& \sum_{x\in\mathcal{X}} p_X(x) \log_2 (k p_X(x)) \\&=& \sum_{x\in\mathcal{X}} p_X(x) \log_2 k    + \sum_{x\in\mathcal{X}} p_X(x) \log_2 p_X(x) \\&=& (\log_2 k) \underbrace{\sum_{x\in\mathcal{X}} p_X(x)}_1    + \sum_{x\in\mathcal{X}} p_X(x) \log_2 p_X(x) \\&=& \log_2 k    - \sum_{x\in\mathcal{X}} p_X(x) \log_2 \frac{1}{p_X(x)} \\&=& \underbrace{\log_2 k}_{f(k)} - H(X).\end{eqnarray}$$In particular, $f$ is $\log$ base $2$, which for this part you answer by just saying log to mean $\log$ base $2$.Your answers to the previous two parts should tell you how the entropy of a uniform distribution (over an alphabet of size $k$) relates to the entropy of any distribution $p_X$ (over the same alphabet of size $k$).Fill in the blanks:**Question:** Because of Gibbs' inequality, the entropy of random variable \_\_\_\_\_\_\_ cannot be larger than the entropy of random variable \_\_\_\_\_\_\_.**Solution:** Because of Gibbs' inequality, the entropy of random variable $\underline{~X~}$ cannot be larger than the entropy of random variable $\underline{~U~}$.In particular, notice that from the answers to the previous parts,$$D(p_ X \parallel p_ U) = H(U) - H(X).$$ By Gibbs' inequality, information divergence is always nonnegative, which means that we must have $H(U) - H(X) \ge 0$, which means that $H(X) \le H(U)$.  Proof of Gibbs' InequalityWe provide a proof for Gibbs' inequality here for those who are interested. For those of you up for the challenge, try to prove it yourself!There are various ways to prove Gibbs' inequality. We'll be using a way that relies on the fact that $\ln x\le x-1$ for all $x>0$, with equality if and only if $x=1$, which we provide a proof for at the end of this page, but for which you can also readily see from the following plot:<jupyter_code>x = np.linspace(0,2,10000)
plt.figure()
plt.plot(x, np.log(x))
plt.plot(x, x - 1)
plt.xlabel('x')
plt.legend(['ln(x)', 'x - 1'], loc=4)
plt.show()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.15733371233655485, 'fraction_numerical': 0.03752131893121091, 'mean_word_length': 4.142265529841657, 'pattern_counts': {'":': 1, '<': 17, '<?xml version=': 0, '>': 30, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '299400', 'license': 'MIT', 'n_tokens_mistral': 7180, 'n_tokens_neox': 6527, 'n_words': 2758, 'path': 'week04/03 Measuring Randomness.ipynb', 'repo_name': 'infimath/Computational-Probability-and-Inference', 'size': '21108'}