Question:
Let $n\geq 2$ be an integer and let $a_1, a_2, …, a_n$ be a uniformly random permutation of the set $\{1,2,…n\}$. Let $X$ be the random variable with 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 $E(X)$ of $X$? Use indicator variables.
Answer: $\frac{n-1}{2}$
I define my indicator variable:
$$
X = \left\{\begin{array}{rc} 1,&\text{the number of indices i with 1 $<=$ i $<=$ $n-1$ and $a_i < a_{i+1}$ }{} \\ 0,&\text{other cases}{}\end{array}\right.
$$
For $n=2$: {1,2} , {2,1} so $Pr = $ $\frac{1}{2}$
$E(X) =$ $P(X_2) =$ $\frac{1}{2}$
For $n=3$: {1,2, 3} , {1,3,2} , {2,3,1} so $Pr = $ $\frac{3}{6}$
Is this the correct method to solve this? I did this for $n$ values but when I computed there result with the answers, I never got it to be the same. How do I solve this?
Best Answer
If you define $$I_i = \begin{cases} 1 & a_i < a_{i+1} \\ 0 & a_i \ge a_{i+1}\end{cases}$$ for $1 \le i \le n-1$, then $X = I_1 + I_2 + \cdots + I_{n-1}$ so $$E[X] = E[I_1 + \cdots + I_{n-1}] = E[I_1] + \cdots + E[I_{n-1}] = P(a_1 < a_2) + \cdots + P(a_{n-1} < a_n).$$ Can you take it from here?