The Frog Problem and Zipf’s Law

How Zipf’s Law appears in a surprising math problem

Recently I was working on some math problems when this especially interesting one came up:

Chad needs seven apples to make an apple strudel for Jordan. He is currently at 0 on the metric number line. Every minute, he randomly moves one meter in either the positive or the negative direction with equal probability. Arctica’s parents are located at +4 and 4 on the number line. They will bite Chad for kidnapping Arctica if he walks onto those numbers. Also, there is one apple located at each integer between 3 and 3, inclusive. Whenever Chad lands on an integer with an unpicked apple, he picks it. What is the probability that Chad picks all the apples without getting bitten by Arctica’s parents?

This specific one is question #25 of the Exeter Math Club Competition 2014 Speed Round. Currently, it’s a little wordy, so what’s it saying in math?

Basically, Chad (who’s position we will denote with x) is situated at 0 on the number line, and every minute he moves to either the left or right with equal probability. The question is asking for the probability that he reaches both +3 and -3 without reaching +4 or -4 at any point.

Our starting setup for the question.

Before Chad reaches -4 or 4, he necessarily needs to visit either -3 or 3. And it’s guaranteed that he will reach -3 or 3 at some point, which you can reason by thinking about a random walk:

count = 0
array = [0]
while count not in [-3, 3]:
    count += np.where(np.random.randint(0,2), 1, -1)
    array.append(count)
x = np.arange(len(array))
plt.plot(x, array, marker="o")
plt.plot([0, x[-1]], [3,3])
plt.plot([0, x[-1]], [-3,-3])
plt.ylim(-6, 6)
plt.xlim(0, len(x)-1)
plt.title(f"Random Walk eventually hits -3 or 3 at {len(x)-1}!");

Our random walk will hit 3 or -3, no matter how long it takes.

Now, since we know at some point Chad’s position will be -3 or 3, we can just pretend everything before never existed, and he was always at -3 or 3. (Without loss of generality, let it be -3.) From that point, the problem reduces to the probability of reaching 3 before reaching -4 (it’s impossible to reach 4 before 3, so that doesn’t have to be considered.)

Our new setup for the problem.

In essence, we’ve actually reduced this problem from a very specific one involving moving to -3 and 3 without reaching -4 and 4 into a much more general one, which is why I’ve given this more general problem the name of The Frog Problem, after a version in which it’s a frog that hops between lily pads on the number line. To make the interesting insights coming later a little easier to understand, I’m going to shift our number line 3 units to the right so that this frog is sitting at position 0, and it needs to get to 6 (maybe there’s a fly there or something) before it reaches -1 (a predator).

We just shifted our setup three units to the right.

Now, to actually solve for the probability of reaching 6 before reaching -1, we can use a combinatorial technique called Combinatorial States — for each state, in this case, what position Chad is at, we can calculate the probability of that state based on the probability of other states, and then solve the resulting system of equations.

So let’s start with some easy states:

What is P₋₁? Well, If Chad is at -1, he’s automatically failed, so the probability of getting to 3 before -4 is 0.

What about P₆? If Chad is at 6, he’s already succeeded, so the probability at 3 is 1.

Ok, that was easy. But what about, say, P₂? Since there’s a 1/2 chance of moving to P₁, and a 1/2 chance of moving to P₃, P₂ should be equal to P₁/2+P₃/2. You should take a moment to just check that that makes sense intuitively — the chance of success of P₂ depends on the chances of success where Chad moves next, so it should be some combination of the probabilities of positions immediately next to 2, i.e. 1 and 3.

We can use the same reasoning for P₂ on P₀, P₁ … P₅ to then construct a system of equations:

Then plugging P₋₁ = 0 and P₆ = 1 into the system of equations, and solving, we can get the following probabilities:

This is a really nice result that makes intuitive sense — First, the odds of success rise as the position, x, gets closer to 6, and even better, the probabilities are correlated to the length of the segment {-1, x}, or equivalently, Pₓ=(x+1)/7.

Part II: Extending the Frog Problem

But we can also extend these probabilities to values of x beyond -1 and 6 — for example, what is P₋₂? Since there is no way to skip certain values, any way to 6 has to go through -1, so the probability must be 0 — similarly, for P₇, there’s no way to get to -1 without going through 6, so the probability must be 1. We can graph this like so:

Graphing our extended probabilities over the x-axis.

But why do we need to set success to 6 or failure to -1? If we change this we can get different functions that move from 0 to 1 as x increases:

If the positions of our failure and success states are set to -5 and 7, we get this graph of probabilities.

We can even try considering scenarios where we don’t have an equal probability of moving left or right…

But we’re getting a little carried away, so let’s keep some of our parameters constant, specifically the position of our failure state, and visualize our probabilities a little differently: what if instead of our x-axis being the position, we instead graphed the probability by the position of our success state (in our example, 6)?

This gives us this graph, with multiple lines for different positions:

GRAPHSSSS.

So what’s interesting about this graph?

Well, it’s easy to see that regardless of where the position of our success state is, moving closer to it creates a linear increase in probability. It also might be seen that our multiple line graphs are actually just scaled variants of the same line graph, that of position zero, although it isn’t entirely obvious since they have different starting points.

But first, what’s Zipf’s Law?

Part III: Zipf’s Law

Zipf’s Law is a law that shows up in rankings — It was first discovered in languages but has also shown up in music, city sizes, and income distribution, among other things. As Wikipedia says:

Zipf’s law was originally formulated in terms of quantitative linguistics, stating that given some corpus of natural language utterances, the frequency of any word is inversely proportional to its rank in the frequency table. Thus the most frequent word will occur approximately twice as often as the second most frequent word, three times as often as the third most frequent word, etc.

Essentially, the 2nd most frequent or second-highest thing appears 1/2 as much as the first highest thing. In general, the nth ranking has 1/n as many occurrences as the most common. We can see this neat pattern with a log-log graph:

Side-by-side comparison of ideal Zipf’s Law and a real-life application of Zipf’s Law.

Note that the Zipf’s Law graphed above is just one version with specific parameters — You can find other versions that slightly deviate from this “ideal” Zipf’s Law but may better fit real-world data.

The exact Zipf’s Law formula is:

where x is the rank, y is the number of occurrences, and n is a controllable parameter, which we’ve set to n=1.

This is what happens when n is set to only 0.6:

Zipf’s Law with n=0.6

So what’s so significant about Zipf’s Law and The Frog Problem?

Well, if we again take a look at our graph of Zipf’s Law and our probability by position of our success state, specifically for position 0, we’ll notice that they are the same graph. We can compare the two:

A comparison of our two graphs.

Well, not exactly the same graph, but they are very similar! Let’s compare the two formulas:

Zipf’s Law:

Probability of Success for Position 0:

Yup, pretty similar. Zipf’s Law pops up in many places, and this is just one example! Pretty cool.