Question: 2017 Fall Final - 14
Let $n \geq 1$ be an integer. 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 string $$ a_1 + b_1,a_2 + b_2,\dots,a_n + b_n. $$ What is the probability that each element in this string is non-zero?
Consider the string $$ a_1 + b_1,a_2 + b_2,\dots,a_n + b_n. $$ What is the probability that each element in this string is non-zero?
(a)
$(1/4)^{n}$
(b)
$1 - (1/4)^{n}$
(c)
$1 - (3/4)^{n}$
(d)
$(3/4)^{n}$