# Expected Value for uniform random permutations

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?

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?
• I've defined an indicator variable $I_1$ for the event $\{a_1 < a_2\}$, and so on for the other events $\{a_i < a_{i+1}\}$. This allows me to write $X$ as the sum of indicator variables. From there, calculating the expectation of $X$ reduces to computing the expectation of each indicator variable. Commented Dec 2, 2018 at 19:08