Two Plus Two Publishing LLC Two Plus Two Publishing LLC
 

Go Back   Two Plus Two Poker Forums > Other Topics > Science, Math, and Philosophy

Notices

Science, Math, and Philosophy Discussions regarding science, math, and/or philosophy.

Reply
 
Thread Tools Display Modes
Old 11-19-2007, 09:29 PM   #1
Pooh-Bah
 
Join Date: Mar 2004
Posts: 5,363
Math puzzle: Breaking the camel\'s back.

Here is a problem and two generalizations. Part 1 is a well-known problem which is nontrivial, but solvable by several techniques. I solved it over dinner as a kid. Part 2 is less well-known. The solution I've seen published is overly complicated, but a simple solution is possible, and generalizes to Part 3.

Part 1: Your camel's back can hold 1 unit. Straws have weights which are uniformly distributed from 0 to 1 unit, and independent of each other. You add one straw at a time. If the weights are 0.7, 0.1, 0.8..., then your camel's back breaks on the 3rd straw. On average, how many straws does it take to break your camel's back?

Part 2: Let f(x) be the average number of straws it takes to break a camel's back if it can hold x units. Determine the asymptotics of f up to o(1), i.e., produce a simple function g so that the limit of f(x)-g(x) as x->infinity is 0.

Part 3: Produce a method for determining the asymptotics for some more general continuous weight distributions, such as the square of a uniformly distributed random variable, or the sum of two.

If you have a nice solution to only 1 part, it is worth posting it, but please put solutions in white.
pzhon is offline   Reply With Quote
Old 11-19-2007, 09:41 PM   #2
old hand
 
Join Date: Feb 2007
Posts: 1,660
Re: Math puzzle: Breaking the camel\'s back.

1) is pretty straightforward and it evaluates to a number that has been discussed a lot recently.

I think i might have an approach for 2. is the answer 2x+2/3+o(1)? if so i used laplace transforms.
blah_blah is offline   Reply With Quote
Old 11-20-2007, 11:33 AM   #3
Pooh-Bah
 
Join Date: Mar 2004
Posts: 5,363
Re: Math puzzle: Breaking the camel\'s back.

I'd like to see your solutions. It sounds like your approach is good (and fast...), although it is at least superficially different from what I used.
pzhon is offline   Reply With Quote
Old 11-20-2007, 06:25 PM   #4
Pooh-Bah
 
Join Date: Sep 2006
Posts: 3,655
Re: Math puzzle: Breaking the camel\'s back.

I have a solution for problem 1 although I couldn't get the text in white .

Solution : Re-formulate the problem and select random numbers from the interval [0,1] .

With probability 0 the camels back will be broken on the first straw .

With probability 1/2 , the camels back will be broken first on the second straw . You may argue that the probability x2 <x1 is 1/2 and so the probability 1< x1+x2 <1+x1 is 1/2 .

With probability 1/2*2/3 the camel's back will be broken first on the third straw . This is only possible if the camel's back is not broken by the first two straws(1/2) multiplied by the probability it is broken on the third straw . The probability the camel's back is broken on the third straw given that it's not broken by the first two straws is 2/3 since x3 is equally likely to be in the interval [0,x1] , [x1,x1+x2] or [x1+x2,1] . So x3 belongs in the interval [0,x1+x2] with probability 2/3 .
Hence 1 < x1+x2+x3 <1+x1+x2 with probability 2/3 .

The camel's back will be broken by the ith straw with probability 1/(i-1)!*(i-1)/i

So if we compute the expectation , we should get
1*0 + 2*1/2 + 3*1/2*2/3 + 4*1/2*1/3*3/4 + 5*1/2*1/3*1/4*4/5 + .... + i*1/(i-1)!*(i-1)/i

As i approaches infinity , the above expression is equivalent to:

e= 1/0! +1/1! + 1/2! + 1/3! + 1/4! +....
jay_shark is offline   Reply With Quote
Old 11-20-2007, 07:13 PM   #5
old hand
 
Join Date: Feb 2007
Posts: 1,660
Re: Math puzzle: Breaking the camel\'s back.

the first problem is a fairly simple consequence of the fact that the simplex bounded by the coordinate planes x_0 = ... = x_n = 1 and x_1+...+x_n = 1 has n-dimensional measure equal to 1/n!, but imo a better solution technique is as follows. Let E(t) denote the expected number of turns to reach t starting at 0. We have, for 0<t\leq 1,

E(t) = (1-t) + \int^t_0 [E(x)+1]dx

This is an integral equation with solution E(t) = a\exp(t). Note that as t decreases to 0, E(t) tends to 1. In particular we conclude that a=0 and E(t) = exp(t), so the desired answer is E(1) = \exp(1) = e
blah_blah is offline   Reply With Quote
Old 11-20-2007, 07:37 PM   #6
Carpal \'Tunnel
 
jogsxyz's Avatar
 
Join Date: Mar 2005
Posts: 6,362
Re: Math puzzle: Breaking the camel\'s back.

Quote:
I have a solution for problem 1 although I couldn't get the text in white .

Solution : Re-formulate the problem and select random numbers from the interval [0,1] .


The Font color is on the bottom right. Just click
the color you want.
jogsxyz is offline   Reply With Quote
Old 11-20-2007, 08:50 PM   #7
Pooh-Bah
 
Join Date: Sep 2006
Posts: 3,655
Re: Math puzzle: Breaking the camel\'s back.

Quote:


With probability 1/2 , the camel's back will be broken first on the second straw . You may argue that the probability x2 <x1 is 1/2 and so the probability 1< x1+x2 <1+x1 is 1/2 .


Let me clarify this part . x2 may either belong to the interval [0,x1] or [x1,x2] and either choice is equally likely . The probability x2 belongs to [0,x1] is 1/2 , or equivalently , the probability x2 belongs to [1,1+x1] is 1/2 .
jay_shark is offline   Reply With Quote
Old 11-21-2007, 09:58 AM   #8
veteran
 
bigpooch's Avatar
 
Join Date: Sep 2003
Location: Hong Kong
Posts: 3,208
Re: Math puzzle: Breaking the camel\'s back.

Was this how you started?

X[j] are positive continuous iiidrv with cdf F(.) and
S[n] = X[1]+...+X[n]

If T is the stopping time for capacity x,
E[T(x)] = 1 + F(t) + F[2](t) + F[3](t) +...
where F[n](t) is the cdf of S[n]

Using characteristic functions, with phi(z) = E[e^(izX)]

E[T(t)] = lim r->infinity{integral_-r to r: [1/(2*pi*i)](1-exp(-izt)/[z(1-phi(z))] dz}
bigpooch is offline   Reply With Quote
Old 11-21-2007, 03:00 PM   #9
Carpal \'Tunnel
 
Subfallen's Avatar
 
Join Date: Sep 2004
Location: farther back
Posts: 6,650
Re: Math puzzle: Breaking the camel\'s back.

Quote:
Quote:


With probability 1/2 , the camel's back will be broken first on the second straw . You may argue that the probability x2 <x1 is 1/2 and so the probability 1< x1+x2 <1+x1 is 1/2 .


Let me clarify this part . x2 may either belong to the interval [0,x1] or [x1,x2] and either choice is equally likely . The probability x2 belongs to [0,x1] is 1/2 , or equivalently , the probability x2 belongs to [1,1+x1] is 1/2 .
I still don't really understand this reasoning.

Can someone explain it further, as if to a mildly retarded twelve-year-old?
Subfallen is offline   Reply With Quote
Old 11-21-2007, 07:38 PM   #10
Pooh-Bah
 
Join Date: Mar 2004
Posts: 5,363
Re: Math puzzle: Breaking the camel\'s back.

Quote:
Part 1: Your camel's back can hold 1 unit. Straws have weights which are uniformly distributed from 0 to 1 unit, and independent of each other. You add one straw at a time. If the weights are 0.7, 0.1, 0.8..., then your camel's back breaks on the 3rd straw. On average, how many straws does it take to break your camel's back?
There are many solutions. In white, I have written up the one I found without pencil or paper when I was 13 after an uncle posed the problem at a family Thanksgiving dinner, and at which blah_blah hinted.

The expected value of a random variable X taking positive integer values is the sum of the probabilities P(X>=1)+P(X>=2) + P(X>=3) + ... This useful trick is actually a change of the order of summation in something that looks like a single sum, but can be expanded:

E(X)
= P(X=1) + 2 P(X=2) + 3 P(X=3) + ...
= P(X=1) + P(X=2) + P(X=3) + ...
+ _________P(X=2) + P(X=3) + ...
+ _______________ + P(X=3) + ...

Summing rows, this is
P(X>=1)+
P(X>=2)+
P(X>=3)+...

Anyway, P(X>=n) = P(the first n-1 straws add up to less than 1, so with k=n-1 we want the sum of the probabilities that the first k straws add up to less than 1 for k=0,1,... The plane x1+...+xk =1 cuts off a simplex of volumn 1/k! from the unit cube, so the expected value is 1/0! + 1/1! + 1/2! + ... = e.


Also at that dinner, we discussed the geometric mean of the numbers in [0,1], which is again related to e.

I'll post my solutions to Parts 2 and 3 later. I used a method which at least looks different from the suggestions of blah_black and bigpooch. However, I would not be surprised if they were all similar, from some perspective.
pzhon is offline   Reply With Quote
Old 11-21-2007, 11:55 PM   #11
Carpal \'Tunnel
 
Duke's Avatar
 
Join Date: Sep 2002
Location: SW US
Posts: 7,975
Re: Math puzzle: Breaking the camel\'s back.

Quote:
Quote:
Part 1: Your camel's back can hold 1 unit. Straws have weights which are uniformly distributed from 0 to 1 unit, and independent of each other. You add one straw at a time. If the weights are 0.7, 0.1, 0.8..., then your camel's back breaks on the 3rd straw. On average, how many straws does it take to break your camel's back?
There are many solutions. In white, I have written up the one I found without pencil or paper when I was 13 after an uncle posed the problem at a family Thanksgiving dinner, and at which blah_blah hinted.

The expected value of a random variable X taking positive integer values is the sum of the probabilities P(X>=1)+P(X>=2) + P(X>=3) + ... This useful trick is actually a change of the order of summation in something that looks like a single sum, but can be expanded:

E(X)
= P(X=1) + 2 P(X=2) + 3 P(X=3) + ...
= P(X=1) + P(X=2) + P(X=3) + ...
+ _________P(X=2) + P(X=3) + ...
+ _______________ + P(X=3) + ...

Summing rows, this is
P(X>=1)+
P(X>=2)+
P(X>=3)+...

Anyway, P(X>=n) = P(the first n-1 straws add up to less than 1, so with k=n-1 we want the sum of the probabilities that the first k straws add up to less than 1 for k=0,1,... The plane x1+...+xk =1 cuts off a simplex of volumn 1/k! from the unit cube, so the expected value is 1/0! + 1/1! + 1/2! + ... = e.


Also at that dinner, we discussed the geometric mean of the numbers in [0,1], which is again related to e.

I'll post my solutions to Parts 2 and 3 later. I used a method which at least looks different from the suggestions of blah_black and bigpooch. However, I would not be surprised if they were all similar, from some perspective.
Was your uncle the anomaly, or is your entire family filled with mathematicians?
Duke is offline   Reply With Quote
Old 11-22-2007, 12:29 AM   #12
banned
 
Limesparks's Avatar
 
Join Date: Nov 2005
Location: WOW IM SMART
Posts: 3,678
Re: Math puzzle: Breaking the camel\'s back.

Quote:
Quote:


With probability 1/2 , the camel's back will be broken first on the second straw . You may argue that the probability x2 <x1 is 1/2 and so the probability 1< x1+x2 <1+x1 is 1/2 .


Let me clarify this part . x2 may either belong to the interval [0,x1] or [x1,x2] and either choice is equally likely . The probability x2 belongs to [0,x1] is 1/2 , or equivalently , the probability x2 belongs to [1,1+x1] is 1/2 .
is there something i dont get about the notation here? how can x2 belong to the group [1,1+x1] if x2 in itself cant be >1?
Limesparks is offline   Reply With Quote
Old 11-22-2007, 09:20 AM   #13
Pooh-Bah
 
Join Date: Sep 2006
Posts: 3,655
Re: Math puzzle: Breaking the camel\'s back.

x2 is either less than x1 or is in between x1 and 1 (note I have x2 above which is a typo) . The probability it is less than x1 is 1/2 . If it is less than x1 with probability 1/2 , then it must belong to the interval [1,1+x1] with the same probability 1/2 . Since adding 1 to x2 has the same distribution as x1 .
jay_shark is offline   Reply With Quote
Old 11-23-2007, 08:17 PM   #14
Pooh-Bah
 
Join Date: Mar 2004
Posts: 5,363
Re: Math puzzle: Breaking the camel\'s back.

Quote:

Part 2: Let f(x) be the average number of straws it takes to break a camel's back if it can hold x units. Determine the asymptotics of f up to o(1), i.e., produce a simple function g so that the limit of f(x)-g(x) as x->infinity is 0.

Solution to Part 2 in white:

As blah_blah pointed out, f(x) satisfies an integeral equation, although I think it is better to write it differently: f(x) = 1 + Integral from x-1 to x of f(t) dt, with initial condition that f(x) = 0 on [-1,0]. This is even simpler if you consider g(x) = f(x)-2x, which satisfies

(1) g(x) = Integral from x-1 to x of g(t) dt,

with initial condition g(x) = -2x on [-1,0].

The integral equation satisfied by g looks like it smooths g out, and damps down the oscillations of g. Since g(x) is an average of values of g on the interval [x-1,x], g is bounded by the values on [-1,0], and then by the values on [0,1], etc. This can be used to show that g is asymptotic to a constant, although I won't give the details here.

The idea I had was to find a conserved quantity, some function h defined on [0,1], so that the integral from t=0 to t=1 of g(x+t) h(t) dt does not depend on x. Let's see what properties h might have to force

H(x) = integral from 0 to 1 of h(t) g(x+t) dt

to be constant. By Leibniz's rule (link),

H'(x) = integral from 0 to 1 of g'(x+t) h(t) dt

Integrating by parts,

H'(x) = g(x+1)h(1) - g(x)h(0) - integral from 0 to 1 of g(x+t) h'(t) dt.

We'd like to choose h to force this to be 0, using what we know about g, equation (1). To get the RHS to involve the integral of g(t) on an interval of length 1, we can set h'=1. Setting h(0)=0 forces a term to drop out, so let h(t)=t.

H'(x) = g(x+1) - integral from t=0 to t=1 of g(x+t) dt
H'(x) = g(x+1)-g(x+1)
H'(x) = 0.

So, we have established that integral from t=0 to t=1 of t * g(x+t) dt is constant. If g is asymptotic to some constant c, then

Limit x->oo H(x)
= integral from 0 to 1 of t c dt
= c/2

H(-1)
= integral from 0 to 1 of t g(t-1) dt
= integral from 0 to 1 of t (-2 (t-1)) dt
= 1/3

Since H is constant, c=2/3.

So, f(x)=g(x)+2x is asymptotic to 2x+2/3. As a quick check, f(1)=e, which is not too much greater than 2 2/3 = 1/0! + 1/1! + 1/2! + 1/3!.
pzhon is offline   Reply With Quote
Old 11-23-2007, 09:47 PM   #15
Pooh-Bah
 
Join Date: Mar 2004
Posts: 5,363
Re: Math puzzle: Breaking the camel\'s back.

Quote:
Part 3: Produce a method for determining the asymptotics for some more general continuous weight distributions, such as the square of a uniformly distributed random variable, or the sum of two.
Solution to Part 3 in white:

The method I used for Part 2 generalizes well. Let a(x) be the probability density function for the weight of a summand. We don't require that the weights be bounded, but they have to be positive, so a(x)=0 for x<0. We'll also use that the weight is continuous, although that isn't really required. Let f(x) for the expected index of the partial sum greater than x, and f(x) =0 for x<0. As before, f satisfies an integral equation,

f(x)= 1 + Integral from t=0 to t=x of f(t) a(x-t) dt.
Equivalently, we can let the lower value be -oo, as f is 0 on (-oo,0).

As before, we'll get rid of that constant term by subtracting off a linear factor. To do this, we need the weight to have an expected value, w. We'll also want the variance to exist. Define g(x) = f(x) - x/w. Note that when x<0, g(x) is not 0, but is -x/w instead. Then g satisfies an integral equation

g(x) = Integral from t=-oo to t=x g(t) a(x-t) dt.

We'd like to find a conserved quantity

H(x) = Integral t=-oo to t=x of g(t) h(x-t) dt.

We'll choose h so this is constant. Because of a different choice of variables, we didn't need the integration by parts (yet), but we get a more complicated application of Leibniz's rule since the upper limit of integration is not constant.

H'(x) = g(x)h(0) + Integral from t=-oo to t=x of g(t) h'(x-t)dt

Let h'(x) be c * a(x), so that this last integral resembles the integral equation for g(x).

H'(x) = g(x) h(0) + Integral from t=-oo to t=x of g(t) c a(x-t) dt
H'(x) = g(x) h(0) + g(x) c
H'(x) = g(x) (h(0) + c)

So, setting c=-h(0), H becomes constant.

We can scale h(0) arbitrarily, so let h(0)=1. Then
h(x) = 1 - Probability(weight < x)
h(x) = Probabability (weight > x)

Let the asymptotic value of g be v.

limit as x->oo H(x)
= limit as x->oo of Integral from t=-oo to t=x of g(x) h(x-t) dt
= limit as x->oo of Integral from t=-oo to t=x of v h(x-t)dt
= v * Integral from y=0 to y=oo of h(y) dy
= v * (-1) Integral from y=0 to y=oo of y h'(y) dy (by parts)
= v * Integral from y=0 to y=oo of y a(y) dy
= v * w

H(0)
= Integral from t=-oo to t=0 of g(t)h(-t)dt
= Integral from t=-oo to t=0 of -t/w h(-t) dt
= Integral from y=oo to y=0 of y/w h(y) (-1)dy
= Integral from y=0 to y=oo of y/w h(y) dy
= 1/w Integral from y=0 to y=oo of y h(y) dy
= 1/w (-1) Integral from y=0 to y=oo of y^2/2 h'(y) dy (by parts)
= 1/(2w) Integral from y=0 to y=oo of y^2 a(y) dy
= 1/(2w) * second moment of weight distribution

So, the asymptotic value v satisfies v * w = 2nd moment/(2w), or v= 2nd moment / (2 * 1st moment^2).

f(x) is asymptotic to x/(1st moment) + 2nd moment/(2 * 1st moment^2).

As a check, the nth moment for a random variable uniformly distributed on [0,1] is 1/n, so we get f(x) ~ x/(1/2) + 1/3 /(2 * 1/4) = 2x + 2/3.

How about an exponential distribution with mean 1? The 1st moment is 1, and the second moment is 2 (and variance is 2-1=1). f(x) ~ x + 2/2 = x+1. In fact, f(x) isn't just asymptotic to x+1, f(x)=x+1. The count of exponential distributions adding up to x is 1 more than a random variable with a Poisson distribution with mean x. So the expected value is x+1.
pzhon is offline   Reply With Quote

Reply
      

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are Off
Pingbacks are Off
Refbacks are Off




All times are GMT -4. The time now is 03:42 AM.


Powered by vBulletin®
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
Content Relevant URLs by vBSEO 3.6.0 ©2011, Crawlability, Inc.
Copyright 2008-2010, Two Plus Two Interactive