Number of Maximas

Interesting puzzle asked in HRT interview

14 pieces of paper labelled 1−14 are placed in a line at random. Spot 𝑖 is a local maximum if the paper at the 𝑖th position is strictly larger than all of it's adjacent papers. Find the expected number of local maxima in the sequence. For example, with 6 numbers, 513246 has 3 local maxima at the first, third, and last spots.

Try to solve this problem yourself before moving on to the solution below

.
.
.

.

.

.

---

Solution

Let 𝐼𝑗 be the indicator random variable indicating whether the 𝑗'th number in the list is a local maximum, where 1≤𝑗≤14. Then, 𝑇=𝐼_1+...+𝐼_14 gives the total number of local maxima.

By linearity of expectation, 𝐸[𝑇]=𝐸[𝐼_1]+...+𝐸[𝐼_14]. Recall that the expected value of an indicator random variable is the probability of the event it indicates, meaning 𝐸[𝐼_𝑗]=𝑃[𝐼_𝑗=1].For spots 2≤𝑗≤13, there are numbers at both spots 𝑗−1 and 𝑗+1. 𝐼_𝑗=1 when the 𝑗'th number is strictly bigger than the (𝑗−1)'th and the (𝑗+1)'th number. Out of the 3! ways to arrange the (𝑗−1)'th, 𝑗th, and (𝑗+1)'th numbers, only 2 of the arrangements form a local maximum. For example, if the three numbers are 123, then the only arrangements which form a local maximum at the second spot are 213 and 312. Thus, the expected value of 𝐼𝑗​ is 𝐸[𝐼𝑗]=2/3!=1/3 ​.

For spot 𝑗=1, there is only one adjacent number at spot 2, since 𝑗=1 is an endpoint. Out of the 2! ways to arrange the numbers at spots 1 and 2, only 1 of the arrangements forms a local maximum.

Thus, 𝐸[𝐼1]=1/2!=1/2 ​. Applying the same logic to the other endpoint at 𝑗=14, 𝐸[𝐼_14]=1/2

​Therefore, 𝐸[𝑇]=1/2⋅2+1/3⋅12=5

.

.

😃 Over to you: Were you able to solve this?

---

👉 If you liked this post, don’t forget to leave a like ❤️. It helps more people discover this newsletter on Substack and tells us that you appreciate solving these weekly questions. The button is located towards the bottom of this email.

👉 If you love reading this newsletter, feel free to share it with friends!