avg # of maximum intersections for m 1-dimensional segments with length L in a range [0,t]?

37 Views Asked by At

I have a discrete range, let's say $[0,T]$.

I also have $m$ segments of length $L\leq T$. A segment is $seg=(a, a+L)$, with $0 \leq a \leq (t-L)$.

The total number of possible configurations of my segments is therefore $(T-L+1)^m$. In each of those configurations there is a point $t \in [0,T]$ during which I have the highest number $n$ of intersecting segments. For example, in case only one segment intersects $t$, then $n=1$; in case all segments intersect $t$, then $n=m$.

Of course, $t$ changes for each configuration.

I would like to know the value of $n$ in the average case.

Best regards.

1

There are 1 best solutions below

0
On

I try to formulate the model for you but it is far from a complete answer.

Let $A_i$ be the left-most point of the $i$-th segment , $i = 1, 2, \ldots, m$

By assuming each configuration is equally likely, then $$\Pr\{A_i = a\} = \frac {1} {T - L + 1}, a = 0, 1, 2, \ldots, T - L$$

Let $B_{ij}$ be the indicator of the range $[j-1, j]$ being covered by the $i$-th segment, $j = 1, 2, \ldots, T$. Since each segment is iid, then

$$ p_j \triangleq \Pr\{B_{1j} = 1\} = \left\{\begin{matrix} \displaystyle \frac {j} {T-L+1} & \text{if} & j = 1, 2, \ldots, L-1 \\ \displaystyle \frac {L} {T-L+1} & \text{if} & T \geq 2L, j = L, L+1, \ldots, T-L+1 \\ \displaystyle \frac {T-j+1} {T-L+1} & \text{if} & j = T-L+2, T-L+3, \ldots, T \\ \end{matrix}\right.$$

Next let $$ N_j = \sum_{i=1}^m B_{ij} \sim \text{Binomial}(m, p_j) $$

and now you want to compute $$ E\left[\max_{1 \leq j \leq T} N_j\right]$$

The difficult part is that these $N_j$ are dependent. One good thing to simplify here is that we have $$ B_{i1} \leq B_{i2} \leq \ldots \leq B_{iL} \text{ and } B_{i,T-L+1} \geq B_{i,T-L+2} \geq \ldots \geq B_{iT}$$ so you may just consider those $N_j$ in the middle. But the joint distribution is not obvious.

If $T$ is not too large, and $m$ is large, then we may try to use multivariate CLT to approximate the distribution of the random vector $(N_1, N_2, \ldots, N_T)$.