I'm ultimately trying to compute the second moment of $X$, or $E[X^2]$. I don't see another way to do this other than to determine the probability distribution $P(X = k)$.
It seems to me that for each $U_i$ and its neighbors, it can take on $4$ positions being $1)\cdot ^{\cdot} \cdot$ $2) ^\cdot . ^\cdot$ $3) ^\cdot \cdot .$ and $4) .\cdot ^\cdot$. Basically peak, valley, middle decreasing and middle increasing. Therefore I think that $p(U_i \space is \space peak) = \frac14$. It is therefore my reasoning that $X$ is binomially distributed with parameter $p = \frac14$ of success, but I feel that there is something wrong as you can have at most $\frac{n}2$ peaks.
Can someone either point out my mistake, or point out a better way to calculate variance? Thank you
I think there are actually 6 positions. In your nomenclature of High (H), Medium (M), and Low (L), there are 3! = 6 ways of permuting the letters $H$, $M$ and $L$. Arguing by symmetry, the probability that $U_i$ is a peak is 1/3 since there's an equal chance that $U_{i-1}$, $U_{i}$, or $U_{i+1}$ is the largest of the 3.
Also, it's not binomially distributed with $p=1/3$ either since whether $U_i$ is a peak or not is not independent of $U_{i-1}$ and $U_{i+1}$. Conditioning on $U_{i-1}$ and $U_{i+1}$ large, the probability that $U_{i}$ is a peak is much less than 1/3.
As you suspected, you do not have to actually compute the distribution of $X$ to find $\mathbb{E}[X^2]$. Instead, you can exploit the linearity of expectation to bypass all the joint distribution intricacies. Write $X = \sum_{i=1}^N \mathbf{1}_i$ where $\mathbf{1}_i$ indicates whether $U_i$ is a peak or not. Then expanding, you end up having to compute terms like $\mathbb{E}[\mathbf{1}_i\mathbf{1}_j]$.