Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
show 10 more comments

3 Answers 3

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

share|improve this answer
add comment
up vote 0 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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