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: X₁ < X₂ < ^{. . .} < X_n-1 < X_n. What can be said about these X_i?

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

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

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

ANSWERS

Expected Value of X_i

n \ i	1	2	3	4	5
1	1
2	1 / 4	3 / 4
3	2 / 18	5 / 18	11 / 18
4	3 / 48	7 / 48	13 / 48	25 / 48
5	12 / 300	27 / 300	47 / 300	77 / 300	137 / 300

George Sicherman noticed that column 1 of the table was 1/n² and the main diagonal was S(n)/(n n!), where S(n) is the n^th 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(X_i) = 1 / (n Σ 1/(n–k)) where the sum ranges over 0≤k<i.

Medians of X_i

n \ i	1	2	3	4
1	1
2	1 / 4	3 / 4
3	(2–√2)/6	√3/6	(6–√6)/6
4	(2–³√4)/8	.144+	.275+	1 / 2

Modes of X_i

n \ i	1	2	3	4
1	1
2	(0, 1/2)	(1/2, 1)
3	0	1 / 3	1 / 2
4	0	1 / 7	2 / 7	5 / 11

P(S) = P( X_S > 1/2 )

n	S	P(S)
3	{3}	3 / 4
4	{4}	1 / 2
4	{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( X_S > X_T )

n	S	T	P(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.