3
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.