Summary
In the following exercise, a simple random walk in one-dimension will be defined and assessed. An analytical approach formulated and a solution presented. Specifically, a random walk with a partially reflecting barrier at \(0\) will be considered, with an empirical comparison suggesting convergence to the analytical description of the solution occuring as large number of trials are considered.
Introduction
Random walks is a well studied subject matter with applications arising across many fields. Random walks are commonly utilized to model topic specific behaviours, despite the phenomena appearing unique to the particular field. A typical random walk is a special kind of Markov chain, where states are all integers, largest move per transition is one step in either direction, and there is no probability assigned to remaining in the current state.
Simple Random Walk
A random walk is commonly defined as a stochastic sequence, defined by
\[S_n = i + \sum_{k=1}^n X_k \ s.t \ (n \in \Bbb{N}) \]
where \(\{S_n\}\) is a stochastic sequence and \(\{X_k\}\) are \(i.i.d\) random variables. Specifically, a simple random walk is defined as a sequence of \(X_k\) where the random variables take a value of \(1\) or \(-1\) with probability \(p \in [0,1]\) and \(1-p\), respectively. Let \(S = \{S_0,S_1,S_2…\}\) be the partial sum process associated with \(X\). The sequence \(S\) is the simple random walk with parameter \(p\). Further context can be found here
Further, a simple random walk can be considered symmetric if \(Pr(X_k=1) = Pr(X_k=-1)\) when considering the one dimension case.
Random walks with additional properties
Random walks with absorption barriers are commonly studied in applications to the “The Gambler’s ruin” or the “The monkey at the cliff” problems. Consider a discrete random walk confined to a range \([a,b]\) and absorbing barriers at \(a\) and \(b\). In this example, \(a\) and \(b\) are considered absorbing states and characterized by the walk ending when either state is reached.
When considering reflecting barriers, \(a\) is a reflecting barrier means that as soon as the walk reaches \(a\) in the next step the walk returns with probability \(1\).
In the following example, a discrete random walk with a partially reflecting barrier at 0 and absorbing barrier at a user defined \(n\) will be considered. Specifically, if \(x = 0\), the probability we remain in the current state is \(Pr(x=0) = \frac{1}{2} \) and \(Pr(x=1) = \frac{1}{2}\), otherwise \(x=k\) and \(Pr(x=k+1) = \frac{1}{2}\) and \(Pr(x=k-1) = \frac{1}{2}\)
The question we look to answer is what is the expected number \(E_n\) of steps to reach \(n\) from \(i\) considering the prior mentioned probabilities.
A recurrence can be set up to solve for \(E_n\).
Initial values:
\[E_n = 0 \tag{1} \]
\[E_0 = 1 + 0.5E_0 + 0.5E_1 \tag{2} \]
\[E_i = 1 + 0.5E_{i-1} + 0.5E_{i+1} \tag{3} \]
Note that \((3)\) simplifies to \(E_{i+1} = 2E_i - E_{i-1} - 2\) with the associated characteristic equation defined as \(x^2-2x+1\). Solving for the roots results in a double root at \(1\), thus the homogenous solution has the form \(E_i = a + bi\). In order to find the associated particular solution use \[E_i = c + di + ei^2 \tag{4} \]
Plug in \((4)\) into \((3)\) to solve for \(e = -1\), and setting \(c,d=0\), we find that \(E_i = -i^2\). Thus the general solution is defined as
\[E_i = a + bi - i^2 \tag{5} \].
Finally, using \((1)\) and \((5)\), we find that \(0 = a+bn-n^2\) and using \((2)\) and \((5)\) we find that \(b = -1\), which is followed by \(a= n + n^2\). Thus generally, the expected number, \(E_n\), of steps to reach \(n\) from \(i\) is defined by
\[E_i = n + n^2 - i - i^2 \tag{6} \]
A random walk with partially reflecting barrier and absorbing barrier
In the below application, the analytical solution to the random walk with a partial reflecting barrier at \(0\) and absorbing barrier at \(n\) is calculated and compared to an empirical solution resulting from the mean derived from the user defined number of trials. The accepted \(n\) values is restricted to \(n < 30\) and the difference between \(n\) and \(i\) is restricted to \(n-i < 10\) for practical reasons. The application is initialized as follows: \(trials = 100\), \(n = 10\), \(i = 5 \).
The web application was constructed using html, css, javascript, with bulk of application written in Elm. Github repository can be found here. All feedback will be appreciated!