What is the chance of a sample in white noise to be a local extremum?

Question

I draw a long sequence of values from a uniform or normal distribution. Observing the resulting sequence, what is the chance of any point in the sequence (aside from the first and last where it is not defined) to be a local extremum? I.e. either a local maximum (the point is larger than both its neighbors) or a local minimum (the point is smaller than both its neighbors).

At first glance, you would think that once you've drawn the 1st point, the expectancy of the 2nd to be smaller\bigger than the 1st is 50% and then the 3rd is bigger\smaller in 50% hence 0.5*0.5 + 0.5*0.5 = 0.5 chance. However there is additional information in the 2nd point being larger than the 1st and hence a bigger (than 50%) chance that the 3rd point is also smaller than the 2nd.

A matlab code which calculates these chances result a chance of 2/3 (0.66%) :

sum(diff(sign(diff(normrnd(0,1,1,10000))))~=0)/10000 % Normal distribution
sum(diff(sign(diff(rand(1,10000))))~=0)/10000 % Uniform distribution

Iv'e tried to apply a combinatoric reasoning to explain this result : As being extremum is defined by 3 points only, let's narrow the problem to observe only 3 points. There are 6 possible orderings to 3 points, in 4 of which the second point is a local extremum, hence the 2/3 chance.

Is this a correct reasoning? Are there other better ways to approach the problem (Integrating the probability density function)?

Answer 1

I have only a partial theoretical answer, plus another numeric simulation.

As pointed out in a comment to Ian's answer, the solution does not depend on the distribution of the data (as long as it is continuous), so I'm simply using uniformly distributed data on [0, 1].

First, I can confirm that in simulations the expected frequency of local extrema appears to not depend on the length $n$ of sequences, and appears to be exactly 2/3. Here is Matlab code to demonstrate this:

N = 1e6; % number of realizations
n = 100; % length of sequence
ext = diff(sign(diff(rand(n, N)))) ~= 0; % extrema
mean(mean(ext))  % relative frequency across points, estimated expectancy across realizations

---

First, why exactly 2/3? As the original poster pointed out, the answer of course depends on the probability of occurrences of different orderings, for simplicity for $n = 3$. There are six such orderings: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1). Because the underlying three random variables are independent and identically distributed, any permutation of the three does not change their joint distribution. The probability distribution across orderings therefore has to be invariant under these permutations. This means this distribution must be uniform, and we therefore have a probability of 1/6 for each ordering.

Since four of the orderings lead to a local extremum, namely those with a 1 or a 3 in the middle position, we have a probability of 4/6 = 2/3 for a local extremum.

---

As pointed out by Ian, the same probability does not necessarily apply to the situation with $n > 3$. If there is a local maximum at one point, there cannot be a local maximum at each of the neighboring points, i.e. we have a negative local correlation w.r.t. the occurrence of a local maximum. It is however possible that there is a local minimum at the next position. I do not see a way to sort out these correlations theoretically, but I looked at them in the simulated data:

R = corr(ext');

The correlation matrix looks like this:

It appears that the autocorrelation is stationary. Averaging across diagonals we can extract the autocorrelation function

lags = -(n - 3) : n - 3;
r = nan(size(lags));
for k = 1 : numel(lags)
    r(k) = mean(diag(R, lags(k)));
end

with this result:

According to this we do have a small negative autocorrelation (-0.125) at lag 1, but an even smaller positive autocorrelation (0.025) at lag 2. Beyond that, correlations are smaller than $\pm$0.001. So my only guess is that the negative autocorrelation at lag 1 is somehow perfectly counterbalanced by the positive autocorrelation at lag 2 so that the average probability of occurrence of a local extremum stays at 2/3.

---

Generalization of the order-statistics approach: Just as we enumerated the possible orderings for $n = 3$ above, we can do so also for larger $n$ computationally, and then determine the probability of a local extremum under the assumption (following the same argument as above) that all orderings are equally possible. Here is an implementation in Matlab which uses the Symbolic Math Toolbox to perform exact arithmetic on rational numbers:

for n = 3 : 10
    uo = perms(1 : n);
    ext = diff(sign(diff(uo'))) ~= 0;
    ratio = sprintf('%d / %d', sum(sum(ext)), numel(ext));
    fprintf('%d :  %s =  %s\n', n, ratio, char(sym(ratio)))
end

The result is

3 :  4 / 6 =  2/3
4 :  32 / 48 =  2/3
5 :  240 / 360 =  2/3
6 :  1920 / 2880 =  2/3
7 :  16800 / 25200 =  2/3
8 :  161280 / 241920 =  2/3
9 :  1693440 / 2540160 =  2/3
10 :  19353600 / 29030400 =  2/3

The first number in the ratios is the number of local extrema, across all $n - 2$ positions and all $n!$ possible orderings, the second is the number of possible local extrema, $(n - 2) ~ n!$.

So now we have the computational but exact proof that the probability is exactly 2/3 for $n$ up to 10. Beyond that, the number of possible orderings becomes so large that it takes very long to evaluate.

I have the feeling this could lead to a proof by induction for arbitrary $n$, but do not know yet how to do so.

Answer 2

Some thoughts here:

Consider a sequence of $N$ iid random variables $X_i$. We have $N-2$ Bernoulli random variables $\{ B_i \}_{i=2}^{N-1}$ which are $1$ when $X_i$ is an extremum and $0$ otherwise. It is not immediately obvious that the $B_i$ are even independent; certainly the version where $B_i$ is $1$ when $X_i$ is a maximum are not independent! So there may be some nontrivial coupling to be considered here.

We can remove this coupling (if it exists) by restricting attention to the case $N=3$ for a moment. Denote the PDF of the variables separately by $f$. Then the probability that $B_2=1$ is

$$\int_{-\infty}^\infty \int_{-\infty}^\infty \int_{\max \{ x,z \}}^\infty f(x) f(y) f(z) dy dx dz + \int_{-\infty}^\infty \int_{-\infty}^\infty \int_{-\infty}^{\min \{ x,z \}} f(x) f(y) f(z) dy dx dz.$$

This can be simplified by splitting over which of $x,z$ is the maximum/minimum. In the uniform case it is straightforward to compute analytically.

In general this probability is not independent of the distribution used. For example, in the Bernoulli case, this quantity is $p^2(1-p)+p^2(1-p)=p-p^2$, so it is larger for $p$ closer to $1/2$. So while I think you are right that it is $2/3$ in the uniform case (I seem to recall a geometric proof that each of the $n!$ "ordered tetrahedra" of the $n$-cube have equal probability under the uniform distribution), I would expect it to be different in general.