0

Let $n \geq 1$ be an integer and consider a uniformly random permutation $a_1, a_2, ... , a_n$ of the set $\{1, 2, . . . , n\}$. Define the random variable X to be the number of indices $i$ for which $1 \leq i < n$ and $a_i < a_{i+1}$. Determine the expected value $E(X)$ of $X$. (Hint: Use indicator random variables.)

Not sure how to go about starting this off as I don't know how to find $E(X)$ of $X$. Thanks for all help :)

Pedro
  • 983
  • 1
  • 6
  • 19
user3373360
  • 1

2 Answers2

1

Hint:

For $i\in\{1,2,\dots,n-1\}$ let $X_i$ take value $1$ if $a_i<a_{i+1}$ for random permutation $a$ and takes value $0$ otherwise. Then $$X=X_1+\cdots+X_{n-1}$$ and by linearity of expectation we find: $$\mathbb EX=\mathbb EX_1+\cdots+\mathbb EX_{n-1}$$ Now release symmetry from its cage.

drhab
  • 151,093
1

Define indicator value $I_i = 1$ iff $a_i < a_{i+1}$ and $0$ otherwise.

$E[X] = E[I_1+I_2+\ldots+I_{n-1}] = \sum_iP[X_i=1]$

Now $a_i<a_{i+1}$ and $a_i > a_{i+1}$ are equally likely.

$E[X] = \frac{n-1}{2}$

Saket Choudhary
  • 958