0
$\begingroup$

I have come across this question in the context of the secretary problem.

Definition of a "local maximum" at position i: All integers 1,...,i-1 are less than the integer at position i.

Given a random permutation of integers 1, 2, 3, …, n with a discrete, uniform distribution, find the expected number of local maxima (according to the above definition).

My approach was to define an indicator random variable:

$$I_i = \begin{cases} 1 &\text{integer $i$ is greater than all previous integers} \\ 0 &\text{else} \end{cases}$$

Then we are looking for

$$E\left[\sum_{i=1}^{n} I_i \right ] = \sum_{i=1}^{n} E[I_i] = \sum_{i=1}^{n}P(I_i=1).$$

Furthermore I was able to decompose the probability further, but it hasn't let me anywhere:

$$P(I_i = 1) = \sum_{k=i}^{n} P(\text{integer $i$ is the $k$th best overall})\ P(\text{item $i$ is a local max | integer $i$ is the $k$th best overall)}$$

$\endgroup$

1 Answer 1

1
$\begingroup$

So let's divide the probability $P( I_i = 1 )$ into$$P( I_i = 1 ) = P \big( \{ n_i \ge i \} \cap \{ I_i = 1 \}\big) + P \big(\{ n_i < i\} \cap \{ I_i = 1\} \big) .$$The second one is $=0$ because if $n_i<0$ there are not $i-1$ numbers which are smaller than $n_i$ to fill the positions $1 , \ldots , n_{i-1}$. So we can continue with the probability $P\big( \{I_i = 1 \} ~ \vert ~ \{ n_i \ge i \} \big)$. For this we need to know what the probability is to draw $i-1$ numbers ($1 , \ldots , n_{i-1}$) from $\{1, \ldots , n\} \setminus \{n_i\}$ and that all of those are in $\{1,\ldots , n_i-1\}$. The probability for that is $\frac{\binom{n_i-1}{i-1}}{\binom{n-1}{i-1}} .$We also have to account for the order in which these can be and furthermore for the order of the $n-(i-1)$ left numbers, which we don't cared about so far, but which also need to be considered to know the whole permutation, so in total for that we get $$\frac{\binom{n_i-1}{i-1}}{\binom{n-1}{i-1}} \cdot (n-1)! .$$Combining that with $P(n_i \ge i ) =\frac{n-(i-1)}n$ we get$$P(I_i = 1 ) = P\big( \{I_i = 1 \} ~ \vert ~ \{ n_i \ge i \} \big) = \frac{\binom{n_i-1}{i-1}}{\binom{n-1}{i-1}} (n-1)! \cdot \frac{n-(i-1)}n .$$This probably can be simplified.

$\endgroup$

You must log in to answer this question.

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