Solution: 2018 Fall Final - 14

Author: Michiel Smid

Question

Let $n$ and $k$ be integers with $1 \leq k \leq n$.
You are given two bitstrings $a_1,a_2,\dots,a_n$ and $b_1,b_2,\dots,b_n$ 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).
Consider the bitstring $$ a_1 \cdot b_1,a_2 \cdot b_2,\dots,a_n \cdot b_n $$ where $a_i \cdot b_i$ is the result of multiplying the two bits $a_i$ and $b_i$. What is the probability that this bitstring contains exactly $k$ many 1's?

(a)

${n \choose k} \cdot \left. 4^{n - k} \middle/ 3^k \right.$

(b)

${n \choose k} \cdot \left. 3^{n - k} \middle/ 4^n \right.$

(c)

${n \choose k} \cdot \left. 4^{n - k} \middle/ 3^n \right.$

(d)

None of the above.

Solution

Let’s see some products

$ 0 \cdot 0 = 0 $
$ 1 \cdot 0 = 0 $
$ 0 \cdot 1 = 0 $
$ 1 \cdot 1 = 1 $

Let $k$ be the number of 1s in this bitstring.

There are n positions and the probability of getting a 1 is $ \frac{1}{4} $

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

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

$ Pr(X=k) = \binom{n}{k} \frac{1^k \cdot 3^{n-k}}{4^n} $

$ Pr(X=k) = \binom{n}{k} \frac{3^{n-k}}{4^n} $