Problem of the Month (January 2018)

Break a stick of length 1 into n pieces at random locations. Order the pieces from smallest to largest length: X1 < X2 < . . . < Xn-1 < Xn. What can be said about these Xi?

What are the expected values E(Xi) for various n and i? What are the medians and modes?

Given some subset S of {1,2,3,...,n}, let XS = Σ Xi, i∈S. What is the probability that P(XS > 1/2) for various n and S? That is, what is the chance that the sum of the Xi for i in S is larger than the sum of the Xi for i not in S?

More generally, if S and T are non-overlapping subsets of {1,2,3,...,n}, what is P(XS > XT)?


ANSWERS

Expected Value of Xi
n \ i12345
11
21 / 43 / 4
32 / 185 / 1811 / 18
43 / 487 / 4813 / 4825 / 48
512 / 30027 / 30047 / 30077 / 300137 / 300

George Sicherman noticed that column 1 of the table was 1/n2 and the main diagonal was S(n)/(n n!), where S(n) is the nth Stirling number of the first kind.

Dan Dima said this problem was the January 2006 IBM Ponder This problem of the month. You can find the question and answer here. Thus with n pieces, E(Xi) = 1 / (n Σ 1/(n-k)) where the sum ranges over 0≤k<i.

Medians of Xi
n \ i1234
11
21 / 43 / 4
3(2–√2)/6√3/6(6–√6)/6
4(2–3√4)/8 .144+ .275+ 1 / 2

Modes of Xi
n \ i1234
11
2(0, 1/2)(1/2, 1)
301 / 31 / 2
401 / 72 / 75 / 11

P(S) = P( XS > 1/2 )
nSP(S)
3{3} 3 / 4
4{4} 1 / 2
{4,1} 3 / 4
5{5} 5 / 16
{5,4} 95 / 96
{5,3} 15 / 16
{5,2} 5 / 8
{5,1} 5 / 12
{4,3} 5 / 32

P(S,T) = P( XS > XT )
nSTP(S,T)
3{3}{2,1} 3 / 4
4{4,1}{3,2} 3 / 4
{4}{3,2,1} 1 / 2
{4}{3,2} 3 / 5
{4}{3,1} 4 / 5
{4}{2,1} 14 / 15
{3}{2,1} 2 / 3


If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 1/1/18.