Solution: 2019 Winter Final - 20

Author: Michiel Smid

Question

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

(a)

$\frac{2}{3} \cdot n$

(b)

$\frac{4}{9} \cdot (n - 1)$

(c)

$\frac{2}{3} \cdot (n - 1)$

(d)

$\frac{4}{9} \cdot n$

Solution

Determine probability of $X_i$

Let $X_i$ be the 1 if $c_i \cdot c_{i + 1}$ is odd
- $1 \cdot 1$ is odd
- $1 \cdot 2$ is even
- $1 \cdot 3$ is odd
- $2 \cdot 1$ is even
- $2 \cdot 2$ is even
- $2 \cdot 3$ is even
- $3 \cdot 1$ is odd
- $3 \cdot 2$ is even
- $3 \cdot 3$ is odd
$X_i$ is odd with probability $\frac{4}{9}$
Profit

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

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

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