Expected time until the range halves

Question

Let look at the next model:

We start with with $n$ points in the interval $[-1,1]$, with each point being set uniformly and independently in the range. At discrete times two points are picked at random and moved to their mean location [e.g. if we pick $-0.6$ and $0.4$, both are moved to $(-0.6 + 0.4) / 2 > = -0.1$].

I'm interested in estimating

the time it takes the system to get to half the initial range,

i.e. to the interval of length $1$ [or may be more correctly to $1 - \frac{1}{2n}$.

My thoughts: I want to look at the range length decrease at one time step. Each pair of points could be picked with the same probability, namely $\frac{1}{n \choose 2} \approx \frac{2}{n^2}$. If none of the edge points picked - there is no decrease at all. If any, except the closest to the edge and the second edge point picked, than the decrease is the whole $\frac{1}{n}$ - the distance to the closest point. If closest point picked, than we expect the range to decrease by $\frac{1}{2n}$ and in case both edge points picked by $\frac{2}{n}$. All in all $$\mathbb{E}(\text{decrease}) = \frac{1}{n \choose 2}\left[\left((n - 3)\cdot\frac{1}{n}+1\cdot\frac{1}{2n}\right)\times 2 + 1\cdot \frac{2}{n}\right]=\frac{4n-6}{n^2(n-1)} \approx \frac{4}{n^2}$$ I'm willing to admit I'm in doubt whether should I multiply by two the above result. [It should be multiplied by initial length of interval containing all the points, though]

Now, it seems that further steps are kind of scaled version of the first step. So starting with the interval of length $x$ we expect interval to shrink to $(1 - \frac{4}{n^2})x$ in one step. Hence, after $k$ steps we have an expected length of $\left(1-\frac{4}{n^2}\right)^kx$, which we solve for $k$ from: $$\left(1-\frac{4}{n^2}\right)^kx = \frac{1}{2}x,$$ so $$ k = \frac{\log \frac{1}{2}}{\log\left(1 - \frac{4}{n^2}\right)} \approx \frac{-\frac{1}{2} -\frac{1}{8} - \frac{1}{24}}{-\frac{4}{n^2} - \frac{8}{n^4}} = \frac{-\frac{2}{3}n^4}{-4(n^2-2)} \approx \frac{1}{6}n^2$$

This whole reasoning fails remarkably on numerical simulations, see my humble attempts to plot time vs. $n$. Except for small $n$ the plot seems pretty linear (done for $n = 2:100:1000$, averaged for $1,000$ runs).

UPDATE: I've run more simulations, so the @joriki's answer now make more sense.

Answer 1

You originally leave the “discrete times” at which the operations occur undetermined, but your later calculations seem to imply that you take the operations to be performed at regular intervals, which we can without loss of generality assume to be unit intervals.

The later steps aren't scaled versions of the first step. The whole thing is rather complicated, since you get a random mixture of points that have already been averaged and those that haven't. I think the following model is more useful to get approximations for the expected number of operations required.

Half the points already start out in the interval $[-\frac12,\frac12]$, and most of the other half of the points will only require a single averaging operation to get there. Then the problem becomes a coupon collector's problem: You want $\frac n2$ points to be averaged at least once, and on average you select one of them per operation (since you select two points and half of them need to be averaged), so according to the standard solution of the coupon collector's problem, you expect to require $mH_m\approx m\ln m$ operations, with $m=\frac n2$. That fits reasonably well with your graph; e.g. at $n=900$, you need about $3300$ operations, and the estimate yields $450\ln450\approx2749$. The rest is due to the fact that some points need to be averaged more than once, so you could try to improve the approximation by modelling the fraction that do.