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 XI and X2 be independent random variables denoting two points n the stick at which we break the stick into three pieces. We assume that X1 and X2 are uniformly distributed over the interval [ 0,1] Let Xs= min(X1, X2) and XL= max(X1, X2). We denote by L1, L2, and Lg the length the three pieces from the left end of the stick LI L2 L3 0 Figure 1: Breaking a stick of length 1 into three pieces We want to compute the probability that L1, L2, and L 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 L1, L2, and L3 cannot form a triangle? There are three cases for which the three pieces cannot form a triangle: Case I: L1 >l2+l Since L1+ L2+ L=l, P(no triangle via case I) is given by P(1>+L3)=P(L1>1-)=P(>2)=P(xs>2 Note that P(Xs>2)=P(X1 and X2 >2). Because X1 and X2 are independent, we have P(X1 and X2> P(X1>2)PX2>2)=22=4 Case II: L2>L1+ l3 P(no triangle via case II)is given by P2>L1+1a)=P2>2)=P(xn-xs>2)=P(x-x2l>2) It is not difficult to show P(IX1-X2l >5=. Geometrically, it is the area of the event IX1-X2l>5 over a square of side length 1
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 X1 and X2 be independent random variables denoting two points on the stick at which we break the stick into three pieces. We assume that X1 and X2 are uniformly distributed over the interval [0, 1]. Let XS ≡ min(X1, X2)and XL ≡ max(X1, X2) . We denote by L1, L2, and L3 the lengths of the three pieces from the left end of the stick. 0 XS XL 1 L1 L2 L3 Figure 1: Breaking a stick of length 1 into three pieces We want to compute the probability that L1, L2, and L3 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 L1, L2, and L3 cannot form a triangle? There are three cases for which the three pieces cannot form a triangle: • Case I: L1 > L2 + L3 Since L1 + L2 + L3 = 1, P(no triangle via case I)is given by P(L1 > L2 + L3) = P(L1 > 1 − L1) = P(L1 > 1 2 ) = P(XS > 1 2 ) . Note that P(XS > 1 2 ) = P(X1 and X2 > 1 2 ). Because X1 and X2 are independent, we have P(X1 and X2 > 1 2 ) = P(X1 > 1 2 )P(X2 > 1 2 ) = 1 2 · 1 2 = 1 4 . • Case II: L2 > L1 + L3 P(no triangle via case II)is given by P(L2 > L1 + L3) = P(L2 > 1 2 ) = P(XL − XS > 1 2 ) = P(|X1 − X2| > 1 2 ) = 1 4 . It is not difficult to show P(|X1 − X2| > 1 2 ) = 1 4 . Geometrically, it is the area of the event |X1 − X2| > 1 2 over a square of side length 1. 1
· Case III:I3>L1+L2 P(no triangle via case III)= by symmetry with case I Since the three cases are mutually exclusive, the probability that L1, L2, and L cannot form a triangle is 4 +i+5=3. Therefore the probability that the three pieces of the stick form a triangle is1-是=1
• Case III: L3 > L1 + L2 P(no triangle via case III)= 1 4 by symmetry with case I. Since the three cases are mutually exclusive, the probability that L1, L2, and L3 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