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.

I've come across this interesting little problem. I think that solving it is just a matter of thinking about it in the right way, but I'm stumped so far. Could someone please give me a hint in the right direction?

The Problem
Suppose you have $n$ logs (pieces of wood, not logarithms) of heights $X_1,\ldots,X_n$. $X_1,\ldots,X_n$ are independent, identically distributed random variables. Their common distribution is the exponential distribution with parameter $\lambda > 0$. The logs are to be stacked in two piles, one-on-top-of-the-other, according to the following procedure. First log 1 is stacked in a pile, then log 2 is stacked in a pile, then log 3, and so on. The i-th log is always stacked in the shortest of the two piles. That is, having stacked logs 1 to i-1, log i is stacked in the shortest of the two piles. What is the probability that log i ends up on top of the tallest pile?

What I've Tried
I've tried the problem with $n = 3$ and $n=4$, but couldn't see what to do. The main idea I've come up with so far is to consider $$ \mathbb{P}(i \in A | \sum_{a \in A} X_a > \sum_{b \in B} X_b ) $$ where $A \cup B = \{1,\ldots,n\}$. But I can't figure out how to work with it.

Thanks.

share|improve this question
1  
The logs are exponential? Now I've seen everything! –  Rahul Nov 2 '12 at 8:06

1 Answer 1

up vote 0 down vote accepted

Call Exp the exponential distribution with parameter $\lambda$. A crucial remark is that, for every $k\geqslant1$, after piece $k$ is stacked, the difference between the heights of the two piles is Exp: to see this, one can show that $|X-Y|$ is Exp for every $X$ and $Y$ independent Exp (this is a version of the waiting time paradox) and use a recursion on $k\geqslant1$.

Let $i\geqslant2$. Using the preceding result for $k=i-1$, one sees that the probability that piece $i$ ends on top of the highest stack is $$ p_i=\mathbb P(X\geqslant S), $$ where $X$ is Exp and $S$ is the sum of $n-i+1$ i.i.d. Exp independent of $X$. To wit, $X=X_i$ and $S=Y+X_{i+1}+\cdots+X_n$, where $Y$ is the difference between the heights of the two piles after piece $i-1$ is stacked and $X_j$ is the height of piece $j$, for every $j$. Thus, $$ p_i=\mathbb E(\mathbb P(X\geqslant S\mid S))=\mathbb E(\mathrm e^{-\lambda S})=\mathbb E(\mathrm e^{-\lambda X})^{n-i+1}. $$ Since $X$ is Exp, $\mathrm e^{-\lambda X}$ is uniform on $(0,1)$, hence $$ p_i=\left(\tfrac12\right)^{n-i+1}. $$ If $i=1$, one asks that $X_1\geqslant X_2+\cdots+X_n$ (in other words, the reasoning above still holds, but with $Y=0$) hence $p_1=p_2=\left(\tfrac12\right)^{n-1}$.

share|improve this answer

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.