Local Maximas of various Permutations!

Key idea : Probabilistic Method and Linearity of expectation

Details: Assume that we generate a permutation uniformly at random from the set of all permutations of $\{1,2,\ldots, n\}$ . Let $I_k$ denote the indicator variable that the $k$ th position in the permutation is a local maxima. Then it is clear that $\mathbb{P}(I_1=1)=\mathbb{P}(I_n=1)=\frac{1}{2}$ and $\mathbb{P}(I_m=1)=\frac{1}{3}, \forall m \neq 1,n$ The last equation follows because given any three distinct numbers, there are two ways in which we can arrange them (out of total six ways) such that the maximum number appears at the middle.

Hence if the random variable $M$ denotes the number of local maxima in a given permutation then $M=\sum_{k=1}^{n}I_k$

Note that the random variables $\{I_k\}$ are mutually dependent. However, the linearity of expectation holds and we have $\mathbb{E}M=\sum_{k=1}^{n}\mathbb{E}I_k=\sum_{k=1}^{n}\mathbb{P}(I_k=1)=2. \frac{1}{2}+(n-2)\frac{1}{3}=\frac{n+1}{3} \hspace{5pt} \blacksquare$

The general formula for the average number of local maxima over the set of permutations of $A_n=\{1, 2, \dots , n\}$ is $\frac{n+1}{3}$ .

This can be proved formally by induction, but I won't write out the whole proof here. By looking at the case moving from $n = 3$ to $n=4$ , we can gain a little intuition about how to count these maxima.

There are 6 ways to permute $A_3$ ; four of them result in one local maximum (i.e. 2 and 3 are adjacent) and the other two result in two local maxima (i.e. 1 is between 2 and 3). It should be clear that to get all 24 of the permutations of $A_4$ , we must "insert" the number 4 somewhere into one of the permutations of $A_3$ : this is because for each of the six permutations of $A_3$ , we can insert 4 in four different positions, and each of these must result in a distinct permutation of $A_4$ (why?).

Considering only the permutations of $A_3$ with one local maximum, we know that when we insert 4 ANYWHERE, it will be a local (in fact, absolute) maximum. However, not all of the available places for 4 will result in an additional local maximum. In fact, it's easy to see that out of the four slots available for inserting 4, exactly two of them will create a permutation of $A_4$ with two local maxima, and the other two will create a permutation of $A_4$ with only one local maximum. So, out of the 16 such permutations, exactly 8 will have two maxima, and the other 8 will have one maximum.

Now considering only the permutations of $A_3$ with two local maxima, we can see that no matter where we place the 4, we will always have two local maxima in our new larger permutation. So, out of the remaining 8 possible permutations of $A_4$ , each has 2 local maxima.

In total, we have an average of $\frac{16*2+8}{24} = \frac{5}{3}$ local maxima over all permutations of $A_4$ . This same reasoning can be used in an induction proof for the general formula. I'd love to see a full solution typed up, but I'm on my phone so this was already pretty taxing X-p

Sweet problem!!