Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
Am I correct in these two consequences of your rules?: (a) After each step, the rods have disjoint interiors; (b) eventually, the unit interval/circle is entirely covered end-to-end by rods (of various lengths). –  Joseph O'Rourke Jul 15 '10 at 1:03
    
Dear Joseph, Yes about (a), however, (b) is not necessarily true for small 'N' and/or short rod lengths. There can be gaps. –  Rob Grey Jul 15 '10 at 1:21
    
@Rob: I have some trouble understanding the model itself. Assume for instance that some rods A, B and C are such that LHS(A) < LHS(B) < LHS(C) < RHS(A) < RHS(B) < RHS(C). Then what happens? If one applies your rule to A and B first, getting A' and B', and then (if necessary), to B' and C, getting B'' and C', one gets a configuration A', B'' and C' which could be different from the configuration one gets if one applyes the rule to B and C first and then (if necessary) to A and the modified B. And this is only one configuration amongst many where this kind of ambiguity arises. Or am I mistaken? –  Did Dec 13 '10 at 8:42
add comment

2 Answers 2

up vote 1 down vote accepted

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).
alt text

share|improve this answer
    
Dear Joseph, Thanks for your answer! However, the most interesting part of this problem for me (which I accidently stumbled upon while simulating another system) is the dramatic effect this had on smoothing out the exponential distribution of the rods with the right $\lambda$. –  Rob Grey Jul 15 '10 at 14:26
    
Joseph, very cool, thanks for running the simulation! From my own simulations, it appears that if we fix $\lambda$ and let $N \rightarrow \infty$, we converge to a Gaussian-looking distribution centered around a mean of $\frac{L}{2}$, where $L$ is the mean length of the rods before overlap processing. –  Rob Grey Jul 16 '10 at 23:19
    
Actually, to be more accurate, the mean seems to be somewhere between L/2 and L, not strictly at L/2... –  Rob Grey Jul 17 '10 at 0:19
    
@Rob: My simulation converged to $L/2$ after $10^7$ iterations. I used $[0,1]$ but had to remove end-effects. I did not look at the distribution, however, just the mean. Cannot post data now... –  Joseph O'Rourke Jul 17 '10 at 0:26
    
Dear Joseph, It looks like my simulation might converge to L/2 as well... but I'm still looking at higher values of 'N' and wanted to be conservative with my statement. My guess is that you're not going to have a uniform distribution! –  Rob Grey Jul 17 '10 at 0:34
show 3 more comments

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.

share|improve this answer
    
The system I was modeling concerned crosslinks between polyethylene molecules (and a coding mistake leading to this question). However, sonicated/digested/etc. DNA is a really good example of a system where your going to have to deal with an exponential distribution of fragment lengths. This is probably a tangent, but how much of an advantage do you get from a pseudo-deterministic cleavage pattern vs. one that's uniform? People seem to make such a fuss about 'unbiased' cleavage with sonication or endonucleases. Is there an inflection point with longer sequencing read lengths? –  Rob Grey Jul 15 '10 at 14:57
    
I think the answer might be that "longer" is not the right question so much as "more variable". I edited my comment above to put a link to the whole dissertation. My model involved a genome length of L, and clone lengths uniformly sampled from [1,1+delta]. If you look at page 28 of the dissertation, you will see there is something special happening at delta=2 (lengths ~ U(1,3)) Short answer, if you want to avoid ambiguity with constant-length clones, you need n~L(lnL+lnlnL), but for 0<del<1, you can get away with more like n~L/2(lnL). I think; it's been a long time... –  RubeRad Jul 15 '10 at 15:25
    
And I didn't answer your first question; back in the day (mid-90s) when I was in school, that was not a question I ever asked. The model I built upon involved constant- (unit-)length clones, and I analyzed assumptions of either U(1,1+delta), or 1+exp(). I suppose it might be interesting to analyze instead an arbitrary discrete distribution at values 1, 1+d1, 1+d2, ... But probably quite harder; simulation would probably work better for getting answers. You know, now I wish I had added another chapter to my dissertation, doing simulations of my theoretical results, and other distros as well! –  RubeRad Jul 15 '10 at 15:32
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.