Python Implementation for the Recursive Solution

[AustinTSchaffer]

Hey Matt,

I've been thinking about this probably too much today and came up with a Python implementation of your recursive solution. I had worked out a slightly different equation on my own, but it turns out that it was exactly the same as yours. I'm really not a trained mathematician in any way, so please don't judge too harshly, I guess.

Anyway, I tossed it around and figured that this can be built up from simple cases, starting with 1 pad ahead of the frog. There's also a case for 0 hops ahead of the frog.

• 0 pads ahead of the frog means that the frog doesn't need to make any jumps. expectedhops(0) = 0
• 1 pad ahead of the frog means the frog only needs to make one jump, and has a 100% chance of choosing the one jump. expectedhops(1) = 1
• 2 pads ahead of the frog means the frog has a 50% chance of jumping straight to the end. The frog also has a 50% chance of jumping to a position where there is only one pad remaining, which is a case that has already been solved. We can reuse that value by adding 1, representing the number of hops it took to get to that position. expectedhops(2) = 0.5*1 + 0.5*(1 + expectedhops(1)) = 1.5
• 3 pads looks similar to 2 pads, except there's a 1/3 chance of jumping to any pad initially. expectedhops(3) = 0.3ish*1 + 0.3ish*(1+expectedhops(1)) + 0.3ish*(1+expectedhops(2))
• etc

The Python code I have is written to model this is below. I only figured that you'd be interested in it because it's a little bit faster in terms of performance since the results are calculated instead of being randomly generated, which will make it easier to test any explicit solutions. I even added some memoization, for a little bonus kick in performance. Should work on both Python 2.7 and Python 3.X, but really, you need to install Python 3.

def expected_hops(pads_remaining):
    """
    Calculates the expected number of hops that a frog will
    take if the frog can only hop along a single file line of pads
    in a single direction and cannot turn around and hop back
    but is able to hop any number of pads in the forward direction,
    regardless of the number of pads.
    """
    assert pads_remaining >= 0
    if pads_remaining == 0: return 0
    return (1.0 / pads_remaining) * sum((
        1 + expected_hops(i)
        for i in range(0, pads_remaining)
    ))

def memoize(function):
    """
    Caches the results of the input function.
    """
    _cache = {}
    def functionwrapper(x):
        if x not in _cache:
            _cache[x] = function(x)
        return _cache[x]
    return functionwrapper

expected_hops = memoize(expected_hops)

if __name__ == '__main__':
    for i in range(1, 101):
        print (i, expected_hops(i))

Fun fact, it appears that the expected number of hops for 10,000 lily pads is 9.78 hops, which is much lower than what I would have expected.

[AustinTSchaffer]

I gotta say though, I'm honestly amazed that you managed to write code while in a pub. Bravo.

[illustromancer]

The 10,000 lilly pad expected # steps is so low because, on average, for each given jump, the frog will jump half way between it's current position and the other bank (because the probabilities are uniformly distributed across all lilypads between the current one and the far bank). As a result, adding significant digits essentially adds more potential space for the frog to land in. EG for n=10 the frogs most likely path is 5, 7.5 (ie 7 or 8), 8.75 (ie 9), 10. For n=10,000 you have just given the frog more "space" in which it can land (ie you've put more space between the 9th lilypad and the far bank than in the n=10 case)

[pcholt]

When I saw how low the average was for 200 hops, I thought there was something wrong with my code, but it makes sense that there would be a logarithmic relationship at play here. Still, I can only contribute my monte carlo simulation, not a mathematical treatment.

[AustinTSchaffer]

Feeling kind of dumb right now, is the solution really this simple?

I had some extra time this morning and tried to express each term using only the previous term, and ended up with expectedhops(n) = expectedhops(n-1) + (1/n), which is a much simpler recursive definition than what I had before. It's so simple, I wondered if it would be possible to convert it a closed form solution.

eh(n) = eh(n-1) + (1/n)
eh(n) = eh(0) + (sum from 1 to n of (1/n))
eh(0) = 0
eh(n) = (sum from 1 to n) of (1/n)

To express this in Python syntax:

def expected_hops(pads):
    if pads <= 0: return 0
    return sum((1/n for n in range(1, pads+1)))

No need for output caching, because it's no longer a branching recursive function. Admittedly, this is where my math abilities stop, because I don't know how to go about converting a summation expression into a true closed-form solution, if that's even possible in this case.

[AustinTSchaffer]

Photo evidence of me working out.

[illustromancer]

For this problem it is that simple. For any given N, the summation you have at the bottom of your picture is the closed form solution. For any given N it is a finite sum of fractions, which is a closed form solution.

You can express it in an alternate way as a Markov Chain with an absorbing state and use matrix algebra to come up with the answer (which has the added benefit of being able to work out the expected number of jumps to any particular state...but that isn't necessary for the Frog Problem as written, we only need the expected number of jumps to the far bank).