6

I would like to compute the probability distribution for the length of the fragments which I would obtain by fragmenting a linear rod of length $L$ in the following way:

  1. I choose at random (uniformly) $n$ breakpoints
  2. I cut the rod at those breakpoints, creating $(n+1)$ fragments.

Now, while it is easy to see that the probability that a stretch of length $x$ does not contain any breakpoint goes like a negative exponential, I don't know how to throw in the information about the length of the rod.

cardinal
  • 24,973
  • 8
  • 94
  • 128
XenophiliusLovegood
  • 61
  • 2
  • 2
    You can choose your units of measurement--meters, yards, parsecs, whatever--without materially changing the problem. So, choose a unit in which the rod has length 1. Done! :-) – whuber May 17 '11 at 16:25
  • @whuber, thanks but I am not yet there. Basically I get a negative exp by computing the product of many small steps, each of them with probability (1-p), in the limit where the length of the step is very small. Now, how do I introduce in this computation the fact that I can't overstep the "right end" of the rod? – XenophiliusLovegood May 17 '11 at 17:02
  • 1
    @X I'm a little lost, because I don't see how you are making a connection between the "many small steps" and the situation you have presented. – whuber May 17 '11 at 17:25
  • @X I also wonder about your "negative exponential" assertion. Fixing a segment of length $x$ in a unit rod (without any loss of generality), the chance that any single breakpoint misses it is $1-x$. Because the breakpoints are independent, the chance that all of them miss it is $(1-x)^n$. That's not a negative exponential: it's a polynomial in $x$. Perhaps you're thinking of an asymptotic characterization for small $x$ and large $n$ (and bounded $nx$)? With those asymptotics the rod's length is arbitrarily large compared to $x$ and therefore should *not* play any role. – whuber May 18 '11 at 04:35
  • @whuber I was obtaining the probability that no breakpoint falls in a segment of length $x$ by $(1-x/M)^{nM}$, from which an exponential when $M$ goes to infinity. So, I divide $x$ in $M$ parts, and multiply the probabilities that each of these parts is _not_ hit by a breakpoint. – XenophiliusLovegood May 18 '11 at 10:20
  • @X Those are the asymptotic conditions I had guessed. Is the answer now clear to you? – whuber May 18 '11 at 15:11
  • @whuber No sorry. First of all, thanks for your effort. Second, could you please either elucidate your answer (say, writing some formulae making your point clearer to me), or give me a pointer to some paper or website in which this problem has been studied already? Assume I don't consider any asymptotics, so the length of the rod matters. (I am also confused about the asymptotics at the moment, in the sense that at no stage I am posing $x$ small, but I think I can think my way out of _that_ confusion). – XenophiliusLovegood May 18 '11 at 16:16

2 Answers2

2

Let the rod have length $L$ and fix a segment of length $x$. The chance that any single breakpoint misses the segment equals the proportion of the rod not occupied by the segment, $1−x/L$. Because the breakpoints are independent, the chance that all of them miss it is the product of $n$ such chances, $(1 - x/L)^n$.

From comments following the question, it appears that $x$ is intended to be small compared to the rod's length: $x/L \ll 1$. Let $\xi = L/x$ (assumed to be large) and rewrite $n = \xi(n/\xi)$, leading (purely via substitutions) to

$$\Pr(\text{all miss}) = (1 - x/L)^n = (1 - 1/\xi)^{\xi(n/\xi)} = \left((1-1/\xi)^\xi\right)^{n/\xi}\text{.}$$

Asymptotically $\xi \to \infty$. If we assume that $n$ varies in a way that makes $n/\xi$ converge to a constant, this probability approaches a computable limit. Let this constant be some value $\lambda$ times $x$. It is the limiting value of $n/\xi/x = n/L$: notice how the length of the rod is involved here and effectively is incorporated in $\lambda$. Because $\exp(-1) = 1/e$ is the limiting value of $(1-1/\xi)^\xi$ and raising to (positive) powers is a continuous function, it follows readily that the limit is

$$\Pr(\text{all miss}) \to e^{-\lambda x}.$$

One application is when $n$ is a constant, entailing $\lambda = n/L$, and $x \ll L$. We obtain $$e^{-nx/L}$$ as a good approximation for the probability that all breaks miss the segment. This analysis shows that the approximation fails as $x$ grows large: the approximation is only as good as the approximation $1/e \sim (1-1/\xi)^\xi$. Finally, if you set $x = L$, the approximation is clearly wrong because it gives $e^{-n}$ instead of the correct answer, $0$.

whuber
  • 281,159
  • 54
  • 637
  • 1,101
  • thanks for your answer. I have one residual doubt. My original quest was to find a pdf for the lengths of the fragments. now, if I use $(1-\frac{x}{L})^n$, I run into troubles. First, (let's assume $L=1,n=1$) it is not normalized $\int_0^1 (1-x)\, dx=\frac{1}{2}$. Secondly, imagine I want to compute the average length of a fragment. That'd be $\int_0^1 x(1-x)\, dx=\frac{1}{6}$, which I don't understand either. What's your take? – XenophiliusLovegood May 21 '11 at 11:42
  • @X We're not computing a probability distribution here: $x$ is a *fixed* value, not a random quantity! (See the first line of my reply.) Thus, neither the normalization nor the expectation make any sense at all. The question I answered is the one you asked in comments: "I was obtaining the probability that no breakpoint falls in a segment of length $x$". Your original question asks for a "probability distribution for the length of the fragments...." Because there will be $n+1$ fragments, you are looking for an $n+1$-variate distribution for *all* the lengths. – whuber May 21 '11 at 19:33
  • 1
    I don't understand well your last comment. On the other hand, I think I possibly got to a satisfactory conclusion: $(1-x)^n$ is the cdf of the pdf I am looking for (in the original question). The corresponding pdf is $n(1-x)^{n-1}$ which is normalized and has nice expectation values. – XenophiliusLovegood May 23 '11 at 10:44
0

Let $\{X_i\}$ be the locations of the cuts.

I'd approach this problem by finding the order statistics $\{Y_i\}$ so that $Y_1$ would be the location of the leftmost cut. Then I'd calculate the probability distributions of the differences between the variables $Y_i-Y_{i-1}$. Don't forget to also calculate $Y_1-0$ and $L-Y_n$.

Can anyone think of a better way?

Tauf
  • 11
  • 2
  • 2
    Yes: First close the rod into a circle. Then break it (uniformly, randomly, independently) at $n+1$ breakpoints. This introduces a helpful symmetry :-). – whuber May 17 '11 at 16:24
  • 2
    Or, draw a connection to the Poisson process. – cardinal May 17 '11 at 16:46