Solution: 2018 Winter Final - 20

Author: Michiel Smid

Question

Let $n \geq 2$ be an integer. You are given $n$ beer bottles $B_1,B_2,\dots,B_n$ and one cider bottle $C$. Consider a uniformly random permutation of these $n+1$ bottles. The positions in this permutation are numbered as $1,2,3,\dots,n+1$. Define the random variable $X$ to be

X = the position of the leftmost beer bottle.

What is the expected value $\mathbb{E}(X)$ of the random variable $X$?

(a)

(b)

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

(c)

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

(d)

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

Solution

Let $X_i$ be 1 if $C$ is not at position 1 and 2 if $C$ is at position 1

$ Pr(X_i=1) = Pr(\text{$B_i$ is at position 1}) = \frac{1}{n+1} $

$ Pr(X_i=2) = Pr(\text{$C$ is at position 1}) = \frac{1}{n+1} $

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

$ \mathbb{E}(X) = \sum_{k=2}^{n+1} 1 \cdot \frac{1}{n+1} + 2 \cdot \frac{1}{n+1} $

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

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

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

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