Expected number of Good Pairs

Question

This is a question I had in my interview: we have $N$ i.i.d Uniform (0, 1) r.v., we define a good neighbor for x_i as the point that is closet to x_i in absolute value. We call a pair (x_i, x_j) as 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. Any ideas?

Answer 1

Any ideas?

Start by letting $G_{i,j}$ indicate that pair $(x_i,x_j)$ is good and then evaluate $\mathsf E(G_{i,j})$.

That is the probability that a specific pair is good. That none of the other $n-2$ samples are closer to either as they are to each other.

---

The expected count of good pairs is $\displaystyle\mathsf E\!\left(\sum\limits_{1\leq i\lt j\leq n}G_{i,j}\right)$ which equals $\dbinom n2\mathsf E(G_{1,2})$ due to Linearity of Expectation and the identicality of the distributions.