Solution: 2018 Fall Final - 19

Author: Michiel Smid

Question

Let $n \geq 2$ be an integer. Consider a string $c_1,c_2,\dots,c_n$ of length $n$, in which each character $c_i$ is a uniformly random element of the set $\{\alpha, \beta, \gamma, \delta, \epsilon\}$ (independently of all other characters).
Define the random variable $X$ to be the number of indices $i$ with $1 \leq i < n$ for which $c_i = c_{i+1}$.
What is the expected value $\mathbb{E}(X)$ of the random variable $X$?
Hint: Use indicator random variables.

(a)

$\left. n \middle/ 25 \right.$

(b)

$\left. (n - 1) \middle/ 5 \right.$

(c)

$\left. n \middle/ 5 \right.$

(d)

$\left. (n - 1) \middle/ 25 \right.$

Solution

Let $X_i$ be 1 if $c_i = c_{i+1}$ and 0 otherwise

So $c_i$ can be any of the 5 characters, but $c_{i+1}$ needs to follow after $c_i$. It has a 1 in 5 chance of being the same character: $ \frac{1}{5} $

We do this for every value from 1 to n-1. We exclude n because there is not value that comes after the last value: $ (n-1) $

$ \mathbb{E}(X) = \mathbb{E}(X_1 + X_2 + \text{…} + X_{n-1}) $

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

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

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