Peaking permutation

Solution 1: Consider any 3 distinct integers from the set $\{1,2,\ldots,n\}.$ There are $\binom{n}{3}$ ways to choose 3 such integers and there are $2$ ways to order them such that the larger one is first. There are $(n-2)!$ arrangements which will have this as a subsequence. Thus, over all $n!$ arrangements, there are $\binom{n}{3} \times 2 \times (n-2)!$ peaks. The expected number of peaks will be $\frac{n \times (n-1) \times (n-2) \times 2 \times (n-2)!}{6 \times n!} = \frac{(n-2)}{3}.$ When $n = 800$ this gives $\frac{798}{3} = 266.$

Solution 2: For $i = 1$ to $798$ , let $I_i$ be the indicator variable that the $i+1$ th position is a peak. Then $I_i$ is independent of all the other values, except that of $i, i+1, i+2$ . By considering all permutations of these values, we see that $E[I_i] = \frac{1}{3}$ . Hence, by linearity of expectation, the number of peaks is $798 E[I_i] = 266$ .