3
$\begingroup$

If a rod (of unit length) is broken into $n$ segments (assuming the $n-1$ breaks occur with uniform probability across the entire length) and $k$ of those segments are chosen at random and laid end to end, so that the sum $s$ of their $k$ lengths can be measured, then what distribution (or probability density function) $\rho(n, k, s)$ characterises this measurement?


So far I only have answers for special cases.

The PDF has domain $0 \leq s \leq 1$ in $\mathbb R$, where the parameters $n$ and $k$ are both integers and satisfy $n \geq 1$ and $0 \leq k\leq n$. Intuitively, the expectation value should be as if the rod were divided evenly:

  • $\int^1_0 \rho(n, k, s)\ ds = 1$
  • $\mathbb E[s] = \int^1_0 \rho(n, k, s)\ s\ ds = \frac k n$

The distribution is trivial if no or all segments are selected:

  • $\rho(n, 0, s)=\delta(s - 0)$
  • $\rho(n, n, s)=\delta(s - 1)$

I expect complementarity between the selected and unselected subsets:

  • $\rho(n, k, s) = \rho(n,\,n-k,\,1-s)$

Intuitively, if only one break occurs, then all possible lengths should be equally probable:

  • $\rho(2, 1, s) = 1 $

In the limit of many breaks, this resembles a Poisson process and so should be able to produce exponential or gamma distributions as an asymptote:

  • $\lim_{n\rightarrow\infty} \rho(n,1,s) = n e^{-ns}$
  • $\lim_{n\rightarrow\infty} \rho(n,k,s) = \frac {n^k s^{k-1}} {\Gamma(k)} e^{-ns}$

Does this much look correct? How would you go about finding the general form for $\rho(n, k, s)\,$?

$\endgroup$
1
1
$\begingroup$

If a unit-length rod is broken into $n=k+u$ segments, where the breaks occur with uniform probability along the rod, then the total end-to-end length $x$ of $k$ randomly-selected segments (discarding the other $u$ segments) is described by the Beta($k,u$) distribution, with probability density function:

$$\rho(k,u,x) = \frac {\Gamma(k+u)} {\Gamma(k)\Gamma(u)} x^{k-1} (1-x)^{u-1}$$

This is equivalent to the distribution for the $k$th-smallest among $(n-1)$ independent variables distributed uniformly over the unit interval.

Derivation

If a break occurs in a rod of unit length, with uniform probability along that length, then the probability that it occurs in the interval $(0,x)$ is $x$, and the probability that it instead occurs in the interval $(x,1)$ is $1-x$. If the rod breaks into $n$ segments, with those $(n-1)$ fissures each occurring independently, then the probability that exactly $k$ of those fissures occur in the interval $(0,x)$ is:

$${{n-1}\choose k} x^k (1-x)^{(n-1)-k}$$

Note the normalisation constant, ${}^nC_k$, because we don't distinguish which order the fissures occur in. The probability that at least $k$ fissures occur in the $(0,x)$ interval is:

$$\sum^{n-1}_{j=k} {{n-1}\choose j} x^j (1-x)^{(n-1)-j}$$

That expression is the cumulative probability that $k$ arbitrarily selected segments will have a combined length less than $x$. The gradient of this provides the probability density for the combined length.

$$\begin{align} \rho(k, n-k, x)&= \frac d {dx} \sum^{n-1}_{j=k} {}^{n-1}C_j\, x^j (1-x)^{(n-1)-j} \\ &=\sum^{n-1}_{j=k} {}^{n-1}C_j\left(jx^{j-1}(1-x)^{n-j-1} -(n-j-1)x^j(1-x)^{n-j-2}\right) \\ &=\sum^{n-1}_{j=k} \left( {}^{n-1}C_j\, j\right)x^{j-1}(1-x)^{n-j-1} \\&\qquad -\left( 0+ \sum^{n-1}_{j=k+1} \left({}^{n-1}C_{j-1}\, (n-j)\right)x^{j-1}(1-x)^{n-j-1} \right) \\ &=\frac {(n-1)!\,k} {k!(n-k-1)!} x^{k-1} (1-x)^{n-k-1} \\&\qquad + \sum^{n-1}_{j=k+1} \left( \frac{(n-1)!\,j}{j!\,(n-j-1)!} - \frac{(n-1)!\,(n-j)}{(j-1)!\,(n-j)!} \right) x^{j-1}(1-x)^{n-j-1} \\&=\frac {\Gamma(n)} {\Gamma(k)\Gamma(n-k)} x^{k-1} (1-x)^{n-k-1} + 0 \end{align}$$

Properties

The complementarity property (between selected and discarded segments) is trivial from the expression for the probability density function. Likewise, it is trivial to confirm that a single break ($k=u=1$) produces a uniform distribution.

The unit normalisation (of the integral with respect to $x$ over the interval), if not already assumed by construction, can be verified by checking both extremes of the cumulative probability function above. This CDF is clearly zero at the origin. When $x$ approaches one then the only non-vanishing term of the CDF will be ${}^{n-1}C_{n-1}x^{n-1}(1-x)^0$, which (although undefined at $x=1$) does limit to one.

Following the normalisation, the mean or expectation value $\frac k n$ can readily be verified from $\int \rho\, x\, dx$ by noting that the constant factor of the PDF is the integral of the other factors.

If the rod has very many fissures, then the problem should resemble a Poisson process and so approach a Gamma distribution (and hence also the exponential distribution in the case that $k=1$) with a matching scale (or fissure-event rate of $\theta^{-1}$). This does require rescaling and renormalisation of the PDF:

$$\begin{align} \lim_{n\rightarrow\infty} \frac 1 {n\theta}\ \rho\left(k, n-k, \frac x {n\theta}\right) &= \lim_{n\rightarrow\infty} \frac 1 {n\theta}\frac {\Gamma(n)} {\Gamma(k)\Gamma(n-k)} \left(\frac x {n\theta}\right)^{k-1} \left(1-\frac x {n\theta}\right)^{n-k-1} \\ &= \frac 1 {\Gamma(k)\theta^k} x^{k-1} \lim_{n\rightarrow\infty} \left(\frac {\Gamma(n)} {\Gamma(n-k) n^k}\right) \left(1-\frac 1 n \left(\frac x \theta \right)\right)^{n-k-1} \\ &= \frac 1 {\Gamma(k)\theta^k} x^{k-1} e^{- \frac x \theta} \end{align}$$

Left as an exercise: to also confirm limiting to a delta distribution as $k$ approaches zero or $n$ (and, to that end, interpreting non-integer $k$)...

(Hat-tip to @whuber for suggesting the Beta distribution might possibly have the appropriate asymptotes.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.