06 Feb 2020 - Dr. Nithin Nagaraj

Lecture No. 3: Probability, Self-information, Shannon Entropy

[Deadline: February 6, 2020]

Instructions: Do not assume anything over and beyond what was defined in the class. In case you use any identity/theorem outside what was done in the class, you will have to show the proof of the same. But, better to avoid this as much as possible. Show your calculations in entirety. Justify all your answers with appropriate reasoning and arguments.

  1. For a random experiment $X$ with sample space $S$, starting from the axioms of probability, prove:
    Theorem 1: $P(\phi) = 0$.

    Theorem 2: $P(A^c) = 1-P(A)$.

    Theorem 3: $0 \leq P(A) \leq 1$.

    Theorem 4: If $A \subseteq B$, then $P(A) \leq P(B)$.

    Theorem 5: $P(A \setminus B) = P(A) - P(A \cap B)$.

    Theorem 6: $P(A \cup B) = P(A) +P(B) - P(A \cap B)$.

    Theorem 7: $P(A \cup B \cup C) = P(A) + P(B) + P(C) - P(A \cap B) - P(A \cap C) - P(B \cap C) + P(A\cap B \cap C)$.

  2. Plot the functions (a) $f(p) = -p\log_2(p)$, (b) $g(p) = -(1-p)\log_2(1-p)$, (c) $H(p) = f(p)+g(p)$. Take $p$ varying from 0.001 to 0.999 for the plots. What are the maximum values of these functions and at what value of $p$ does the functions achieve maximum? Derive the location of the maxima analytically.

  3. An experiment consists of tossing 2 coins simulataneously. One of the coins is unbiased, but the other coin has HEADS on both sides. List the sample space and find the self-information of all possible outcomes of this random experiment. What is the Shannon Entropy of this experiment? (remember that Shannon Entropy has units :)

  4. Guessing Game: Similar to the guessing game we played in class, let each trial of the game involve picking a number at random from the set $X = {1,2,3,4 }$ with probabilities ${\frac{1}{3}, \frac{1}{3}, \frac{1}{6}, \frac{1}{6} }$ respectively. (a) Find the self-information of each outcome, (b) Find the Shannon entropy of $X$, (c) Design an optimal strategy of asking YES/NO questions, (d) What is the average number of questions in your strategy?, (e) Why is it different from $H(X)$?, (f) Under what conditions will the average number of questions for the best strategy equal $H(X)$?

  5. An unbiased die with 3 sides numbered 1, 2 and 3 is rolled once. If 1 appears, then another unbiased die with six sides is freshly rolled, else (if a 2 or a 3 appeared in the first roll of the first die) do nothing. (a) Write the sample space $S$ and the associated probabilities of all the outcomes of $S$. (b) What is the probability that a 4 appears in any of the rolls? (c) Let $V$ be the event that a prime number appears in any of the rolls. What is the probability of $V$? (d) What is the Shannon Entropy of this experiment?

  6. Experiment $X_1$ has an entropy of $H(X_1) = 5~shannons$, experiment $X_2$ has an entropy of $H(X_2) = 5~nats$ and experiment $X_3$ has an entropy of $H(X_3) = 3.5~trits$. Arrange these in descending order of entropies (justify your answer).