0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ I'm kind of lost on what you are doing. Can you please elaborate. $\endgroup$
    – Toby
    Commented Dec 2, 2018 at 19:00
  • $\begingroup$ 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. $\endgroup$
    – angryavian
    Commented Dec 2, 2018 at 19:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .