Two Plus Two Newer Archives  

Go Back   Two Plus Two Newer Archives > Other Topics > Science, Math, and Philosophy

Reply
 
Thread Tools Display Modes
  #11  
Old 11-22-2007, 12:55 AM
Duke Duke is offline
Senior Member
 
Join Date: Sep 2002
Location: SW US
Posts: 5,853
Default 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?

[/ QUOTE ]
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.
<font color="white">
The expected value of a random variable X taking positive integer values is the sum of the probabilities P(X&gt;=1)+P(X&gt;=2) + P(X&gt;=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&gt;=1)+
P(X&gt;=2)+
P(X&gt;=3)+...

Anyway, P(X&gt;=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. </font>

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.

[/ QUOTE ]

Was your uncle the anomaly, or is your entire family filled with mathematicians?
Reply With Quote
  #12  
Old 11-22-2007, 01:29 AM
Limesparks Limesparks is offline
Senior Member
 
Join Date: Nov 2005
Location: WOW IM SMART
Posts: 2,482
Default 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 &lt;x1 is 1/2 and so the probability 1&lt; x1+x2 &lt;1+x1 is 1/2 .



[/ QUOTE ]

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 .

[/ QUOTE ]
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 &gt;1?
Reply With Quote
  #13  
Old 11-22-2007, 10:20 AM
jay_shark jay_shark is offline
Senior Member
 
Join Date: Sep 2006
Posts: 2,277
Default 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 .
Reply With Quote
  #14  
Old 11-23-2007, 09:17 PM
pzhon pzhon is offline
Senior Member
 
Join Date: Mar 2004
Posts: 4,515
Default 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-&gt;infinity is 0.


[/ QUOTE ]
Solution to Part 2 in white:
<font color="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-&gt;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!.
</font>
Reply With Quote
  #15  
Old 11-23-2007, 10:47 PM
pzhon pzhon is offline
Senior Member
 
Join Date: Mar 2004
Posts: 4,515
Default 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.

[/ QUOTE ]
Solution to Part 3 in white:
<font color="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&lt;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&lt;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&lt;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 &lt; x)
h(x) = Probabability (weight &gt; x)

Let the asymptotic value of g be v.

limit as x-&gt;oo H(x)
= limit as x-&gt;oo of Integral from t=-oo to t=x of g(x) h(x-t) dt
= limit as x-&gt;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.
</font>
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

Forum Jump


All times are GMT -4. The time now is 05:53 PM.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2024, vBulletin Solutions Inc.