MPCS 50103 — Problem Set 7

Instructions

This problem set is due on Wednesday February 26, 2020 at 17:00. 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 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?
  2. 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.
  3. Consider a noisy channel which has a $\frac 1 4$ chance of introducing error (i.e. it sends the wrong bit). Suppose we send a stream of random bits through the channel with probability $\frac{7}{10}$ of sending a 0 and probability $\frac{3}{10}$ of sending a 1.
    1. What is the probability that a 0 is received?
    2. What is the probability that a 0 was sent, given that a 0 is received?
  4. The $GC$-content of a DNA string is the proportion of the string that is either a $G$ or $C$. More specifically, given a DNA string $w$, we define $$\mathbb{GC}(w) = \frac{|w|_G + |w|_C}{|w|},$$ where $|w|$ is the number of symbols in the string $w$, $|w|_G$ is the number of $G$s in $w$, and $|w|_C$ is the number of $C$s in $w$. Suppose we generate a random DNA string $w$ of length $n$ with the following probabilities for each symbol: $$\begin{matrix} \Pr(A) = 0.4 & \Pr(C) = 0.1 & \Pr(G) = 0.3 & \Pr(T) = 0.2 \end{matrix}$$ What is the expected $GC$-content of the string $w$?

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. Suppose that $A,B \neq \emptyset$. Prove that if $\Pr(A \mid B) = \Pr(A)$, then $\Pr(B \mid A) = \Pr(B)$.
  4. Prove that if $X$ and $Y$ are independent random variables, then $$E(X \cdot Y) = E(X) \cdot E(Y).$$
  5. Rosen 7.1 Exercises 17, 19, 21
  6. Rosen 7.2 Exercises 7, 9, 11, 13, 31, 35
  7. Rosen 7.3 Exercises 9, 11, 13, 19, 21, 23