[1]

Random Walk of a Frog & the Golden Ratio

0. Apart from Symmetry

[2]

A random walk is a mathematical object that describes a path that consists of a succession of random steps on some mathematical space. To be simple, let's just assume a random walk on the integer number line, . Imagine the real axis with integers marked by circles.

A nasty frog leaps among these circles according to the following rules of random walk. If we denote the position of the frog at -th step as

1. Initial position of the frog is at 1, (i.e )

2. In each move, the frog leaps either circles to the right, or circles to the left. Also both possibilities have same probability, . In other words,

Then the question is

What is the probability that the frog ever reaches the origin, (i.e. point 0) ?

This question is somewhat different from the original form. Many random walk analysis assume initial point to be the origin, () and investigate the probability of eventual return. Also many random walk models , in which the movement is symmetric. However, the nasty frog refuses to return to his/her home, rather the frog wants to go to his/her neighbor's house next to it.

A well known fact about 1 dimensional random walk is that the probability of eventual return is one. In other words, if we do not give further restrictions on the movement, eventual return is guaranteed. So, does the same result apply to our nasty frog as well? Let's find out.

1. Well Definedness

Before we get into precise mathematical analysis, let's talk about the parameters and . Suppose the frog eventually arrived at the origin after number of steps. If are number of leaps to left and right respectively, we get the following equation

This equation (also called linear Diophantine equation) has integer solutions if and only if

which is indeed correct. So is not an impossible output, the random walk model is well defined.

2. Clarification

Next we have to clarify what we mean by such probability. It is easy to define the probability that the frog reaches 0 within the first leaps, denoting as . Note that we are concerning all the possibilities of crossing the origin within, not at the specific -th step. In equivalent form, is

It is clear that the sequence is monotonic and bounded above by 1, so that by Monotone convergence theorem it has the limit

Let denote the number of trajectories of the first leaps such that the frog reaches 0 by the -th leap and never before. Then using , we can restate as infinite sum

because denotes the probability that frog reaches 0 by the the -th leap and never before.

3. Recurrence Relation

[3]

For solving the problem, it will be useful to look also at trajectories starting at numbers other than 1. For instance, what is the number of trajectories starting at the number that first reach 0 by the -th leap?

In order that such a trajectory reaches 0, it has to reach 1 first. Note that we use the fact that leaps to the left are always by 1, and so the frog cannot reach 0 from 2 without leaping to 1 first. Let be the number of the leap by which 1 is first reached. This is nothing but , since going from 2 to 1 is totally equivalent (isomorphic) to going from 1 to 0. Then, leaps remain to move from 1 to 0, and the number of ways for these leaps is . So for a given , summing up all the possible values for (which is ) we get

Furthermore, let's examine trajectories starting at the number 3. If we define the number to be the number of trajectories starting at the number 3 and first reaching 0 by the -th step. As before, in order that such a trajectory reaches 0, it has to reach 2 first. Let be the number of the leap by which 2 is first reached. This is nothing but (it is just the same reasoning!) , Then leaps remain to move from 2 to 0, and the number of ways for these leaps is . so for a given , summing up all the possible values we get

4. Recurrence Relation to Generating Functions

Now, the key tool for analyzing such numbers is generating function. We correspond each sequence

to functions

such that

Then the recurrence relations we obtained in Section 3 are equivalent to

if we introduce dummy variable and

if we introduce dummy variable .

5. Clever Trick - Different point of view

Lastly, let us investigate trajectories starting at 1 from a different point of view. By the first move, either the frog reaches 0 directly (which is nothing but saying ) , or it leaps to the number 3. In the latter case, it has by definition, possibilities of reaching 0 for the first time after the next leaps.

Hence we get a direct relationship between and by

Converted to a relation between the generating functions we defined in Section 4,

using .

---

Now let's go back to the original question, which is finding the limiting probability

This is nothing but by definition of . Then using above relationship,

solving this cubic equation gives

6. Why Not P = 1?

[4]

First,

is not the solution. The only choice is

the golden ratio . Then why not ? First, since

converges and , we have

for is well -defined (by comparison test) and is indeed increasing, since

so, the graph on a -plane where

should be left side of golden ratio . Hence .

7. Conclusion

A nasty frog going 2 steps right or 1 step left have probability of eventual arrival to his/her neighbor's house ! haha

The change of steps give the frog asymmetric movement, but it produces beautiful golden ratio !

8. Citations

[1] Image Source Link

[2] <Pushing Random Walk Beyond Golden Ratio> by Ehsan Amiri & Evgeny Skvortsov

[3] Book <Invitation to Discrete Mathematics> by Jiri Matousek, page 355

[4] Book <Invitation to Discrete Mathematics> by Jiri Matousek, page 356

---

Lastly, this is my random walk simulation for number of steps via Python.

Due to asymmetric movement, frog is moving away from the neighborhood of origin. This clearly shows that the probability of arrival to neighbor's house is NOT 1, should be strictly less than 1... 😅

import matplotlib.pyplot as plt
import numpy as np

def random_walk_1D(n):
    elements = [2, -1]
    probabilities = [0.5, 0.5]
    x = [1]    
    for i in range(1, n + 1):
        y = np.random.choice(elements, 1, p = probabilities)
        x.append(x[i-1] + y)    
    return x
    
#----------------------#
n = 200
N = [i for i in range(n+1)]

plt.plot(N, random_walk_1D(n))
plt.grid(axis = 'y')
plt.xlabel('n')
plt.ylabel('$X_n$')
plt.show()