We are solving problem #2 as described in the following screen shot (taken from the class handout)
Short background on the problem: In this project we are asked to verify an analytical result derived in a handout given in the class called ’Continuos approximation to random walk’.
A random walk is formulated, by proposing that \(\pi _{j}^{\left ( n\right ) }\)which is the probability that the position of a particle at \(x=j\Delta x\) and at time \(n\Delta t\) can be expressed as \(f\left ( x,t\right ) \Delta x\), where \(f\left ( x,t\right ) \) represents a density per unit length, which gives a measure of the particle being at that position \(x\) at time \(t.\)
Starting with this and applying a limiting argument lead to a partial differential equation whose solution is the normal distribution function with certain mean and variance. However, the condition for arriving at the PDE was that as we make \(\Delta t\) and \(\Delta x\) small, we needed to keep the ratio \(\frac {\left ( \Delta x\right ) ^{2}}{\Delta t}\)constant.
In this assignment, we simulate a random walk as \(\Delta t\) and \(\Delta x\) are made smaller and smaller subject to this same condition to verify if the distribution of the final position of the random walk converges to the solution of the PDE which is normal distribution and if the converged distribution will have the same variance of \(2Dt\) and same mean of \(\beta t\) as does the solution of the PDE.
The details of the theoretical derivation is shown in the above mentioned handout. A diagram below is made to help illustrate the overall purpose of this assignment. In this assignment, we are working on the flow shown on the right side below.
These are the questions we are trying to answer in this project
The input to the program is \(t,D,\beta \) where \(t\) is the total random walk time and \(D,\beta \,\ \)represents the terms as shown in the diagram above.
A distribution of the final random walk position is generated by running the random walk simulation a number of times (called the sample size). In each such run, we use a specific number of steps. The number of steps is increased, and we generate another distribution. We keep doing this and plot each distribution as the number of steps is increased.
At the end of the simulation, to verify that the distribution in the limit is normal. A quantile-quantile plot is made to compare the generated histogram with the theoretical standard normal distribution to see if the result is close to a straight line or not. Also a plot is made showing the convergence of the variance of the current distribution as number of steps is increased by keeping track of the relative error in the variance. In addition, the RMS error between the standard normal and the current distribution is calculated and plotted as a function of delta(T) as delta(T) is made smaller and smaller. The program is written in Matlab version 2007a and uses the statistics toolbox.
We simulate a random walk, where each step made is either to the left or to the right with probability \(q\) and \(p\) respectively.
Let \(Y_{i}\) be either \(1\) or \(-1\) depending if we make a right or a left step. Hence
and now if we let \(X_{n}=Y_{1}+Y_{2}+\cdots +Y_{n}\) then the final position of the random walk can be written as
where \(\Delta x\) is the step size. The step size is found by solving \(\Delta x=\sqrt {2D\Delta t}\) where \(D\) is the diffusion parameter which is an input, and \(\Delta t\) is the current time step found by dividing the total simulation fixed time \(t\), which is an input, by the current number of steps \(n\).
This program handles a general value for \(\beta \) other than zero. To be able to accomplish this, we need to determine the correct starting step size \(n\) to avoid the problem with coming up with a value for the probability \(p\) being larger than \(1\). So, this was done in the initialization stage using this formula
And the simulation was started from the above \(n\) and not from \(1\).
To answer the first question of this simulation, which is to determine if the final position distribution converges to normal distribution with mean \(\beta t\) and variance \(2Dt\), a quantile plot was used. In this plot, the quantile for the standard normal distribution was plotted against the quantile of the distribution of the final position.
The \(x-axis\) of the quantile-quantile plot was found as follows
Where \(F^{-1}\) is the inverse of the CDF for the standard normal distribution (the matlab function norminv() was used for this). While the \(y-axis\) is the quantile of the actual data (the sample data of the final distribution of the random walk position). This was found by sorting the data from small to large and then using the resulting sorted vector as the \(y\) values. Notice that the distribution was already standardized using
Where \(\mu =\beta t\) and \(\sigma =\sqrt {2Dt}\),