3
$\begingroup$

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 ?

$\endgroup$
0

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ The last step should be $1+\frac{1}{2} + \cdots + \frac{1}{n}$? $\endgroup$
    – angryavian
    Feb 28, 2021 at 7:27
  • $\begingroup$ Absolutely, thank you. $\endgroup$
    – user801306
    Feb 28, 2021 at 7:29
2
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

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