[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 
Initial position of the frog is at 1, (i.e
)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
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
[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()