Back

Question: 2018 Winter Final - 19

Author: Michiel Smid
Let $n \geq 2$ be an integer. Consider a bitstring $b_1,b_2,\dots,b_n$ of length $n$, in which each bit $b_i$ is 0 with probability 1/2, and 1 with probability 1/2 (independent of all other bits).
Define the random variable $X$ to be the number of indices $i$ with $1 \leq i < n$ for which $b_i \cdot b_{i+1} = 0$.
What is the expected value $\mathbb{E}(X)$ of the random variable $X$?
Hint: Use indicator random variables.
(a)
$(n-1)/4$
(b)
$3n/4$
(c)
$n/4$
(d)
$3(n-1)/4$