Two Plus Two Poker Forums Math puzzle: Breaking the camel's back.
 Register FAQ Search Today's Posts Mark Forums Read Video Directory TwoPlusTwo.com

 Notices

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

 11-19-2007, 10:29 PM #1 pzhon 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.
 11-19-2007, 10:41 PM #2 blah_blah 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.
 11-20-2007, 12:33 PM #3 pzhon 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.
 11-20-2007, 07:25 PM #4 jay_shark 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! +....
 11-20-2007, 08:13 PM #5 blah_blah 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
11-20-2007, 08:37 PM   #6
jogsxyz
Carpal \'Tunnel

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.

11-20-2007, 09:50 PM   #7
jay_shark
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 .

 11-21-2007, 10:58 AM #8 bigpooch veteran     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}
11-21-2007, 04:00 PM   #9
Subfallen
Carpal \'Tunnel

Join Date: Sep 2004
Location: farther back
Posts: 7,244
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?

11-21-2007, 08:38 PM   #10
pzhon
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&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.

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.

11-22-2007, 12:55 AM   #11
Duke
Carpal \'Tunnel

Join Date: Sep 2002
Location: SW US
Posts: 7,981
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&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.

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?

11-22-2007, 01:29 AM   #12
Limesparks
banned

Join Date: Nov 2005
Location: WOW IM SMART
Posts: 3,677
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 &gt;1?

 11-22-2007, 10:20 AM #13 jay_shark 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 .
11-23-2007, 09:17 PM   #14
pzhon
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-&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!.

11-23-2007, 10:47 PM   #15
pzhon
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&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.

 Thread Tools Display Modes Linear Mode

 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 Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Two Plus Two     Two Plus Two Magazine Forum     The Best of Two Plus Two     The Two Plus Two Bonus Program     Two Plus Two Pokercast     Two Plus Two Videos     Marketplace         General Marketplace         Staking - Offering Stakes         Staking - Seeking Stakes         Staking - Selling Shares - Online         Staking - Selling Shares - Live         Staking Rails         Transaction Feedback & Disputes     Commercial Marketplace     Staking - Offering Stakes     About the Forums Fantasy Sports     Fantasy Sports         Sporting Events General Poker Discussion     Beginners Questions     Live Casino Poker         Poker Venues         Regional Communities     Poker Goals & Challenges     Books and Publications     Poker Theory     Poker Tells/Behavior, hosted by: Zachary Elwood     News, Views, and Gossip     Twitch - Watch and Discuss Live Online Poker     Televised Poker     Home Poker     Poker Legislation & PPA Discussion hosted by Rich Muny     That's What She Said!     Poker Beats, Brags, and Variance Coaching/Training     Coaching Advice     Cash Game Poker Coach Listings     Tournament/SNG Poker Coach Listings International Forums     Deutsch         BBV [German]     Français     Two Plus Two en Espańol No Limit Hold'em     Medium-High Stakes PL/NL     Micro-Small Stakes PL/NL     Medium-High Stakes Full Ring     Micro-Small Stakes Full Ring     Heads Up NL     Live Low-stakes NL Limit Texas Hold'em     Mid-High Stakes Limit     Micro-Small Stakes Limit Tournament Poker     STT Strategy     Heads Up SNG and Spin and Gos     Mid-High Stakes MTT     Small Stakes MTT     MTT Community     MTTc - Live         WPT.com Other Poker     High Stakes PL Omaha     Small Stakes PL Omaha     Omaha/8     Stud     Draw and Other Poker General Gambling     Backgammon Forum hosted by Bill Robertie.     Probability     Psychology     Sports Betting     Other Gambling Games Internet Poker     Internet Poker         Winning Poker Network         nj.partypoker.com         Global Poker     Commercial Software     Software         Commercial Software         Free Software     nj.partypoker.com         WPT.com 2+2 Communities     Other Other Topics         OOTV         Game of Thrones     The Lounge: Discussion+Review     EDF     Las Vegas Lifestyle     BBV4Life         omg omg omg     House of Blogs Sports and Games     Sporting Events         Single-Team Season Threads         Fantasy Sports     Wrestling     Golf     Pool, Snooker, and Billiards     Chess and Other Board Games     Video Games         League of Legends         Hearthstone     Puzzles and Other Games Other Topics     Politics         Economics     Business, Finance, and Investing     Travel     Science, Math, and Philosophy     History     Religion, God, and Theology     Health and Fitness     Student Life     The Studio     Laughs or Links!     Computer Technical Help     Programming

All times are GMT -4. The time now is 10:17 AM.

 Contact Us - Two Plus Two Publishing LLC - Privacy Statement - Top