Solution: 2018 Winter Final - 14

Author: Michiel Smid

Question

You are given two bitstrings $a_1,a_2,\dots,a_{77}$ and $b_1,b_2,\dots,b_{77}$ of length 77. In both bitstrings, each bit is 0 with probability 3/4, and 1 with probability 1/4 (independent of all other bits).
Consider the string $$ a_1-b_1,a_2-b_2,\dots,a_{77}-b_{77}. $$ What is the probability that each element in this string is non-zero?

(a)

$(6/8)^{77}$

(b)

$(3/8)^{77}$

(c)

$(5/8)^{77}$

(d)

$(4/8)^{77}$

Solution

The difference in string $a-b$ is non-zero at each position only if $a_i$ is 1 and $b_i$ is 0 or $a_i$ is 0 and $b_i$ is 1, for all $1 \leq i \leq 77$

Let $X_i$ be 1 if $a_i$ and $b_i$ are different and 0 otherwise

$ Pr(X_i = 1) = \frac{1}{4} \cdot \frac{3}{4} + \frac{3}{4} \cdot \frac{1}{4} $

$ Pr(X_i = 1) = \frac{3}{16} + \frac{3}{16} $

$ Pr(X_i = 1) = \frac{6}{16} $

$ Pr(X_i = 1) = \frac{3}{8} $

The probability that each element in the string is non-zero is the probability that each element is different

$ \frac{3}{8} \cdot \frac{3}{8} \cdot \text{…} \cdot \frac{3}{8} $

$ = {( \frac{3}{8})}^{77} $