Can you solve The Frog Problem?

Matt uses a light themed IDE. That's all you need to know about Matt.

Why did the frog cross the river 10,000 times? To avoid a probability quiz.

Matt: Uses python, the king of languages for quick and dirty solutions. Also Matt: Does analysis in Excel

I went nearly crazy with this problem until I finally realized it's just the harmonic series... Wow, that was a lot of hours to in the end get to such a simple answer. If it wasn't for your Parker Square video, I might have given up or not even tried though, so thank you Matt.

If there are 0 places in front of the frog, we are already at the end E[0] = 0. If there are n places in front of the frog, then for each of the places (on which we land with probability 1/n) we have the expected number of jumps from there, plus the one jump to get there from the current position. E[n] = 1 + 1/n sum (i=0..(n-1)) E[i] Similarly, if there are n-1 places in front, we have: E[n-1] = 1 + 1/(n-1) sum (i=0..(n-2)) E[i] If we scale them appropriately and take the difference, we get: n E[n] - (n-1) E[n-1] = n - (n-1) + E[n-1] Solving for E[n], we obtain: E[n] = E[n-1] + 1/n This recurrence relation is immediately recognisable as the harmonic series sum (i=1..n) 1/i = 1 + 1/2 + 1/3 + 1/4 + ... + 1/n. The partial sum of this has no closed-form formula. For n=10 though we get the 10th harmonic number which is 7381/2520. It's well known that the harmonic series does not converge, but its growth is incredibly slow. The harmonic numbers can be approximated by ln(n) + 0.5772156649 (where this 0.577... is the Euler–Mascheroni constant). So even with 12000 lily pads there will less than 10 jumps on average. And with 1.5×10⁴³ lily pads there are less than 100 jumps on average.

The obvious starting point was to solve via recursion. Since landing with any number of pads remaining is the same as a problem starting with that many pads. For n possible spots, the answer is 1 (the frog must hop once now) plus 1/n * the solution for each smaller problem of i steps between i=1 and i=n-1 (the pads it might land that would require a further solution). But recursion is inefficient. Solving the same problem multiple times is often unnecessary. That's the case here were we just need to know the solution for each smaller n down to n=1. Instead of recursion, we can just keep a list of previous solutions as we work up. So f(n) = (f(1)+f(2)...f(n-1))/n +1 But again, we don't need each individual solution, just the running sum of solutions. And that sum is ingrained in each solution, so we don't need to keep a separate running total. We just need to know the values of n-1 and f(n-1). We just squash f(1)+f(2)+...f(n-1) into a variable for the running sum r, we get f(n)= r/n+1, and from that can see that r= n*(f(n)-1). Plug that in to get the old running sum from f(n-1) and we get f(n) = (f(n-1)+((n-1)*(f(n-1)-1)))/n + 1 Simplify f(n) = (f(n-1)+(n-1)*f(n-1)-(n-1))/n + 1 f(n) = (n*f(n-1)-n+1)/n + 1 f(n) = f(n-1) - n/n +1/n + 1 f(n) = f(n-1) + 1/n Which is kind of amazing. That's the algebraic notation for the harmonic series. The frog problem is the harmonic series. (n=10 is 7381/2520). But knowing that it is the harmonic series, we need to re-examine the problem to find the real beauty here. There is a 1/1 chance that the frog reaches the far bank eventually. But there is also a 1/2 chance that the frog visits the last lily pad along his journey. Which makes sense. At any step, no matter how far back the frog is, there are equal chances of landing on that pad or skipping it to the end. There are also chances of landing on a pad before it, but those chances don't matter since no matter where else the frog lands, a jump from that spot also holds to the equal probability of landing on or skipping the last pad. And this continues. For the pad before that, there are 2 chances to skip it and 1 to land on it. 1/3 odds that pad is visited. 1/4 for the pad before that, then 1/5, 1/6, etc. All a clever disguise for the harmonic series in probability.

