Solution: 2019 Winter Final - 14

Author: Michiel Smid

Question

Let $n$ and $k$ be integers with $0 \leq k \leq n$.
You are given two bitstrings $a_1,a_2,...,a_n$ and $b_1,b_2,...,b_n$, both of length $n$. In both bitstrings, each bit is 0 with probability 1/2, and 1 with probability 1/2 (independent of all other bits).
For each $i$ with $1 \leq i \leq n$, let $c_i = a_i - b_i$. Consider the set $$ P = \{i : 1 \leq i \leq n \text{ and } c_i \geq 0\}. $$ What is the probability that the size of the set $P$ is equal to $k$?

(a)

${n \choose k} \cdot (3/4)^{n - k} \cdot (1/4)^k$

(b)

${n \choose k} \cdot (3/4)^k \cdot (1/4)^{n - k}$

(c)

${n \choose k} \cdot (3/4)^k \cdot (1/2)^k$

(d)

None of the above.

Solution

The probability that $c_i \geq 0$ is $ \frac{3}{4} $

$X \sim \text{Binomial}(n,3/4)$

$P(|P| = k) = \binom{n}{k} \left(\frac{3}{4}\right)^k \left(\frac{1}{4}\right)^{n-k}$