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!
Hi, may be I do not understood the problem but what about the following sequence of the 14 numbers which has 7 numbers that are strictly major of their adiacente numbers ?
2 1 4 3 6 5 8 7 10 9 12 11 14 13
Many thanks in advance for your answer