The answer is the harmonic numbers (a_n = \sum_{i=1}^n{\frac{1}{n}}) Proof: Let a_n be the total number of jumps needed. We are looking for a value for a_10 and a formula for a_n. To jump n leaves the frog does one of the n possible jumps with probability 1/n to any leaf i and then has to jump a number of n - i leaves in a_{n-i} ways. Thus, we get the recurrence relation: a_1 = 1; a_n = 1/n + 1/n(a_1 + 1) + 1/n(a_2 + 1) + ... 1/n(a_{n-1} + 1) where each +1 comes from the initial jump. After some algebra, the recurrence is: a_1 = 1; a_n = 1 + 1/n \sum_{i=1}^{n-1}{a_i}. From here, try to get a_n in terms of a_{n-1}: a_n = 1 + 1/n * (n-1) / (n-1) * \sum_{i=1}^{n-1}{a_i} # multiply by x/x doesn't change result a_n = 1 + (n-1) / n * (1 / (n - 1)) * \sum{i=1}^{n-1}{a_i} # reorder factors a_n = 1 + (1 - 1/n) * (1 / (n - 1) * \sum{i=1}^{n-2}{a_i} + a_{n-1} / (n - 1)) # extract the last term of the sum a_n = 1 + (1 - 1/n) * (a_{n-1} - 1 + a_{n-1} / (n-1)) # use the same formula from the start but for a_{n-1} a_n = 1/n + a_{n-1} # expand all parantheses, do algebra But that with a_1 = 1 gives a_n = \sum_{i=1}^n{\frac{1}{n}}, the harmonic numbers. And indeed, even experimenting we get to the same solution: a_10 = 2.92880931. I used the following script to simulate: import random PRINT_EVERY = 100000 def jump(end=10): pos = 0 ret = 0 while pos != end: pos = random.randrange(pos, end) + 1 ret += 1 return ret sum_jumps = 0 num_tries = 0 while True: for _ in range(PRINT_EVERY): sum_jumps += jump() num_tries += 1 print("Avg {:.8f} ({} / {})".format( (sum_jumps + 0.0) / num_tries, sum_jumps, num_tries)) And it prints: ... Avg 2.92880365 (366686217 / 125200000) Avg 2.92880069 (366978727 / 125300000) Avg 2.92880195 (367271764 / 125400000) Avg 2.92880530 (367565065 / 125500000) Avg 2.92880385 (367857764 / 125600000) Avg 2.92880500 (368150789 / 125700000) Avg 2.92880931 (368444211 / 125800000) I'm thus confident that the solution above is real and works.

You: Jumping hurdles I, an intellectual: AUTOFROG ENABLED

Problem: ...and do NOT use recurrence relations. Parker Solution: So I used a recurrence relation.

Initial reaction: "It's obviously 3" Make a simulation of just one iteration: get 3. Leave satisfied

I think it's important to figure out what is on the other side. What's the frog's motivation? Is it trying to be stealthy? Is it trying to get to a potential mate before a larger more attractive frog does? Did he wake up late and is rushing into work? I think we need to go deeper into this issue.

5:48 Bec's scrawling reminds me SO much of me, aged about 12, writing out all the possible games of noughts and crosses in a small notebook. Haha!

The expected number of jumps required to get to pad 'n' will be, I think, the sum of the harmonic series Hn=Σ(1/n). Matt's simulation also seems to give that result. Here's why I think that's the case: For n=1, number of expected jumps is, trivially, one. For n=2, initially the frog has an equal probably of jumping on both pads, thus assigning them a score of half. This means that the frog will jump on each pad 0.5 number of times. Then, on the next step, if it's on pad 2 and not the final pad, expected number of jumps is, again, 1. Thus, total for the last pad is 1+1/2 For n=3, it's 1/3 for the first pad, 1/2+1/3 for the second and 1+1/2+1/3 for the final pad. For the general case, the total is Σ(1/n) Edit: I think what I did is a Markov chain.

"import random" inside a while loop, that's some classic Parker Python Programming

I got the same answer as Binary Agenda, going kind of backwards. First I computed the recurrence relation (same one Matt found) and computed its values. I graphed it and it looked like it was growing logarithmically, and with a little playing around I found it was growing like ln(n) + something. Looking at this difference at n=1000 to get a good estimate for something I found it was 0.577. I recognized 0.577 as a special thing but I couldn't remember what it was! I tried wolfram alpha, which is usually good for giving nearby closed forms for numbers, to no avail. (ln(sqrt(pi)) was my best guess, but it wasn't quite hitting) Anyway... I just relaxed my mind a minute and thought, out of nowhere, we're dealing with fractions! The harmonic numbers (1/1 + 1/2 + 1/3 + ... + 1/n) grows logarithmically and is a bunch of fractions. So I tried it and it matched exactly. From there it wasn't too hard to prove that the harmonic numbers satisfied this recurrence relation, without using anything too advanced. (But not as elegantly as Binary Agenda) And of course after this I realized what 0.577 was! The Euler-Macheroni constant -- which is defined as the limiting difference between the n'th harmonic number and ln(n). It's definition is exactly the context where it showed up in this problem. Why didn't wolfram alpha catch that! Come on, that's an important one! log(sqrt(pi)), really?! Anyway, fun problem! I like problems like this where I have to use a combination of empirical investigation and formal thinking to get it. Also kudos to Binary Agenda for their elegant solution. BTW the exact solution for 10 is 1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/9 + 1/10 = 7381/2520 = 2.928 968253 968253 ...

After working this out with my favorite math software, Microsoft Paint, my guess is 4. I wish I could upload my glorious image here, but a boring old number will have to do.

I'll try with real frogs. Simulations are not precise enough. 😂

I'm going with 3. Because that seems right based on the frogs in my head.

The answer is: integral from 0 to 1 of (x^10-1)/(x-1) = 7381/2520

Summing the averages going to the next landing location from each position, in turn, should add up to the total average? 1/10 + 1/9 + 1/8 + 1/7 + 1/6 + 1/5 + 1/4 + 1/3 + 1/2 + 1