5

Suppose I have an interval of length $x$ and I want to drop $n$ sticks of unit length onto it (where $\sqrt x<n<x$). What is the expected overlap between sticks? ($x$ can be assumed to be large enough that edge effects are negligible.)

I assume this is a standard problem and has a name but I don't know it. It's related to the birthday problem, a discrete version of this problem, and also to Rényi's parking problem which disallows overlap rather than measuring it.

I suppose there are at least two ways to measure overlap: the total length of the interval covered by more than one stick, or the same weighted by the number of sticks, less 1, at that point. The second is slightly more natural in my application, but I'd be happy with either.

Edit: I found Comparing Continuous and Discrete Birthday Coincidences: “Same-Day” versus “Within 24 Hours” (2010) which discusses finding the probability of any overlap in my model, rather than the expected length of the overlap.

Charles
  • 32,122
  • 1
    for either, you want the 'expectation method', which can be found in ross. The (simple) idea is you integrate the probability of a given bound being covered by more than one or exactly 2 or whatever sticks. – mike Aug 27 '13 at 14:40

1 Answers1

3

Let $t \in [0,x]$. The probability that a given stick hits $t$ (assuming left end-point of stick chosen uniformly in $[0,x-1]$) is

$p(t) = \begin{cases} \frac{t}{x-1} & t < 1 \\ \frac{1}{x-1} & 1 < t < x-1 \\ \frac{x-t}{x-1} & x-1 < t < x\end{cases}$.

The probability that $\geq 2$ sticks hit $t$ is (via the complement) $1-(1-p(t))^n- np(t)(1-p(t))^{n-1} $.

If $H(t,\omega)$ is the indicator for the event that $\geq 2$ sticks hit $t$, then the total length of such points is $\int_{t=0}^x H(t,\omega) dt$. Take the expectation, and we are left with $\int_0^x (1-(1-p(t))^n - np(t)(1-p(t))^{n-1} dt$. Feed that into some symbolic integrator?

For the weighted version, the same idea yields $\int_0^x \sum_{k=2}^n (k-1) \binom{n}{k} p(t)^k (1-p(t))^{n-k} dt$.

That's all I feel like doing for the moment. Interesting form... A potential simplification is if you consider a cyclic interval.

Evan
  • 3,861