Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let's say you generate 3 uniformly distributed, independent random numbers on the interval $[0,1]$. Now consider the lengths of the 4 segments made.

What is the probability that the sum of the two medium-length segments is greater than $ 0.5 $?

Example

Let the random numbers be $ 0.5 $, $ 0.3 $, $ 0.1 $. This cuts the interval like so:

|*|**|**|*****|

The sum of the medium-length segments is then $ 0.2 + 0.2 = 0.4 $.

Answer (numerical, no proof)

I ran a computer simulation of this and got the answer: spoiler.

However I can't seem to come up with a derivation of this.

share|improve this question
    
That's an interesting way to hide a spoiler... –  Ilmari Karonen Jul 22 '11 at 19:14
    
Thought of it on the spot ;) –  tskuzzy Jul 22 '11 at 19:16
    
@leonbloy: Not as I read the question. As I understand it, if the random numbers were $0.2,0.4,0.5$, the medium-length segments would be the first two, and the sum of their lengths would (still) be $0.4$. In other words, I take the ordering to be by actual length, not by position in the unit interval. –  Brian M. Scott Jul 22 '11 at 19:57
    
Yes, it's not clear if we are ordering the points (according to the values) or the segments (acording to their lenghts). OP? –  leonbloy Jul 22 '11 at 20:16
1  
@Didier: Yep, I'd already upvoted it :-) Another fact that might be interesting: the event is equivalent to throwing 4 iid uniforms in [0,1] and comparing the geometric mean of the extremes against that of the middle pair. –  leonbloy Jul 24 '11 at 20:59
show 4 more comments

2 Answers 2

up vote 5 down vote accepted

Let us try to compute this probability without actually evaluating any integral.

We begin with the remark that one can realize the three random numbers and the number $1$ itself as the four first points of a homogenous Poisson process. In other words, the lengthes of the four intervals are proportional to $(X_i)_{1\le i\le 4}$ where the random variables $X_i$ are i.i.d. and exponential of parameter $1$.

Introducing the order statistics $X_{(i)}$ of the sample $(X_i)$, one asks for $p=P(A)$ with $$ A=[X_{(2)}+X_{(3)}\ge X_{(1)}+X_{(4)}]. $$ Using the notation $X_{(0)}=0$, the waiting time paradox shows that the increments $$ Y_i=X_{(i)}-X_{(i-1)} $$ are independent for $1\le i\le 4$ and that each $Y_i$ is exponential of parameter $5-i$. Since the event of interest is also $$ A=[Y_2\ge Y_4], $$ the probability $p$ is also $$ p=P(Z\ge 3Z'), $$ where $Z$ and $Z'$ are i.i.d. and exponential of parameter $1$. In other words, $p=P(U\le1/4)$ with $$ U=Z'/(Z+Z'). $$ Since $U$ is uniformly distributed in the interval $(0,1)$, $p=1/4.$

Added later on More generally, throwing $n$ points in $(0,1)$ yields $n+1$ intervals. The ordered lengthes of these intervals are proportional to the order statistics $(X_{(i)})_{1\le i\le n+1}$ of an i.i.d. sample $(X_i)_{1\le i\le n+1}$ of exponential random variables. For each $i$, $X_{(i)}=Y_1+\cdots+Y_i$, where the random variables $(Y_i)_{1\le i\le n+1}$ are independent and the distribution of $Y_i$ is exponential with parameter $n+2-i$.

share|improve this answer
    
Thanks for the wonderfully simple and concise solution! I'll take a closer look at it later today. –  tskuzzy Jul 24 '11 at 16:55
    
@tskuzzy, thanks for the appreciation. Do not hesitate asking for precisions on some steps if needed, since conciseness is not always a virtue... –  Did Jul 24 '11 at 17:00
    
Why is it that the $ X_i $ are independent? If we have 2 segments, doesn't the length of the second depend completely on the length of the first? Also, could you elaborate on the how you got the distribution of $ Y_i $? I looked at the time waiting paradox but I don't see how your result follows from it. And finally, is the fact that $ U $ is uniform something that I should just know? Or did you have to derive that for this particular problem? Thanks again! –  tskuzzy Jul 25 '11 at 13:10
    
The keyword here is proportional: the lengthes of the consecutive subintervals of $(0,1)$ are distributed like $X_i/(X_1+\cdots+X_4)$, or equivalently, the position of the $i$th point is $(X_1+\cdots+X_i)/(X_1+\cdots+X_4)$. One can rediscover this by elementary computations, or look into any textbook on point processes, for example the one by Brémaud. –  Did Jul 25 '11 at 15:03
    
Distribution of $Y_i$: for a sample of size $2$, this is the waiting time paradox but you can also reprove it since $[Y_1\in dx,Y_2\in dy]$ is $[X_1\in dx,X_2\in x+dy]$ union $[X_2\in dx,X_1\in x+dy]$ and the exponential(2) product exponential(1) distribution follows. For a sample of size $n$, one decomposes $[Y_1\in dx_1,\ldots,Y_n\in dx_n]$ likewise. Try to do it, if there is a problem I will give more details. –  Did Jul 25 '11 at 15:08
show 1 more comment

The lengths of the segments are uniformly distributed over the unit $3$-simplex (see Simulating uniformly on $S^1=\{x \in \mathbb{R}^n \mid \|x\|_1=1\}$). Thus, the desired probability is the fraction of the part of the unit $3$-simplex with $x_1\le x_2\le x_3\le x_4$ for which $x_2+x_3\ge\frac12$.

The unit simplex has volume $1/6$, so the restriction to one particular permutation of the coordinates leads to a volume of $1/6\cdot1/4!=1/144$. We can check this to make sure the integration bounds are set up correctly:

$$\int_0^{1/4}\int_{x_1}^{(1-x_1)/3}\int_{x_2}^{(1-x_1-x_2)/2}\mathrm dx_3\mathrm dx_2\mathrm dx_1=\frac1{144},$$

as computed here.

The integration bounds under the condition $x_2+x_3\ge\frac12$ are a bit trickier, since there are two possibilities, depending on $x_2$. For $x_2\ge\frac14$, all values of $x_3$ with $x_3>x_2$ fulfill the condition, whereas for $x_2<\frac14$ there's a new lower bound $\frac12-x_2$ for $x_3$. Thus we split the integral into two parts at $x_2=\frac14$, with different lower bounds for $x_3$:

$$\int_0^{1/4}\int_{x_1}^{1/4}\int_{1/2-x_2}^{(1-x_1-x_2)/2}\mathrm dx_3\mathrm dx_2\mathrm dx_1=\frac1{768},$$

$$\int_0^{1/4}\int_{1/4}^{(1-x_1)/3}\int_{x_2}^{(1-x_1-x_2)/2}\mathrm dx_3\mathrm dx_2\mathrm dx_1=\frac1{2304},$$

as computed here and here, respectively. So the desired probability is indeed

$$\frac{\frac1{768}+\frac1{2304}}{\frac1{144}}=144\cdot\frac{4}{2304}=\frac{144}{576}=\frac14\;.$$

share|improve this answer
    
Very nice! I thought of representing the lengths of the segments as a 3-simplex, but I didn't think that the distribution would be uniform. I was thinking of generalizing the problem to more than 4 segments and arbitrary sums. Your observation makes this general situation significantly more feasible to solve. –  tskuzzy Jul 22 '11 at 23:58
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.