# Expected number of "local maxima" in an integer sequence

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 kth best overall})\ P(\text{item i is a local max | integer i is the kth best overall)}$$

## 1 Answer

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.