# Expected number of overlaps between intervals

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]$.

-
Please, state the distribution of $m_i$ is uniform - without loss of generality it can be on $[0,1]$ again. I suggest also that we delete our comments, as they're all now incorporated in OP. I still suggest you trying induction over $n$ – Ilya Jan 14 '13 at 9:45
The $N$ distributions look like an unnecessary complication; the problem would be essentially the same if they were just intervals, right? – joriki Jan 14 '13 at 11:18
"The starting point of each interval is drawn from an uniform distribution" I surmise, uniform in $[0,1-\delta]$? "number of overlaps" is an ambiguous expression for me (if two intervals coincide, is that 1 overlap or 2? if three intervals coincide, is that 2 or 3?), perhaps it would be clearer to count "isolated intervals". – leonbloy Jan 14 '13 at 12:25
Why is the problem in the last paragraph equivalent? Shouldn't the overlaps get less probable if the midpoints are drawn from $[0,1]$ instead of $[0,1-\delta]$? – joriki Jan 14 '13 at 13:41
@Eleanore: "if three of them overlap that is a pair of overlaps" Now I'm even more confused. Take A=[.1 .4] B=[.2 .5] C=[.3 .6] I don't know if you'd count that as "one pair", two overlaps or three – leonbloy Jan 14 '13 at 13:41

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}$

-

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$.

-
May I ask you to explain your solution? What is $\chi$? – Eleanore Jan 15 '13 at 14:27
The characteristic function of the interval: $\chi_E(\alpha)=1$ if $\alpha\in E$ and zero otherwise. – Rabee Tourky Jan 15 '13 at 14:31
But E is a set of intervals, right? So, I choose $\alpha$ as a point in $[0,1]$. How can I say that $\alpha \in E$? How is $E$ chosen? – Eleanore Jan 15 '13 at 14:39
I totally misunderstood your question. I thought it was fixing $\{E_n\}$ each of length $\delta$ what is the average overlap of the sets at $\alpha\in [0,1]$ with the uniform distribution. – Rabee Tourky Jan 15 '13 at 14:56

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}$$

-