# Probability that position $i$ is a peak in $\sigma$, where $\sigma$ be a uniformly random permutation of $\{1,\ldots,n\}$

Let $$\sigma$$ be a uniformly random permutation of $$\{1,\ldots,n\}$$. That is $$\sigma(1),\sigma(2),\ldots, \sigma(n)$$ is a permutation and it is chosen uniformly from one of the $$n!$$ permutations. Position $$i$$ is a peak in $$\sigma$$ if $$\sigma(i)$$ is the maximum number amongst $$\sigma(1),\sigma(2),\ldots,\sigma(i)$$. For instance if $$\sigma$$ is the permutation $$3,4,1,2,5$$ then positions $$1,2,5$$ are peaks and positions $$3$$ and $$4$$ are not. Note that position $$1$$ is always a peak. Let $$\sigma$$ be a uniform random permutation of $$\{1,2,\ldots,n\}$$.

1.What is the probability that position $$i$$ is a peak in $$\sigma$$?

2.What is the expected number of peaks in $$\sigma$$?

Here's what I got so far, I'm not sure whether it is right or not.

So, I know $$i$$ is a peak in $$\sigma$$ if and only if $$\sigma(i) > \sigma(i-1), \sigma(i) > \sigma(i-2), \ldots, \sigma(i) > \sigma(1)$$. And thus, I set an indicator random variable $$M_{ij}= \begin{cases} 1 & , \ if \ \sigma(i) > \sigma(j)\\ 0 & , \ otherwise \end{cases}$$

And, set $$X_{i} = \sum_{j=1}^{i-1} M_{ij}$$.

Thus, $$P(i \ is \ a \ peak) = P(X_{i} =i-1) = P(M_{i1} =1, M_{i2}=1,\ldots, M_{i,i-1}=1)$$

Since $$P(M_{i1} =1) = \frac{number \ of \ elements \ j \ such \ that \ \sigma(j) < \sigma(i)}{n} = \frac{\sigma(i)-1}{n}$$. After we pick the first element, there is only $$\sigma(i)-2$$ choices left for second element, so $$P(M_{i2} =1) = \frac{\sigma(i)-2}{n-1}$$, and so on, up to $$i-1$$ term.

Thus, $$P(M_{i1} =1, M_{i2}=1,\ldots, M_{i,i-1}=1) = \frac{\sigma(i)-1}{n} \times \frac{\sigma(i)-2}{n-1} \times \ldots \times \frac{\sigma(i)-(i-1)}{n- (i-2)} = \prod_{j=1}^{i-1} \frac{\sigma(i) -j}{n- (j-1)}$$?

I was wondering is $$\prod_{j=1}^{i-1} \frac{\sigma(i) -j}{n- (j-1)}$$ the correct probability or not?

And, I was wondering if the above analysis is in the right direction or does it have a better way to do it ?

Let's count the number of permutations of $$1,\ldots,n$$ in which position $$i$$ is a peak. Suppose $$k=\sigma(i)\in\{i,\ldots,n\}$$ is the number filling the $$i^{\text{th}}$$ position of your permutation $$\sigma$$. If $$\sigma(i)$$ is in fact a peak, then the previous $$i-1$$ elements of $$\sigma$$ must belong to the set $$\{1,\ldots,k-1\}$$. There are $${k-1 \choose i-1}(i-1)!$$ ways to fill in these preceding $$i-1$$ entries and $$(n-i)!$$ ways to fill in the remaining $$n-i$$ entries. Therefore, the probability that position $$i$$ is a peak equals $$\frac{ \sum_{k=i}^n{k-1 \choose i-1}(i-1)!(n-i)!}{n!}=\frac{1}{i}$$ Now let $$X_i=1$$ if $$\sigma(i)$$ is a peak and $$X_i=0$$ else. Set $$X=X_1 + \dots + X_n$$. Then $$X$$ counts the numbers of peaks of $$\sigma$$ and for each $$1 \leq i \leq n$$ $$\mathbb{E}(X_i)=P(X_i=1)=\frac{1}{i}$$ Finally, $$\mathbb{E}(X)=\sum_{i=1}^n\mathbb{E}(X_i)=1+\frac{1}{2}+\dots + \frac{1}{n}$$ Thank you @angryavian for the correction.
• The last step should be $1+\frac{1}{2} + \cdots + \frac{1}{n}$? Feb 28, 2021 at 7:27
Matthew Pilling's approach is correct. I just want to mention a slightly easier way to get $$P(\text{i is a peak})=1/i$$.
Conditioned on knowing what $$\sigma(i+1),\ldots, \sigma(n)$$ are, the distribution of $$\sigma(1),\ldots, \sigma(i)$$ is a uniform permutation of $$i$$ distinct numbers (namely, the $$i$$ numbers not equal to $$\sigma(i+1),\ldots, \sigma(n)$$). The largest of these $$i$$ numbers is equally likely to be in any of the $$i$$ positions, so in particular it has a $$1/i$$ chance of being in the $$i$$th position, which is the condition for making $$\sigma(i)$$ a peak. Since we know $$P(\text{i is a peak} \mid \sigma(i+1)=s_{i+1}, \ldots, \sigma(n) = s_n)=1/i$$ no matter what the last $$n-i$$ terms are, the unconditional probability $$P(\text{i is a peak})$$ is also $$1/i$$.