wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> The Toad and the Water Lilies
        
(Message started by: ThudanBlunder on Jun 6^th, 2008, 9:40am)

Title: The Toad and the Water Lilies
Post by ThudanBlunder on Jun 6^th, 2008, 9:40am

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?

Title: Re: The Toad and the Water Lilies
Post by Eigenray on Jun 10^th, 2008, 12:15pm

Bit tricky, this one, but nice:

[hideb]Let p_n be the probability that the toad ever lands on the pad n units to the right.
We have p₀ = 1, and for n != 0,
p_n = (p_n-2+p_n+1)/2,
or p_n+1 = 2p_n - p_n-2.
The characteristic polynomial of this recurrence is
x³ - 2x² + 1 = (x-1)(x²-x-1),
which has roots 1, r, and s, where r = (1+sqrt 5)/2, s = (1-sqrt 5)/2.
But because the recurrence only holds for n!=0, we have to solve it twice:
p_n = A + Brⁿ + Csⁿ, n >= -1;
p_n = X + Yrⁿ + Zsⁿ, 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₀ = 1. This gives A+C=1, Y=1.
Equating the two formula for p_-1 gives finally
1/r = A+C/s = A+(1-A)/s,
and therefore
A = (r-s)/[r(1-s)] = (3sqrt5 - 5)/2,
which is the limit of p_n as n goes to infinity.[/hideb]
We can also say that the expected value of the farthest left the toad ever goes is [hide](1+sqrt5)/2[/hide].

Title: Re: The Toad and the Water Lilies
Post by Barukh on Jun 12^th, 2008, 6:14am

Nicely done, Eigenray! :D :D

Title: Re: The Toad and the Water Lilies
Post by ThudanBlunder on Jun 12^th, 2008, 7:23am

on 06/12/08 at 06:14:11, Barukh wrote:

Nicely done, Eigenray! :D :D

Yes, indeed!

A less classical, more hand-wavy sort of solution is as follows:
[hide]
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³)
So we have
1 - p = (1 - p³)/2
giving
p = (http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif5 - 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
Since the toad travels at an average rate of 1/2 lily per jump, the fraction of skipped lilies = (1 - p)²
Hence the fraction of water lilies it will land on
= 1 - (1 - p)²
= p(2 - p)
= (3http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif5 - 5)/2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/simeq.gif 0.854102...
[/hide]

Title: Re: The Toad and the Water Lilies
Post by jollytall on Aug 9^th, 2008, 12:40pm

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 half-line.