<center> <img src = "https://i.imgsafe.org/6c/6cb75b6a5b.png" /></center>
[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, <img src="http://latex.codecogs.com/gif.latex?\mathbb{Z}" title="\mathbb{Z}" /> . Imagine the real axis with integers marked by circles. 

<center> <img src = "https://i.imgsafe.org/63/63de9749af.png" /></center>

A nasty frog leaps among these circles according to the following rules of random walk. If we denote the position of the frog at <img src="http://latex.codecogs.com/gif.latex?n" title="n" />-th step  as <img src="http://latex.codecogs.com/gif.latex?X_n" title="X_n" align = "center"/>

1. Initial position of the frog is at 1, (i.e <img src="http://latex.codecogs.com/gif.latex?X_0&space;=&space;1" title="X_0 = 1" align = "center"/>)

2. In each move, the frog leaps either <img src="http://latex.codecogs.com/gif.latex?a" title="a" /> circles to the right, or <img src="http://latex.codecogs.com/gif.latex?b" title="b" /> circles to the left. Also both possibilities have same probability, <img src="http://latex.codecogs.com/gif.latex?\frac{1}{2}" title="\frac{1}{2}" align = "center"/> . In other words, 

<center> <img src="http://latex.codecogs.com/gif.latex?X_{n&plus;1}&space;=&space;\begin{cases}&space;X_n&space;&plus;&space;2&space;&&space;(\text{with&space;probability&space;}&space;\frac{1}{2})&space;\\&space;\text{or}&space;\\&space;X_n&space;-&space;1&space;&&space;(\text{with&space;probability&space;}&space;\frac{1}{2})&space;\end{cases}" title="X_{n+1} = \begin{cases} X_n + a & (\text{with probability } \frac{1}{2}) \\ \text{or} \\ X_n - b & (\text{with probability } \frac{1}{2}) \end{cases}" /> </center>

Then the question is 

<center> <b> <i> What is the probability that the frog ever reaches the origin, (i.e. point 0) ? </i> </b> </center>

This question is somewhat different from the original form. Many random walk analysis assume initial point to be the origin, (<img src="http://latex.codecogs.com/gif.latex?X_0&space;=&space;0" title="X_0 = 0" align = "center"/>) and investigate the probability of eventual return. Also many random walk models <img src="http://latex.codecogs.com/gif.latex?X_{n&plus;1}&space;=&space;X_{n}&space;\pm&space;1" title="X_{n+1} = X_{n} \pm 1" align = "center"/> , 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 <img src="http://latex.codecogs.com/gif.latex?2" title="a" /> and <img src="http://latex.codecogs.com/gif.latex?1" title="b" /> .  Suppose the frog eventually arrived at the origin after <img src="http://latex.codecogs.com/gif.latex?n" title="n" /> number of steps. If <img src="http://latex.codecogs.com/gif.latex?x,&space;y" title="x, y" align=  "center"/> are number of leaps to left and right respectively, we get the following equation

<center> <img src="http://latex.codecogs.com/gif.latex?2x-y&space;&plus;&space;1&space;=&space;0&space;\implies&space;y&space;-&space;2x&space;=&space;1" title="ax-by + 1 = 0 \implies by - ax = 1" /> </center>

This equation (also called [linear Diophantine equation](https://en.wikipedia.org/wiki/Diophantine_equation#Linear_Diophantine_equations)) has __integer__ solutions if and only if 

<center> <img src="http://latex.codecogs.com/gif.latex?\gcd(2, 1)\&space;|&space;\&space;1&space;\iff&space;\gcd(2,1)&space;=&space;1" title="\gcd(a,b)\ | \ 1 \iff \gcd(a,b) = 1" /> </center>

which is indeed correct. So <img src="http://latex.codecogs.com/gif.latex?X_n&space;=&space;0" title="X_n = 0" align = "center"/> 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 <img src="http://latex.codecogs.com/gif.latex?n" title="n" /> leaps, denoting as <img src="http://latex.codecogs.com/gif.latex?P_n" title="P_n" align = "center"/> . Note that we are concerning all the possibilities of crossing the origin within, not at the specific <img src="http://latex.codecogs.com/gif.latex?n" title="n" />-th step. In equivalent form, <img src="http://latex.codecogs.com/gif.latex?P_n" title="P_n" align = "center"/> is

<center> <img src="http://latex.codecogs.com/gif.latex?\frac{\&hash;&space;\text{&space;of&space;trajectories&space;of&space;first&space;}n\text{&space;leaf&space;that&space;pass&space;through&space;0}&space;}{2^n}" title="\frac{\# \text{ of trajectories of first }n\text{ leaf that pass through 0} }{2^n}" /> </center> 

It is clear that the sequence <img src="http://latex.codecogs.com/gif.latex?\left\{&space;P_n&space;\right\}" title="\left\{ P_n \right\}" align = "center"/> is monotonic and bounded above by 1, so that by [Monotone convergence theorem](https://en.wikipedia.org/wiki/Monotone_convergence_theorem) it has the limit

<center> <img src="http://latex.codecogs.com/gif.latex?P&space;=&space;\lim_{n&space;\rightarrow&space;\infty}&space;P_n" title="P = \lim_{n \rightarrow \infty} P_n" /> </center>

Let <img src="http://latex.codecogs.com/gif.latex?a_i" title="a_i" align = "center"/> denote the number of trajectories of the first <img src="http://latex.codecogs.com/gif.latex?i" title="i" /> leaps such that the frog reaches 0 by the <img src="http://latex.codecogs.com/gif.latex?i" title="i" />-th leap and never before. Then using <img src="http://latex.codecogs.com/gif.latex?\left\{&space;a_i&space;\right\}" title="\left\{ a_i \right\}" align = "center"/> , we can restate <img src="http://latex.codecogs.com/gif.latex?P" title="P" /> as infinite sum

<center> <img src="http://latex.codecogs.com/gif.latex?P&space;=&space;\sum_{i=1}^{\infty}&space;\frac{a_i}{2^i}" title="P = \sum_{i=1}^{\infty} \frac{a_i}{2^i}" /> </center> 

because <img src="http://latex.codecogs.com/gif.latex?\frac{a_i}{2^i}" title="\frac{a_i}{2^i}" align  ="center"/> denotes the __probability__ that frog reaches 0 by the the <img src="http://latex.codecogs.com/gif.latex?i" title="i" />-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 <img src="http://latex.codecogs.com/gif.latex?b_i" title="b_i" align = "center"/> of trajectories starting at the number <img src="http://latex.codecogs.com/gif.latex?2" title="a" /> that first reach 0 by the <img src="http://latex.codecogs.com/gif.latex?i" title="i" />-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 <img src="http://latex.codecogs.com/gif.latex?j" title="j" align = "center"/> be the number of the leap by which 1 is first reached. This is nothing but <img src="http://latex.codecogs.com/gif.latex?a_j" title="a_j" align = "center"/>, since going from 2 to 1 is totally __equivalent (isomorphic)__ to going from 1 to 0. Then, <img src="http://latex.codecogs.com/gif.latex?i-j" title="i-j" align = "center"/> leaps remain to move from 1 to 0, and the number of ways for these <img src="http://latex.codecogs.com/gif.latex?i-j" title="i-j" align  = "center"/> leaps is <img src="http://latex.codecogs.com/gif.latex?a_{i-j}" title="a_{i-j}" align = "center" /> . So for a given <img src="http://latex.codecogs.com/gif.latex?j" title="j" /> , summing up all the possible values for <img src="http://latex.codecogs.com/gif.latex?j" title="j" align  ="center"/> (which is <img src="http://latex.codecogs.com/gif.latex?j=1,2,...,i-1" title="j=1,2,...,i-1" align = "center"/>) we get 

<center> <img src="http://latex.codecogs.com/gif.latex?b_i&space;=&space;\sum_{j=1}^{i-1}&space;a_j&space;a_{i-j}" title="b_i = \sum_{j=1}^{i-1} a_j a_{i-j}" /> </center>

Furthermore, let's examine trajectories starting at the number 3. If we define the number <img src="http://latex.codecogs.com/gif.latex?c_i" title="c_i" /> to be the number of trajectories starting at the number 3 and __first__ reaching 0 by the <img src="http://latex.codecogs.com/gif.latex?i" title="i" />-th step. As before, in order that such a trajectory reaches 0, it has to reach 2 first. Let <img src="http://latex.codecogs.com/gif.latex?j" title="j" align = "center"/> be the number of the leap by which 2 is first reached. This is nothing but <img src="http://latex.codecogs.com/gif.latex?a_j" title="a_j" align = "center"/> (it is just the same reasoning!) , Then <img src="http://latex.codecogs.com/gif.latex?i-j" title="i-j" align = "center"/> leaps remain to move from 2 to 0, and the number of ways for these <img src="http://latex.codecogs.com/gif.latex?i-j" title="i-j" align = "center"/>  leaps is <img src="http://latex.codecogs.com/gif.latex?b_{i-j}" title="b_{i-j}" align = "center"/> . so for a given <img src="http://latex.codecogs.com/gif.latex?j" title="j" align= "center"/> , summing up all the possible values we get 

<center> <img src="http://latex.codecogs.com/gif.latex?c_i&space;=&space;\sum_{j=1}^{i-1}&space;a_j&space;b_{i-j}" title="c_i = \sum_{j=1}^{i-1} a_j b_{i-j}" /> </center>


## 4. Recurrence Relation to Generating Functions

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

<center> <img src="http://latex.codecogs.com/gif.latex?\left\{&space;a_i&space;\right\},&space;\left\{&space;b_i&space;\right\},&space;\left\{&space;c_i&space;\right\}" title="\left\{ a_i \right\}, \left\{ b_i \right\}, \left\{ c_i \right\}" /> </center>

to functions 

<center> <img src="http://latex.codecogs.com/gif.latex?a(x),&space;b(x),&space;c(x)" title="a(x), b(x), c(x)" /> </center>

such that 

<center> <img src="http://latex.codecogs.com/gif.latex?\begin{align*}&space;a(x)&space;=&space;a_1x&space;&plus;&space;a_2&space;x^2&space;&plus;&space;a_3&space;x^3&space;&plus;&space;...&space;=&space;\sum_{i=1}^{\infty}&space;a_i&space;x^i\\&space;b(x)&space;=&space;b_1x&space;&plus;&space;b_2&space;x^2&space;&plus;&space;b_3&space;x^3&space;&plus;&space;...&space;=&space;\sum_{i=1}^{\infty}&space;b_i&space;x^i\\&space;c(x)&space;=&space;c_1x&space;&plus;&space;c_2&space;x^2&space;&plus;&space;c_3&space;x^3&space;&plus;&space;...&space;=&space;\sum_{i=1}^{\infty}&space;c_i&space;x^i\\&space;\end{align*}" title="\begin{align*} a(x) = a_1x + a_2 x^2 + a_3 x^3 + ... = \sum_{i=1}^{\infty} a_i x^i\\ b(x) = b_1x + b_2 x^2 + b_3 x^3 + ... = \sum_{i=1}^{\infty} b_i x^i\\ c(x) = c_1x + c_2 x^2 + c_3 x^3 + ... = \sum_{i=1}^{\infty} c_i x^i\\ \end{align*}" /> </center>


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

<center> <img src="http://latex.codecogs.com/gif.latex?\begin{align*}&space;b(x)&space;&=&space;\sum_{i=1}^{\infty}&space;b_i&space;x^i&space;\\&space;&=&space;\sum_{i=1}^{\infty}&space;\left(&space;\sum_{j=1}^{i-1}&space;a_j&space;a_{i-j}&space;\right&space;)x^i&space;\\&space;&=&space;\left(&space;\sum_{i=1}^{\infty}&space;a_i&space;x^i&space;\right)\left(&space;\sum_{i=1}^{\infty}&space;a_i&space;x^i&space;\right)&space;\\&space;&=&space;\left(&space;\sum_{i=1}^{\infty}&space;a_i&space;x^i&space;\right)^2&space;=&space;a^2(x)&space;\end{align*}" title="\begin{align*} b(x) &= \sum_{i=1}^{\infty} b_i x^i \\ &= \sum_{i=1}^{\infty} \left( \sum_{j=1}^{i-1} a_j a_{i-j} \right )x^i \\ &= \left( \sum_{i=1}^{\infty} a_i x^i \right)\left( \sum_{i=1}^{\infty} a_i x^i \right) \\ &= \left( \sum_{i=1}^{\infty} a_i x^i \right)^2 = a^2(x) \end{align*}" /> </center>

if we introduce dummy variable <img src="http://latex.codecogs.com/gif.latex?a_0&space;=&space;0" title="a_0 = 0" align = "center"/> and 

<center> <img src="http://latex.codecogs.com/gif.latex?\begin{align*}&space;c(x)&space;&=&space;\sum_{i=1}^{\infty}&space;c_i&space;x^i&space;\\&space;&=&space;\sum_{i=1}^{\infty}&space;\left(&space;\sum_{j=1}^{i-1}&space;a_j&space;b_{i-j}&space;\right&space;)x^i&space;\\&space;&=&space;\left(&space;\sum_{i=1}^{\infty}&space;a_i&space;x^i&space;\right)\left(&space;\sum_{i=1}^{\infty}&space;b_i&space;x^i&space;\right)&space;=&space;a(x)b(x)=&space;a^3(x)&space;\end{align*}" title="\begin{align*} c(x) &= \sum_{i=1}^{\infty} c_i x^i \\ &= \sum_{i=1}^{\infty} \left( \sum_{j=1}^{i-1} a_j b_{i-j} \right )x^i \\ &= \left( \sum_{i=1}^{\infty} a_i x^i \right)\left( \sum_{i=1}^{\infty} b_i x^i \right) = a(x)b(x)= a^3(x) \end{align*}" /> </center>

if we introduce dummy variable <img src="http://latex.codecogs.com/gif.latex?b_0&space;=&space;0" title="b_0 = 0" align = "center"/> .  

## 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 <img src="http://latex.codecogs.com/gif.latex?a_1&space;=&space;1" title="a_1 = 1" align = "center"/>) , or it leaps to the number 3.  In the latter case, it has by definition, <img src="http://latex.codecogs.com/gif.latex?c_{i-1}" title="c_{i-1}" /> possibilities of reaching 0 for the first time after the next <img src="http://latex.codecogs.com/gif.latex?i-1" title="i-1" /> leaps. 

<center> <img src = "https://i.imgsafe.org/6b/6bdcf2e0c9.png" /></center>

Hence we get a direct relationship between <img src="http://latex.codecogs.com/gif.latex?a" title="a" /> and <img src="http://latex.codecogs.com/gif.latex?c" title="c" /> by 

<center> <img src="http://latex.codecogs.com/gif.latex?a_i&space;=&space;\begin{cases}&space;a_1&space;&&space;(i&space;=&space;1)&space;\\&space;c_{i-1}&space;&&space;(i&space;>&space;1)&space;\end{cases}" title="a_i = \begin{cases} a_1 & (i = 1) \\ c_{i-1} & (i > 1) \end{cases}" /> </center> 

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

<center> <img src="http://latex.codecogs.com/gif.latex?\begin{align*}&space;a(x)&space;&=&space;a_1&space;x&space;&plus;&space;\sum_{i&space;>&space;1}&space;a_ix^i&space;\\&space;&=&space;x&space;&plus;&space;\sum_{i&space;>&space;1}&space;c_{i-1}&space;x^i&space;\\&space;&=&space;x&space;&plus;&space;(c_1&space;x^2&space;&plus;&space;c_2&space;x^3&space;&plus;&space;...)&space;\\&space;&=&space;x&space;&plus;&space;x&space;c(x)&space;=&space;x&space;&plus;&space;x&space;a^3(x)&space;\end{align*}" title="\begin{align*} a(x) &= a_1 x + \sum_{i > 1} a_ix^i \\ &= x + \sum_{i > 1} c_{i-1} x^i \\ &= x + (c_1 x^2 + c_2 x^3 + ...) \\ &= x + x c(x) = x + x a^3(x) \end{align*}" /> </center>

using <img src="http://latex.codecogs.com/gif.latex?c(x)&space;=&space;a^3(x)" title="c(x) = a^3(x)" align = "center"/> . 

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

<center> <img src="http://latex.codecogs.com/gif.latex?P&space;=&space;\sum_{i=1}^{\infty}&space;\frac{a_i}{2^i}" title="P = \sum_{i=1}^{\infty} \frac{a_i}{2^i}" /> </center> 

This is nothing but <img src="http://latex.codecogs.com/gif.latex?a(1/2)" title="a(1/2)"  align = "center"/> by definition of <img src="http://latex.codecogs.com/gif.latex?a(x)" title="a(x)" align = "center"/> . Then using above relationship, 

<center> <img src="http://latex.codecogs.com/gif.latex?a&space;(1/2)&space;=&space;\frac{1}{2}&space;&plus;&space;\frac{1}{2}&space;a^3(1/2)&space;\iff&space;P&space;=&space;\frac{1}{2}&space;&plus;&space;\frac{P^3}{2}" title="a (1/2) = \frac{1}{2} + \frac{1}{2} a^3(1/2) \iff P = \frac{1}{2} + \frac{P^3}{2}" /> </center>

solving this cubic equation gives 

<center> <img src="http://latex.codecogs.com/gif.latex?P^3&space;-2P&space;&plus;&space;1&space;=&space;(P&space;-&space;1)(P^2&space;&plus;&space;P&space;-&space;1)&space;=&space;0&space;\iff&space;P=1&space;\text{&space;or&space;}&space;P&space;=&space;\frac{-1&space;\pm&space;\sqrt{5}}{2}" title="P^3 -2P + 1 = (P - 1)(P^2 + P - 1) = 0 \iff P=1 \text{ or } P = \frac{-1 \pm \sqrt{5}}{2}" /> </center>

## 6. Why Not P = 1? 
[4]

First, 

<center> <img src="http://latex.codecogs.com/gif.latex?P&space;=&space;\frac{-1&space;-&space;\sqrt{5}}{2}&space;<&space;0" title="P = \frac{-1 - \sqrt{5}}{2} < 0" align = "center"/></center>

is not the solution. The only choice is 

<center> <img src="http://latex.codecogs.com/gif.latex?1&space;\text{&space;or&space;}\phi&space;:=&space;\frac{-1&space;&plus;&space;\sqrt{5}}{2}" title="1 \text{ or }\phi := \frac{-1 + \sqrt{5}}{2}" />
</center> 

the __golden ratio__ . Then why not <img src="http://latex.codecogs.com/gif.latex?P&space;=&space;1" title="P = 1" align = "center"/> ? First, since 

<center> <img src="http://latex.codecogs.com/gif.latex?P&space;=&space;\sum_{i=1}^{\infty}&space;\frac{a_i}{2^i}" title="P = \sum_{i=1}^{\infty} \frac{a_i}{2^i}" /> </center>

converges and <img src="http://latex.codecogs.com/gif.latex?a_i&space;\geq&space;0" title="a_i \geq 0" align = "center"/> , we have 

<center> <img src="http://latex.codecogs.com/gif.latex?a(x)&space;=&space;\sum_{i=1}^{n}&space;a_{i}x^i&space;\leq&space;P&space;=&space;a(1/2)" title="a(x) = \sum_{i=1}^{n} a_{i}x^i \leq P = a(1/2)" /> </center>

for <img src="http://latex.codecogs.com/gif.latex?x&space;\in&space;(0,&space;1/2)" title="x \in (0, 1/2)" align  ="center"/> is well -defined (by comparison test) and is indeed increasing, since 

<center> <img src="http://latex.codecogs.com/gif.latex?x_1^i&space;<&space;x_2&space;^i&space;\text{&space;for&space;}&space;0&space;<&space;x_1&space;<&space;x_2&space;<&space;1" title="x_1^i < x_2 ^i \text{ for } 0 < x_1 < x_2 < 1" /> </center>

so, the graph <img src="http://latex.codecogs.com/gif.latex?x&space;=&space;\frac{a}{a^3&space;&plus;&space;1}" title="x = \frac{a}{a^3 + 1}" align = "center"/> on a <img src="http://latex.codecogs.com/gif.latex?ax" title="ax" />-plane where <img src="http://latex.codecogs.com/gif.latex?0&space;<&space;x&space;\leq&space;1/2" title="0 < x \leq 1/2" align = "center"/> 

<center> <img src = "https://i.imgsafe.org/6c/6c7b21073f.png" /> </center>

should be left side of golden ratio <img src="http://latex.codecogs.com/gif.latex?\phi,&space;0&space;<&space;a&space;<&space;\phi" title="\phi, 0 < a < \phi" align = "center" /> . Hence <img src="http://latex.codecogs.com/gif.latex?P&space;=&space;a(1/2)&space;=&space;\phi" title="P = a(1/2) = \phi" align = "center"/> . 

## 7. Conclusion
A nasty frog going 2 steps right or 1 step left have probability <img src="http://latex.codecogs.com/gif.latex?\phi&space;=&space;(-1&space;&plus;&space;\sqrt{5})/2" title="\phi = (-1 + \sqrt{5})/2" align = "center"/> 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](http://getdrawings.com/img/frog-silhouette-6.png)

[2] [<___Pushing Random Walk Beyond Golden Ratio___> by Ehsan Amiri & Evgeny Skvortsov](https://pdfs.semanticscholar.org/d292/4e4468e325f547032ae30b1f024d414db643.pdf)

[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 <img src="http://latex.codecogs.com/gif.latex?n=200" title="n=200" /> number of steps via Python.

<center> <img src = 'https://i.imgsafe.org/6c/6ce9a10a7f.png' /></center>

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... &#128517;

```
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()
```