Solution: 2017 Fall 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 \neq b_{i+1}$.
What is the expected value $\mathbb{E}(X)$ of the random variable $X$?
Hint: Use indicator random variables.

(a)

$\frac{n-1}{2}$

(b)

$\frac{n+1}{2}$

(c)

None of the above.

(d)

$\frac{n}{2}$

Solution

All this to say that the current bit is different from the next bit

Let S be the set of all pairs of bits of length n
$ S = { (0,0), (0,1), (1,0), (1,1) } $
$ |S| = 4^n $
Let A be the event that the current bit is different from the next bit
$ A = { (0,1), (1,0) } $
$ |A| = 2 $
$ Pr(A) = \frac{2}{4} = \frac{1}{2} $

Since we’re considering the current bit and its next bit, we don’t consider the last bit since there’s no bit after the last bit

This means we have n-1 pairs

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

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

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

The expected value of X is $ \frac{n-1}{2} $