# Expected Number of Good Pairs

This is a question I had in my interview: we have $$N$$ i.i.d Uniform$$(0, 1)$$ random variables. Define a good neighbor for $$x_i$$ as the point that is closest to $$x_i$$ in absolute value. We call a pair $$(x_i, x_j)$$ a good pair if $$x_i$$ is $$x_j$$'s good neighbor and $$x_j$$ is $$x_i$$'s good neighbor. What's the expected number of good pairs?

The order statistics $$x_{(1)}\le x_{(2)} \le \cdots \le x_{(N)},$$ when suitably scaled, have iid exponential gaps $$y_i = x_{(i+1)} - x_{(i)},$$ and those gaps are the distances between neighboring points. A "good" gap is one that is smaller than the gaps immediately before and after it.
There are $$2$$ gaps with only one adjacent gap (namely, $$y_1$$ and $$y_{N-1}$$). The chance that such a gap is smaller than its neighbor is $$1/2$$ because the two values are iid (and continuously distributed). Otherwise the chance a gap is smaller than two neighboring gaps is $$1/3,$$ for a comparable reason. There are $$N-3$$ such gaps. Therefore the expectation is
$$2\left(\frac{1}{2}\right) + (N-3)\left(\frac{1}{3}\right) = \frac{N}{3}.$$
This analysis provides an unexpected detail: except for the pairs of points at the ends of the interval (each of which has a $$1/2$$ chance of being good), every other adjacent pair has a $$1/3$$ chance to be good.