Puzzles, Maths and Algorithms: Stick Breaking

Puzzles, Maths and Algorithms: Stick Breaking
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, ∫ ₀^0.5p(x)dx = 1. The expected length of the smaller stick is E[x] = ∫ x p(x) dx = ∫ ₀^0.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 ∫ _a^1-2a ∫ _a+x^1-adxdy = (1-3a)². 

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] =  ∫ ₀^1/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  ∫ ₀^1/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/3^1/2 ∫ ₀^(1-x)/2 4y/(1-x) dx dy + ∫ ₀^1/3 ∫ ₀^x 4y/(1-x) dx dy + 
                                               ∫ ₀^1/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