Urban Operations Research Professor Arnold I. Barnett Lecture Note of 9/26/2001 Prepared by James S. Kang Stick Breaking Problem Consider a stick of length 1. Let X 1 and X 2 be independent random variables denoting two points on the stick at which we break the stick into three pieces. We assume thatX 1 andX 2 are uniformly distributed over the interval [0,1]. Let X S ≡ min(X 1 ,X 2 )and X L ≡ max(X 1 ,X 2 ). WedenotebyL 1 , L 2 ,andL 3 the lengths of the three pieces from the left end of the stick. 0 XLXS 1 L1 L2 L3 Figure 1: Breaking a stick of length 1 into three pieces We want to compute the probability that L 1 , L 2 ,andL 3 form a triangle. Clearly, the three pieces can form a triangle if the length of the longest piece is not greater than the sum of the lengths of the other two pieces. Let us consider the complementary question to the original question: What is the probability that L 1 , L 2 ,andL 3 cannot form a triangle? There are three cases for which the three pieces cannot form a triangle: ? Case I: L 1 >L 2 +L 3 Since L 1 +L 2 +L 3 =1,P(no triangle via case I)is given by P(L 1 >L 2 +L 3 )=P(L 1 >1 ?L 1 )=P(L 1 > 1 2 )=P(X S > 1 2 ). Note that P(X S > 1 2 )=P(X 1 and X 2 > 1 2 ). Because X 1 and X 2 are independent, we have P(X 1 and X 2 > 1 2 )=P(X 1 > 1 2 )P(X 2 > 1 2 )= 1 2 · 1 2 = 1 4 . ? Case II: L 2 >L 1 +L 3 P(no triangle via case II)is given by P(L 2 >L 1 +L 3 )=P(L 2 > 1 2 )=P(X L ?X S > 1 2 )=P(|X 1 ?X 2 |> 1 2 )= 1 4 . It is not di?cult to show P(|X 1 ?X 2 | > 1 2 )= 1 4 . Geometrically, it is the area of the event |X 1 ?X 2 |> 1 2 over a square of side length 1. 1 ? Case III:L 3 >L 1 +L 2 P(no triangle via case III)= 1 4 by symmetry with case I. Since the three cases are mutually exclusive, the probability that L 1 , L 2 ,andL 3 cannot form a triangle is 1 4 + 1 4 + 1 4 = 3 4 . Therefore the probability that the three pieces of the stick form a triangle is 1 ? 3 4 = 1 4 . 2