Solution: 2018 Winter Final - 19

Author: Michiel Smid

Question

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/4$

(b)

$3(n-1)/4$

(c)

$3n/4$

(d)

$(n-1)/4$

Solution

Let $X_i$ be 1 if $b_i \cdot b_{i+1} = 0$ and 0 otherwise. This only happens if a pair of consecutive bits contain a 0.

$ Pr(X_i = 1) = Pr{(b_i = 0 \text{ and } b_{i+1} = 1)} + Pr{(b_i = 1 \text{ and } b_{i+1} = 0)} + Pr{(b_i = 0 \text{ and } b_{i+1} = 0)} $

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

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

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

Since the last bit has no bit after it, we only take into account the first $n-1$ bits

$ \mathbb{E}(X) = \sum_{k=1}^{n-1} 1 \cdot Pr(X_i = 1) $

$ \mathbb{E}(X) = \sum_{k=1}^{n-1} \frac{3}{4} $

$ \mathbb{E}(X) = \frac{3}{4} \cdot (n-1) $

$ \mathbb{E}(X) = \frac{3(n-1)}{4} $