2
$\begingroup$

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.

  • 1
    The logs are exponential? Now I've seen everything!2012-11-02

1 Answers 1

0

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}$.