Author 
Topic: The Toad and the Water Lilies (Read 1306 times) 

ThudnBlunder
wu::riddles Moderator Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489


The Toad and the Water Lilies
« on: Jun 6^{th}, 2008, 9:40am » 
Quote Modify

A toad hops down a long line of water lilies. Before each hop it flips a fair coin to decide whether to hop two lilies forward or one lily back. What is the expected fraction of the water lilies it will land on?


IP Logged 
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: The Toad and the Water Lilies
« Reply #1 on: Jun 10^{th}, 2008, 12:15pm » 
Quote Modify

Bit tricky, this one, but nice: hidden:  Let p_{n} be the probability that the toad ever lands on the pad n units to the right. We have p_{0} = 1, and for n != 0, p_{n} = (p_{n2}+p_{n+1})/2, or p_{n+1} = 2p_{n}  p_{n2}. The characteristic polynomial of this recurrence is x^{3}  2x^{2} + 1 = (x1)(x^{2}x1), which has roots 1, r, and s, where r = (1+sqrt 5)/2, s = (1sqrt 5)/2. But because the recurrence only holds for n!=0, we have to solve it twice: p_{n} = A + Br^{n} + Cs^{n}, n >= 1; p_{n} = X + Yr^{n} + Zs^{n}, n <= 0. This has 6 unknowns, but we also know the following: (a) p_{n} is bounded for all n. This gives B=0 and Z=0. (b) p_{n} converges to 0 as n goes to infinity. This gives X=0. (c) p_{0} = 1. This gives A+C=1, Y=1. Equating the two formula for p_{1} gives finally 1/r = A+C/s = A+(1A)/s, and therefore A = (rs)/[r(1s)] = (3sqrt5  5)/2, which is the limit of p_{n} as n goes to infinity.  We can also say that the expected value of the farthest left the toad ever goes is (1+sqrt5)/2.

« Last Edit: Jun 10^{th}, 2008, 12:17pm by Eigenray » 
IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: The Toad and the Water Lilies
« Reply #2 on: Jun 12^{th}, 2008, 6:14am » 
Quote Modify

Nicely done, Eigenray!


IP Logged 



ThudnBlunder
wu::riddles Moderator Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489


Re: The Toad and the Water Lilies
« Reply #3 on: Jun 12^{th}, 2008, 7:23am » 
Quote Modify

on Jun 12^{th}, 2008, 6:14am, Barukh wrote:Nicely done, Eigenray! 
 Yes, indeed! A less classical, more handwavy sort of solution is as follows: Let p = the probability that a toad starting at 1 regresses to 0 at some point. To never regress it must jump forward (probability = 1/2) and not subsequently regress three times (probability = 1  p^{3}) So we have 1  p = (1  p^{3})/2 giving p = (5  1)/2 Now consider the probability that during a particular jump the toad leaps over a lily that it never has and never will land on. For this to happen it must a) be jumping forward (probability = 1/2) b) never regress from where it lands (probability = 1  p) c) not have reached in the past the lily it is jumping over (probability = 1  p) So the probability that a particular jump carries the toad over a skipped lily = (1  p)^{2}/2 Since the toad travels at an average rate of 1/2 lily per jump, the fraction of skipped lilies = (1  p)^{2} Hence the fraction of water lilies it will land on = 1  (1  p)^{2} = p(2  p) = (35  5)/2 0.854102...


IP Logged 
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.



jollytall
Senior Riddler
Gender:
Posts: 585


Re: The Toad and the Water Lilies
« Reply #4 on: Aug 9^{th}, 2008, 12:40pm » 
Quote Modify

Shouldn't it be devided by two, for he is only jumping  practically  into one direction? The question talks about a long line, not a halfline.


IP Logged 



