Solution: 2016 Fall Final - 19

Author: Michiel Smid

Question

Let $n \geq 2$ be an integer and let $a_1a_2 \dots a_n$ be a uniformly random permutation of the set $\{1,2,\dots,n\}$. Let $X$ be the random variable with the value

X = the number of indices $i$ with $1 \leq i \leq n - 1$ and $a_i < a_{i + 1}$.

For example, if $n = 6$ and the permutation is 3, 5, 4, 1, 6, 2, then $X = 2$.
What is the expected value $\mathbb{E}(X)$ of $X$?
Hint: Use indicator random variables.

(a)

$\frac{n}{2}$

(b)

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

(c)

$\frac{n}{4}$

(d)

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

Solution

Let $X_i$ be 1 if the next number is greater than the current number and 0 otherwise.

The probability that a random number is greater than the previous number is $\frac{1}{2}$

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

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

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

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