: Given a stick of length 1 meter. It is cut into two parts randomly.

: Given a stick of length 1 meter. It is cut into three parts randomly.

: 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.

Solution for problem 1: 1/4 (1a), 3/4 (1b)

Solution for problem 2: 1/9 (2a), 11/18 (2b), 5/18 (2c), 1/3 (2d), 1/4 (2e), 0 (2f), 0 (2g)

Solution for problem 3: 15/16 - 2log(3/2) (3a), …

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}^{0.5}p(x)dx = 1. The expected length of the smaller stick is E[x] = ∫ x p(x) dx = ∫

_{0}^{0.5}2xdx = 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-a}dxdy = (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] = ∫

_{0}^{1/3}6a(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 ∫

_{0}^{1/2}2 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} ∫

_{0}^{(1-x)/2} 4y/(1-x) dx dy + ∫

_{0}^{1/3} ∫

_{0}^{x} 4y/(1-x) dx dy +

∫

_{0}^{1/3}∫

_{x}^{(1-x)/2}4x/(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)

## No comments:

## Post a Comment