I met an interesting but challenging problem in my homework:

Suppose $n-1$ independent points $x_1$, $x_2$, ..., $x_{n-1}$ are uniformly distributed on unit interval [0,1]. These $n-1$ points seperate the unit interval into $n$ pieces. Suppose the lengths of these $n$ intrvals are $v_1$, $v_2$, ..., $v_n$. What is the probablity that $v_i < a$ for $i = 1,2,...,n$ ? Here $1/n < a < 1$ is a constant.

The joint distribution of $v_1$, $v_2$, ..., $v_{n-1}$ is a uniform distribution on a $n-2$ dimention simplx with $f(v_1, v_2,...,v_{n-1}) = (n-1)!$. The simplex is $$v_i \geq 0, \; i=1,2,...,n-1$$ $$v_1 + v_2 + ... + v_{n-1} \leq 1$$ The proof of this density distribution is not easy.

I followed this idea but I found it's still hard. Maybe there are some other starting points to consider this problem.

  • $\begingroup$ @ClementC. what do you mean? $\endgroup$ – Stupid_Guy Nov 8 '14 at 22:34
  • 1
    $\begingroup$ @Stupid_Guy Show us your thoughts. People is more eager to help if you show that you have invested some effort in the problem. Nobody likes to do some other's homework. $\endgroup$ – leonbloy Nov 8 '14 at 22:38
  • 1
    $\begingroup$ That before asking a question, you should have given it some thought and have attempted to solve it by yourself. $\endgroup$ – Clement C. Nov 8 '14 at 22:39
  • $\begingroup$ @ClementC. Sure, I will add it:-) $\endgroup$ – Stupid_Guy Nov 8 '14 at 22:49

Here is a full analysis:

For every $a\geqslant0$ and every integer $n\geqslant1$, let $p_n(a)$ denote the probability that $n-1$ i.i.d. uniform points separate $[0,1]$ into $n$ pieces of length at most $a$, hence $p_n(a)=0$ for $a\leqslant1/n$ and $p_n(a)=1$ for $a\geqslant1$.

One can deduce $p_{n+1}$ from $p_n$ through a conditioning argument:

Throw $n$ i.i.d. uniform points in $[0,1]$. The position $x$ of the rightmost point has density $nx^{n-1}$ for $x$ and the rightmost interval has length at most $a$ if $x\geqslant1-a$. Conditionally on each $x$ in $[0,1]$, the $n-1$ other points are distributed as $n-1$ i.i.d. uniform points in $[0,x]$ hence they separate $[0,x]$ into $n$ intervals distributed as the $n$ intervals delineated by $n-1$ i.i.d. uniform points in $[0,1]$, scaled by the homothetic factor $x$. Thus, for every $a\geqslant0$,

$$p_{n+1}(a)=\int_{1-a}^1nx^{n-1}p_n(a/x)\mathrm dx.$$

One can tediously recover from this identity and from the initial condition $p_1=\mathbf 1_{[1,+\infty)}$ the easy fact that $$p_2(a)=\left\{\begin{array}{cc}0&a\leqslant\tfrac12\\2a-1&\tfrac12\leqslant a\leqslant1\\1&a\geqslant1\end{array}\right.$$ To go further, note that each function $p_n$ coincides with a specific polynomial on each interval $\left[\frac1k,\frac1{k-1}\right]$ for $k\geqslant1$, with $p_{n}=1$ on $[1,+\infty)$ and $p_{n}=0$ on $\left[0,\frac1{n}\right)$. To wit, the change of variables $$p_n(a)=(n-1)!\,a^{n-1}\,q_n(1/a),$$ yields the initial condition $q_1=\mathbf 1_{[0,1]}$ and, for every $n\geqslant1$ and every real number $t$, $$q_{n+1}(t)=\int_{t-1}^tq_n(x)\mathrm dx.$$ This concludes the proof of our final result:

For every $n\geqslant1$, $p_n(a)=(n-1)!\,a^{n-1}\,q_n(1/a)$, where $q_n$ denotes the $n$th Irwin-Hall density, that is, the density of the sum of $n$ i.i.d. random variables uniformly distributed on $[0,1]$.

  • $\begingroup$ For some odd reason, given the fact that both $0\le p_k(a)\le1$ and $|a|<1$, your last formula reminds me of $\cos2t=2\cos^2t-1$. $\endgroup$ – Lucian Nov 9 '14 at 0:23

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.