The consequence of overlap sharing for the length-distribution of rods randomly placed on a line - MathOverflow

The consequence of overlap sharing for the length-distribution of rods randomly placed on a line

2010-07-15T00:01:57Z

Please imagine that one populates a finite line of unit length, or circle with unit length contour (to avoid edge-effects), with $N$ one-dimensional 'rods' such that their LHS-ends, at positions $(p_1, ..., p_k, ..., p_N) \in P$, are placed in accordance with a uniform random distribution over [0, 1]. Here, the rod lengths, $(l_1, ..., l_k, ..., l_N) \in L$, are exponentially distributed according to some rate parameter $\lambda$ - i.e. the random variable $l_k$ has distribution $l_k$ ~ Exp($\lambda$), giving a probability density function for rod length of $\lambda e^{\lambda l}$. One would similarly expect an exponential distribution for the distances between adjacent points in the set $P$.

We have the following two rules for handling overlaps between rods:

(1) - If the 'contour' of one rod (say, 'Rod A') completely covers another (say, 'Rod B'), i.e. where (Rod A-LHS) < (Rod B-LHS) and (Rod A-RHS) > (Rod B-RHS), we remove 'Rod B' from from the line and no longer consider it.

(2) - If there is only a partial overlap in the contours of two rods, 'Rod A' and 'Rod B', the length of this overlap is split evenly and each half is added to the contours of 'Rod A' and 'Rod B', respectively.

Starting from our initial exponential distribution of rod lengths, $(l_1, ..., l_k, ..., l_N)$, after this overlap-splitting process what is the new probability distribution for the length of some rod, $l_k$?

A few observations:

As $\lambda \rightarrow \infty$, the number of rods left on the line (after overlaps are handled) should increase, and the mean rod length should decrease.

As $N \rightarrow \infty$, the number of overlap-processed rods left on the line should increase, and the mean rod length should decrease. Intuitively I would expect that the number of rods remaining on the line after overlap processing will increase ever more slowly with $N$ after some threshold/'saturation' value is reached (presumably where the line is completely covered with rods).

As $\lambda \rightarrow -\infty$, there should be fewer rods left remaining on the line after overlap processing, and the mean rod length should increase. At some sufficiently large value of $\lambda$, we should be left with only a single rod on the line which has the left-most/smallest LHS-side. If we also have that $N \rightarrow \infty$, the mean length of the rod should approach the unit length of the line.

As $N \rightarrow 0$, there should be fewer rods, and an increasing mean rod length.

Inspired by Joseph O'Rourke's answer, and some simulation results of mine, if one fixes $\lambda$ and lets $N \rightarrow \infty$, one appears to converge to a rod length distribution centered around a mean value somewhere between $\frac{L}{2}$ and $L$, where $L$ is the original mean length of the rods before overlap processing. However, this distribution appears to be Gaussian, not uniform.

Do we actually converge to a Gaussian distribution? How does the distribution and its variance change with increasing $N$?

Answer by Joseph O'Rourke for The consequence of overlap sharing for the length-distribution of rods randomly placed on a line

2010-07-15T13:16:17Z

This is not an answer, only a simplification and conjecture concerning that simplification. First, only consider $N$ large enough so that the interval/circle is fully covered (the "eventually" in my comment). Second, rather than your exponential distribution, fix all rods to the same (small) length $L$, perhaps $L < \frac{1}{2}$ suffices. Retain your assumption that the left endpoint of each rod is chosen uniformly in $[0,1]$. Then I conjecture that the limiting distribution is uniform with mean rod length $L/2$. I have only heuristic arguments for this (shorter rods get absorbed by newly added ones, existing longer rods get chopped from the ends). Perhaps you could alter your simulation to this simplified circumstance to see if this is empirically true?

If this conjecture holds, then perhaps it holds even for an exponential distribution, with $L$ now the mean length of that distribution.

Addendum: I verified this myself, and indeed it seems to hold empirically. Here are results of a simulation adding 10 million rods of length $L=\frac{1}{10}$ to $[0,1]$. Only lengths of rods within $[L,1-L]$ are averaged in the graph (to exclude edge effects).

Answer by RubeRad for The consequence of overlap sharing for the length-distribution of rods randomly placed on a line

2010-07-15T14:35:07Z

I don't have an answer either, except to note that this setup is very similar to the core of my dissertation. This stochastic distribution of random-length intervals models the problem of genomic mapping; if you have blasted many copies of some genetic material into fragments, how do you characterize the fragmentations that can uniquely be reconstructed (up to complete reversal) -- vs. fragmentations that are ambiguous (can be consistently reconstructed in multiple ways)?

Then there's the question of, OK, you've sampled fragments of DNA with a distribution that you believe gives you sufficient probability of being unambiguous, so how do you actually figure out how to order the fragments into a map? If you further cut the fragments at all occurrences of a few short DNA sequences (restriction sites for digestion enzymes), overlaping areas will yield common distributions of sub-fragment lengths, and you can begin to see who overlaps who, and start to piece the whole thing together.

If you are cool with postscript, you can find two papers at this link (search for Settergren), or I have pdf'd them here and there. Or,you could just download the whole dissertation.