Expected number of overlaps between intervals

Question

Suppose $N$ intervals of length $\delta$ are positioned in $[0,1]$. The starting point $l_i$ of each interval is drawn from an uniform distribution, i.e., $l_i \in [0, 1-\delta]$, thus it will determine the position of the $i$-th interval.

These intervals may overlap at some point in $[0,1]$. I call "overlap" each superimposition of an interval over another interval.

E.g. A = [0, 0.2] B = [0.1, 0.3] C = [0.25 0.45]. Number of overlaps = 2 (A with B, B with C)

Since an overlap occurs between a pair of intervals, $\frac{N(N-1)}{2}$ is the maximum number of overlaps.

I would like to compute the expected number of overlaps between the intervals in $[0,1]$.

Answer 1

This answer is not complete, hopefully it leads somewhere.

Select 2 intervals $[x_1-{\delta\over2},x_1+{\delta\over2}]$, $[x_2-{\delta\over2},x_2+{\delta\over2}]$ with $x_2\ge{x}_1$ and $\delta\le{1\over2}$.

There are 3 regions (non-contigous and possibly empty) in $[0,1]$, a region clear of intervals, a region with 1 interval and a region with 2 intervals.

Now if $x_2-x_1\gt{\delta}$ $(p=?)$, then the intervals are

$$[0,x_1-{\delta\over2}], [x_1+{\delta\over2},x_2-{\delta\over2}], [x_2+{\delta\over2},1]$$

$$[x_1-{\delta\over2},x_1+{\delta\over2}], [x_2-{\delta\over2},x_2+{\delta\over2}]$$

$$[\phi]$$

respectively. And if $x_2-x_1\le{\delta}$ $(q=1-p)$, then the intervals are

$$[0,x_1-{\delta\over2}], [x_2+{\delta\over2},1]$$

$$[x_1-{\delta\over2},x_2+{\delta\over2}]$$

$$[x_2-{\delta\over2},x_1+{\delta\over2}]$$

respectively.

What happens when you add $[x_3-{\delta\over2},x_3+{\delta\over2}]$ with $x_3\ge{x}_2$?

Can you generalise this for $x_{n}$?

Remember the order of selection is not important so you can always reorder so that $x_1\le{x}_2\le{...}\le{x}_n$.

Further thoughts

I think this can be attacked from the other end.

Given a collection of $n$ points in the interval $[\delta,1-\delta]$, what is the probability distribution for the length of $x_n-x_1$?

This may be non-trivial but given the degree of fredom aspect, is it a $t$-function? I have asked this question to clarify this.

With that in hand, $P(overlaps=n)=P(x_n-x_1\le\delta)$.

Then eliminate $x_n$ and consider the interval $[x_1,x_{n-1}]$, then $p(overlaps=n-1)=P(x_{n-1}-x_1\le\delta|x_n-x_1\gt\delta)$, and so on.

By the way, the minimum number of overlaps is 0 or $n-{1\over\delta}$

Answer 2

Let $E_n$, $n=1,2,\ldots, N$ be an arbitrary but finite number of intervals of length $\delta$ in $[0,1]$.

For each $\alpha\in [0,1]$ let $f(\alpha) = \sum_{i=1}^n \chi_{E_n}(\alpha)$. For each $\alpha$, $f(\alpha)$ is the number of overlaps at $\alpha$ of the intervals.

Notice that $\int_0^1 f(\alpha) = n\delta$.

Answer 3

I found a reference where it is stated that: "To compute the expected number of intersections, use the fact that expectation is additive. The expected number of intersections is just $\binom{N}{2}p$ where $p$ is the probability of an intersection".

(To be honest, I can't figure out why $\binom{N}{2}p$ is the expected number. I ask you some suggestions in the comments. I tried with a Monte Carlo simulation and it seems to work fine.)

Then the probability $p=P(|l_i - l_j| < \delta)$ of having one intersection is computed as the portion of the area of the square $[0,1-\delta]\times[0,1-\delta]$ between the curves: $l_i - l_j > \delta$ and $l_i - l_j > -\delta$, and it is equal to: $$ P(|l_i - l_j| < \delta) = \frac{2\delta-3\delta^2}{(1-\delta)^2} $$