7
$\begingroup$

You break a stick of unit length in two. You then subsequently break the biggest of the resulting two sides in two, thus obtaining three pieces.

What is the expected length of the smallest of the three?

(Each breaking of a stick is assumed to be at a random point in that stick, uniformly distributed.)

  • 0
    it is related - but different!2012-12-08

3 Answers 3

7

If the shorter stick after the first break has length $S$ then $S$ uniformly distributed on $[0,\frac{L}{2}]$.

If $S=s$ then the shorter part of the longer stick will have length $T$ uniformly distributed on $[0,\frac{L-s}{2}]$. You will certainly have $T \lt s$ if $\frac{L}{3} \lt s \le \frac{L}{2}$.

So the expectation of the minimum of $S$ and $T$ is

$\int_{s=\frac{L}{3}}^\frac{L}{2} \int_{t=0}^\frac{L-s}{2} t \frac{2}{L-s} \frac{2}{L} \,dt\,ds + \int_{s=0}^\frac{L}{3} \int_{t=0}^s t \frac{2}{L-s} \frac{2}{L} \,dt\,ds + \int_{s=0}^\frac{L}{3} \int_{t=s}^\frac{L-s}{2} s \frac{2}{L-s} \frac{2}{L} \,dt\,ds $ $= \frac{7 L}{144} +2L\log\left( \frac{3}{2}\right)-\frac{7L}{9} +\frac{5L}{3} -4L\log\left( \frac{3}{2}\right) $ $= L\left(\frac{15}{16} -2\log\left( \frac{3}{2}\right) \right)$ the same as did's answer

  • 0
    Oh, so sorry, I was trying to solve a different problem and though this one was the same. I didn't read the question carefully. I agree your answer is right.2015-06-16
5

The lengths of the two pieces of a stick of length $L$ are $\frac12(1\pm U)L$, where $U$ is uniform on $(0,1)$. Hence the lengths of the three pieces are $ \frac12(1-U),\quad \frac14(1+U)(1+V),\quad\frac14(1+U)(1-V), $ where $U$ and $V$ are i.i.d. uniform on $(0,1)$. The smallest $S$ of these three lengths is $S=\frac12(1-U)$ on $A=[V\lt a(U)]$ and $S=\frac14(1+U)(1-V)$ on $B=[V\gt a(U)]$, where $a$ is defined by $ a(u)=\frac{(3u-1)^+}{u+1}. $ Since $\mathbb E(A\mid U)=a(U)$, $ \mathbb E(S\mathbf 1_A\mid U)=\frac12(1-U)a(U). $ Likewise, $ \mathbb E(S\mathbf 1_B\mid U)=\frac14(1+U)\mathbb E((1-V)\mathbb 1_{V\gt a(U)}\mid U)=\frac14(1+U)\frac12(1-a(U))^2. $ Summing these yields $ \mathbb E(S\mid U)=\frac12(1-U)a(U)+\frac18(1+U)(1-a(U))^2, $ which can be simplified into $ \mathbb E(S\mid U)=\frac18(1+U)-\frac18\frac{((3U-1)^+)^2}{1+U}. $ Thus, $\mathbb E(S)=\frac3{16}-\tfrac18t$, with $ t=\int_{1/3}^1\frac{(3u-1)^2}{1+u}\mathrm du=\int_0^{1}\frac{4x^2}{2+x}\mathrm dx, $ that is, $ t=\left[2x^2-8x+16\log(2+x)\right]_{0}^1=-6+16\log\left(\frac32\right). $ Finally, $ \mathbb E(S)=\frac{15}{16}-2\log\left(\frac32\right)=0.12657\ldots $

  • 0
    honestly dont understand what you mean.... your reasoning was brilliant, you nailed the question... thank you for addressing this problem :)2012-12-08
5

When you make the first cut, the bigger piece has length $p$ that is uniformly distributed in $[\frac12, 1]$. (And so the smaller piece has length $1-p$ uniformly distributed in $[0, \frac12]$, but of course not independent of the length $p$ of the bigger piece.)

Similarly, when you cut this piece of length $p$ at a uniformly chosen point, the smaller piece of the two has length $q$ uniformly distributed in $[0, \frac{p}{2}]$.

The smallest of the three pieces is therefore of length $\min(q, 1-p)$. We can calculate its expected value as $ \int_{1/2}^{1} \int_{0}^{p/2} \min(q, 1-p) \;(\frac{1}{p/2}dq) \;(\frac{1}{1/2}dp) = \int_{1/2}^{1} \frac{4}{p} \int_{0}^{p/2} \min(q, 1-p) \;dq \;dp$

If $p/2 \le 1-p$ (which happens when $p \le 2/3$), then as $q \le p/2 \le 1-p$, it is always the case that $\min(q, 1-p) = q$, and so the inner integral becomes $ \int_{0}^{p/2} \min(q, 1-p) \;dq = \int_{0}^{p/2} q \;dq = \frac{p^2}{8}.$

Else, for $p/2 > 1-p$, the inner integral can be split as $\begin{align} \int_{0}^{p/2} \min(q, 1-p) \;dq &= \int_{0}^{1-p} q \;dq + \int_{1-p}^{p/2} (1-p) \;dq \\ &= (1-p)^2/2 \;\;+\;\; p(1-p)/2 - (1-p)^2 \\ &= p(1-p)/2 - (1-p)^2/2 \end{align}$

So the outer integral is $\begin{align} &\int_{1/2}^{1} \frac{4}{p} \int_{0}^{p/2} \min(q, 1-p) \;dq \;dp \\ &=\int_{1/2}^{2/3} \frac{4}{p}\frac{p^2}{8} \;dp + \int_{2/3}^{1} \frac{4}{p}(\frac{p(1-p)}{2} - \frac{(1-p)^2}{2})\;dp \\ &=\int_{1/2}^{2/3} p/2 \;dp + \int_{2/3}^{1} \left(2(1-p) - \frac{2(1-p)^2}{p}\right) \; dp \\ &= \frac{7}{144} + \frac{1}{9} - (\log(9/4) - 7/9)\\ &= \frac{15}{16} - \log\left(\frac94\right) \approx 0.12657 \end{align}$

This looks like a really strange answer, but it is roughly confirmed by the following simulation:

#!/usr/bin/env python import random num_samples = 0 sum_samples = 0 for num_samples in xrange(1, 100000000):     r1 = random.uniform(0, 1)     p = max(r1, 1 - r1)     r2 = random.uniform(0, p)     q = min(r2, p - r2)     cur_sample = min(q, p - q, 1 - p)     sum_samples += cur_sample     average = sum_samples / num_samples     if num_samples % 100000 == 0:         print 'Average is %.5f after %d samples' % (average,num_samples)