Puzzles, Maths and Algorithms: Stick Breaking
Problem Set 1: Given a stick of length 1 meter. It is cut into two parts randomly.
Problem Set 2: Given a stick of length 1 meter. It is cut into three parts randomly.
Problem Set 3: Given a stick of length 1 meter. It is cut into two parts randomly. Then bigger stick is picked and is again cut into two parts randomly.
Generalized Cut Problem: Find the solution to problem 2a-2c, 3a-3c for n-1 cuts.
Let us work out solution for 1a. Smaller stick has length x which is uniformly distributed in the range [0,0.5]. The probability distribution of x is p(x) = 1 / [1/2-0] = 2. Yes it is a pdf, ∫ 00.5p(x)dx = 1. The expected length of the smaller stick is E[x] = ∫ x p(x) dx = ∫ 00.52xdx = 1/4.
2a) Let us work out solution for 2a. Let two cuts are at distance x,y from one end. Let x < y. So the three sticks are of length x, y-x, 1-y. Let z = min(x,y-x,1-y) represent the minimum length of the stick. Let Pr(z>a) indicate the probability that min length stick has length greater than a.
=> Pr(z>a) = 2 * Pr(x>a, y-x>a, 1-y>a) = Pr(x>a, a+x < y < 1-a)
Note multiplication by 2 is for the other case (x > y). Since a+x< y < 1-a, we get x < 1-2a. Also setting x =a, we get a < 1/3 (which is obvious).
=> Pr(z > a) = 2 ∫ a1-2a ∫ a+x1-adxdy = (1-3a)2.
So we get Pr(z<=a) = 1-Pr(z>a). And Pr(z=a) = derivative of Pr(z<=a) at a = 6(1-3a).
=> E[a] = ∫ 01/36a(1-3a)da = 1/9
2b) We can do a similar derivation for z = max(x,y-x,1-y) to get the expected max length. It would be slightly more complicated. Unlike above, we compute here Pr(z< a)
=> Pr(z < a) = Pr(x < a, y-x < a, 1-y < a) = Pr( 1-2a < x < a, 1-a < y < x + a).
We need to be careful here are respect constraints like x > 0, x < y, y < 1. To ensure these constraints are respected. Pr(z < a) is broken into three cases, Case 1: a < 1/2. Case 2: a >= 1/2, 0 < x < 1-a, Case 3: a >= 1/2, 1-a < x < a. Then we have to take differential of obtained Pr(z < a) to get Pr(z=a). [Dont mix terms from the three cases].
Integrate the first case from [1/3 to 1/2]. Second and third case from [1/2 to 1]. We will see the desired output as 1/2+1/9=11/18. (Don't forget to multiply by 2 to cover for x > y case).
2c) It would be easy to obtain: 1 - (2a) - (2b) = 1 - 1/9 - 1/2 - 1/9 = 1/2 - 2/9 = 5/18.
2d) Since there are no constraints, expected length of middle cut is 1/3
2e) For triangle, we require satisfaction of three inequalities
x + y - x > 1-y,
x + 1- y > y - x,
y - x + 1 - y > x
Apart from the implicit x < y inequality.
=> 1/2 < y < x + 1/2, x < 1/2
So x follows a pdf of P(x) = 2. y satisfied the range with probability x. So the probability of triangle formation is ∫ 01/22 x dx = 1/4.
2f) There are discrete stick lengths, e.g. (3/12, 4/12, 5/12) that satisfy this property. There are countably infinite, yet the area encapsulated by them is 0.
Problem set 3 is slightly more complicated. Let us work out 3a).
Let the first cut is at length x from shorter side (x < 1/2). Now from the stick of length (1-x), we make a cut at random of length y. Let y < (1-x)/2. If x is the shortest stick then x < y => x < 1/3.
Case 1: 1/3 < x < 1/2, 0 < y < (1-x)/2 => y is the shortest stick
Case 2: 0 < x < 1/3
Case 2a: 0 < y < x => y is the shortest stick
Case 2b: x < y < (1-x)/2 => x is the shortest stick
We also note that P(x) = 2 (a uniform distribution in [0,1/2]), P(y) = 2/(1-x) (a uniform distribution in [0, (1-x)/2]).
So the Expected min length = ∫ 1/31/2 ∫ 0(1-x)/2 4y/(1-x) dx dy + ∫ 01/3 ∫ 0x 4y/(1-x) dx dy +
∫ 01/3∫ x(1-x)/24x/(1-x) dx dy = 15/16 - 2 log(3/2)
For Generalized problem read David and Nagaraja's Order Statistics (pp. 133-135, and p. 153)
The solutions through Monte-Carlo simulations. Following python code solves problem set 2 and 3.
Problem Set 1: Given a stick of length 1 meter. It is cut into two parts randomly.
- Problem 1a: What is the expected length of the smaller stick?
- Problem 1b: What is the expected length of the bigger stick?
Problem Set 2: Given a stick of length 1 meter. It is cut into three parts randomly.
- Problem 2a: What is the expected length of the smallest stick?
- Problem 2b: What is the expected length of the largest stick?
- Problem 2c: What is the expected length of the stick with second smallest (or second largest) length?
- Problem 2d: What is the expected length of the middle stick (stick that is between the two cuts)?
- Problem 2e: What is the probability that the three sticks would form a triangle?
- Problem 2f: What is the probability that the three sticks would form a right angle triangle?
- Problem 2g: What is the probability that the three sticks would form an equilateral triangle?
Problem Set 3: Given a stick of length 1 meter. It is cut into two parts randomly. Then bigger stick is picked and is again cut into two parts randomly.
- Problem 3a: What is the expected length of the smallest stick?
- Problem 3b: What is the expected length of the largest stick?
- Problem 3c: What is the expected length of the stick with second smallest (or second largest) length?
- Problem 3d: What is the expected length of the middle stick (stick that is between the two cuts)?
- Problem 3e: What is the probability that the three sticks would form a triangle?
- Problem 3f: What is the probability that the three sticks would form a right angle triangle?
- Problem 3g: What is the probability that the three sticks would form an equilateral triangle?
Generalized Cut Problem: Find the solution to problem 2a-2c, 3a-3c for n-1 cuts.
Let us work out solution for 1a. Smaller stick has length x which is uniformly distributed in the range [0,0.5]. The probability distribution of x is p(x) = 1 / [1/2-0] = 2. Yes it is a pdf, ∫ 00.5p(x)dx = 1. The expected length of the smaller stick is E[x] = ∫ x p(x) dx = ∫ 00.52xdx = 1/4.
2a) Let us work out solution for 2a. Let two cuts are at distance x,y from one end. Let x < y. So the three sticks are of length x, y-x, 1-y. Let z = min(x,y-x,1-y) represent the minimum length of the stick. Let Pr(z>a) indicate the probability that min length stick has length greater than a.
=> Pr(z>a) = 2 * Pr(x>a, y-x>a, 1-y>a) = Pr(x>a, a+x < y < 1-a)
Note multiplication by 2 is for the other case (x > y). Since a+x< y < 1-a, we get x < 1-2a. Also setting x =a, we get a < 1/3 (which is obvious).
=> Pr(z > a) = 2 ∫ a1-2a ∫ a+x1-adxdy = (1-3a)2.
So we get Pr(z<=a) = 1-Pr(z>a). And Pr(z=a) = derivative of Pr(z<=a) at a = 6(1-3a).
=> E[a] = ∫ 01/36a(1-3a)da = 1/9
2b) We can do a similar derivation for z = max(x,y-x,1-y) to get the expected max length. It would be slightly more complicated. Unlike above, we compute here Pr(z< a)
=> Pr(z < a) = Pr(x < a, y-x < a, 1-y < a) = Pr( 1-2a < x < a, 1-a < y < x + a).
We need to be careful here are respect constraints like x > 0, x < y, y < 1. To ensure these constraints are respected. Pr(z < a) is broken into three cases, Case 1: a < 1/2. Case 2: a >= 1/2, 0 < x < 1-a, Case 3: a >= 1/2, 1-a < x < a. Then we have to take differential of obtained Pr(z < a) to get Pr(z=a). [Dont mix terms from the three cases].
Integrate the first case from [1/3 to 1/2]. Second and third case from [1/2 to 1]. We will see the desired output as 1/2+1/9=11/18. (Don't forget to multiply by 2 to cover for x > y case).
2c) It would be easy to obtain: 1 - (2a) - (2b) = 1 - 1/9 - 1/2 - 1/9 = 1/2 - 2/9 = 5/18.
2d) Since there are no constraints, expected length of middle cut is 1/3
2e) For triangle, we require satisfaction of three inequalities
x + y - x > 1-y,
x + 1- y > y - x,
y - x + 1 - y > x
Apart from the implicit x < y inequality.
=> 1/2 < y < x + 1/2, x < 1/2
So x follows a pdf of P(x) = 2. y satisfied the range with probability x. So the probability of triangle formation is ∫ 01/22 x dx = 1/4.
2f) There are discrete stick lengths, e.g. (3/12, 4/12, 5/12) that satisfy this property. There are countably infinite, yet the area encapsulated by them is 0.
Problem set 3 is slightly more complicated. Let us work out 3a).
Let the first cut is at length x from shorter side (x < 1/2). Now from the stick of length (1-x), we make a cut at random of length y. Let y < (1-x)/2. If x is the shortest stick then x < y => x < 1/3.
Case 1: 1/3 < x < 1/2, 0 < y < (1-x)/2 => y is the shortest stick
Case 2: 0 < x < 1/3
Case 2a: 0 < y < x => y is the shortest stick
Case 2b: x < y < (1-x)/2 => x is the shortest stick
We also note that P(x) = 2 (a uniform distribution in [0,1/2]), P(y) = 2/(1-x) (a uniform distribution in [0, (1-x)/2]).
So the Expected min length = ∫ 1/31/2 ∫ 0(1-x)/2 4y/(1-x) dx dy + ∫ 01/3 ∫ 0x 4y/(1-x) dx dy +
∫ 01/3∫ x(1-x)/24x/(1-x) dx dy = 15/16 - 2 log(3/2)
For Generalized problem read David and Nagaraja's Order Statistics (pp. 133-135, and p. 153)
The solutions through Monte-Carlo simulations. Following python code solves problem set 2 and 3.
from random import random
def prob2():
niter = 100000
n, ntri, nrtri = 0.0, 0, 0
lsmall, llarge, lmid, lcenter = 0, 0, 0, 0
while n < niter:
n += 1
p = random()
q = random()
x = min(p, q)
y = max(p, q)
l1 = x
l2 = y-x
l3 = 1-y
mn = min(l1, l2, l3)
mx = max(l1, l2, l3)
md = 1 - mn - mx
lsmall += mn
llarge += mx
lmid += md
lcenter += y
if l1 + l2 > l3 and l1 + l3 > l2 and l2 + l3 > l1:
ntri += 1
if mn**2 + md**2 == mx**2:
nrtri += 1
print 'min len:', lsmall/n
print 'max len:', llarge/n
print 'mid len:', lmid/n
print 'center stick len', lcenter/n
print 'triangle prob:', ntri/float(n)
print 'right triangle prob:', nrtri/float(n)
def prob3():
niter = 100000
n, ntri, nrtri = 0.0, 0, 0
lsmall, llarge, lmid, lcenter = 0, 0, 0, 0
while n < niter:
n += 1
p = random()
q = random()
l1 = 0.5 * (1-p)
l2 = 0.25 * (1+p) * (1-q)
l3 = 0.25 * (1+p) * (1+q)
mn = min(l1, l2, l3)
mx = max(l1, l2, l3)
md = 1 - mn - mx
lsmall += mn
llarge += mx
lmid += md
lcenter += (l2+l3)/2
if l1 + l2 > l3 and l1 + l3 > l2 and l2 + l3 > l1:
ntri += 1
if mn**2 + md**2 == mx**2:
nrtri += 1
print 'min len:', lsmall/n
print 'max len:', llarge/n
print 'mid len:', lmid/n
print 'center stick len', lcenter/n
print 'triangle prob:', ntri/float(n)
print 'right triangle prob:', nrtri/float(n)
Read full article from Puzzles, Maths and Algorithms: Stick Breaking