CMSC 27100 — Problem Set 7

Instructions

This problem set is due on Friday November 22, 2019 at 23:59. Solutions to Problems should be submitted on Gradescope and will be graded. Solutions to Exercises will not be graded and you should not submit them, although we will be happy to discuss them with you.

Problems

  1. Consider strings over the binary alphabet $\{0,1\}$. We say a string $x$ is compressible by $c$ if we can compress it into a string $x'$ of size at most $|x| - c$ and we can decompress $x'$ to recover $x$. We have seen in class that there must be strings which are incompressible by $c$; that is, there exist strings $y$ which cannot be compressed into strings of length $\leq |y| - c$.
    1. What is the probability that a string of length 31 is incompressible by 8?
    2. What is the probability that a string of length $n$ is incompressible by $c$?
  2. Consider strings of length 8 that are randomly generated over the binary alphabet $\{0,1\}$ and the following events: You may refer to solutions from the midterm or past problem sets for the sizes of these events.
    1. Compute $\Pr(A)$.
    2. Compute $\Pr(B)$.
    3. Compute $\Pr(A \mid B)$.
    4. Are these events independent? If not, are these events positively or negatively correlated?
  3. Suppose that $A,B \neq \emptyset$. Prove that if $\Pr(A \mid B) = \Pr(A)$, then $\Pr(B \mid A) = \Pr(B)$.
  4. Let $(\Omega,\Pr)$ be a probability space where $|\Omega|$ is prime and $\Pr$ is the uniform probability distribution on $\Omega$. Prove that no two non-trivial events can be independent.
  5. Suppose we are sending a message of length 12 one bit at a time over a noisy channel which has a $\frac 1 4$ chance of introducing error.
    1. What is the probability of at most one error being introduced?
    2. What is the probability that at least two errors are introduced?

Exercises

  1. Prove that $\Pr(\overline A) = 1 - \Pr(A)$.
  2. Prove that $\Pr(A \cap B \cap C) = \Pr(A \mid B \cap C) \cdot \Pr(B \mid C) \cdot \Pr(C)$.
  3. Rosen 7.1 Exercises 17, 19, 21
  4. Rosen 7.2 Exercises 7, 9, 11, 13, 31, 35