1
$\begingroup$

Let $a_1,a_2 ,... a_n$ be a permutation of 1 to $n$. We define sequence $b = b_1 , b_2 ,... ,b_n$ as $b_i = max ~~{a_1,a_2,...a_i}$. Find Expected Value of $X$: distinct numbers in $b_i$.

For example if the permutation is $1, 3, 2$ then $b = 1,3,3$ so X is 2. (i.e 1 and 3 are distinct numbers). Another example: for permutation $1 , 3 , 4 ,2$ we have $b = 1,3,4,4$ so $X = 3$.

If we do this for all permutations of 1 to 3, we get sum of distinct numbers in $b$: $11$. For permutation of $1$ to $4$, it is $50$. So expected values are $11/6$ and $50/24$ respectively.

But I cannot find the pattern in this to find the answer for general case $n$. I tried to use an indicator variable $ I_i = \begin{cases} 1, & \text{if $i$ appears in position $1$ to $i$} \\[2ex] 0, & \text{o.w} \end{cases} $

And tried to define $X_ = \sum I_i$ but I found out this is not correct.

So I want help for this question. This problem is probably related to linearity of expectation.

$\endgroup$

1 Answer 1

3
$\begingroup$

Let $I_i$ be the indicator variable that $a_i = b_i$, namely that $a_i$ is the maximum of the first $i$ values of the permutation.

Hint: Show that $X = \sum I_i$.

Hint: Show that $ E[I_i] = \frac{1}{i}$.

Hence, $ E[X] = \sum_{i=1}^n \frac{1}{i}$.
This agrees with the $n=3, 4$ cases that you calculated.

$\endgroup$

You must log in to answer this question.

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