4
$\begingroup$

Let n ≥ 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 ≤ i < n and $a_i$ < $a_{i+1}$. Determine the expected value E(X) of X. (Hint: Use indicator random variables.)

This question seems to be over my head. Any help to lead in right direction is appreciated. Thank you.

$\endgroup$

2 Answers 2

2
$\begingroup$

Hint: write $X$ as a sum of indicator random variables, and use the fact that they are identically distributed.

$\endgroup$
1
  • 3
    $\begingroup$ The indicator variables are not independently distributed, but then independence is not required to use Linearity of Expectation. They are identically distributed though, and that makes the evaluation easy. $\endgroup$ Commented Apr 3, 2015 at 1:56
1
$\begingroup$

The indicator variables could be $X_{i}$ where $X_{i}=1$ if $a_i < a_{i+1}$ and 0 otherwise. Does $\mathbb{P}(X_{i}=1)$ depend on $i$? Then use linearity of expectation, i.e. $\mathbb{E}(X)=\mathbb{E}(\sum X_{i})=\sum \mathbb{E}(X_{i}) = \sum \mathbb{P}(X_{i}=1)$.

$\endgroup$

You must log in to answer this question.

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