Math 480, Fall 2016, Assignment 14

I must study politics and war that my sons may have liberty to study mathematics and philosophy.

- John Adams, letter to Abigail Adams, May 12, 1780

Carefully define the following terms, then give one example and one non-example of each:

1. Mean (of a real-valued random variable).
2. Variance (of a real-valued random variable).
3. Standard deviation (of a real-valued random variable).
4. Typical sequence (your answer will be long and will involve a tolerance parameter $k$).

Carefully state the following theorems (you do not need to prove them):

1. Chebyshev's inequality.
2. Asymptotic equipartition theorem.

Solve the following problems:

1. Let $\mathscr{X}=\{h,t\}$ represent tosses of an unfair coin for which $P(h)=2/3$ and $P(t)=1/3$. Take $\epsilon=0.1$ and let $k$ have the smallest value consistent with this value of $\epsilon$.

(a) Compute $H(\mathscr{X})$, in bits (you may wish to use a calculator to make a decimal approximation).

(b) Find all typical sequences of length $6$.

(c) Compare the number of typical sequences to the estimate provided in the AET.

(d) If time permits, repeat this calculation with longer or shorter sequences, and with other values of $\epsilon$.

--------------------End of assignment--------------------