By 苏剑林 | May 30, 2016
The random walk model is simple in form, but through it, rich results can be derived. It is one of the foundations for various diffusion models in physics and is equivalent to Brownian motion in stochastic processes.
Literature reviewed by the author indicates that mathematicians have conducted thorough research on the symmetric random walk problem [2], explored the relationship between random walks and partial differential equations [3], and also studied asymmetric random walks [4]. However, the shortcomings of existing results include: 1. The methods used to derive the probability distributions or partial differential equations for random walks are not concise or clear enough; 2. More general asymmetric random walk problems have not been researched.
This chapter compensates for these deficiencies. First, through methods of generating functions and Fourier transforms, the partial differential equations satisfied by asymmetric random walks are derived. Furthermore, it is proposed that since random walks are easy to simulate on a computer, simulating the solutions of partial differential equations via random walks is an effective numerical approach.
This section introduces the random walk through a grid-walking problem that essentially belongs to a binomial distribution.
Consider a particle on the real number axis. At $t=0$, it is located at the origin. Every second, it moves forward or backward by one grid step ($+1$ or $-1$) with equal probability. What is the probability distribution of its position after $n$ seconds?
This is an independent repeated experiment which can be solved using the generating function method. The movement per second can be described by the function $\frac{1}{2}z + \frac{1}{2}z^{-1}$, where the $\frac{1}{2}z$ term represents moving 1 unit in the positive direction with probability $\frac{1}{2}$, and $\frac{1}{2}z^{-1}$ represents moving 1 unit in the negative direction with probability $\frac{1}{2}$. Since the movements are independent and repeated, the distribution after $n$ seconds can be described by: \begin{equation} \left(\frac{z+z^{-1}}{2}\right)^n=\sum_{k=0}^{n}\frac{1}{2^n}\binom{n}{k}z^{2k-n}\tag{1} \end{equation} The coefficient $\frac{1}{2^n}\binom{n}{k}$ of $z^{n-2k}$ indicates that the probability of the particle being at $n-2k$ is $\frac{1}{2^n}\binom{n}{k}$. Clearly, this is a binomial distribution problem.
The random walk model is a refinement of the above problem:
Consider a particle on the real axis. At $t=0$, it is at the origin. Every $\Delta t$ seconds, it moves forward or backward by $\Delta s$ grids ($+\Delta s$ or $-\Delta s$) with equal probability. Considering $\Delta t, \Delta s \to 0$, what is the probability distribution of its position after $t$ seconds?
Similarly, using the generating function technique, we obtain \begin{equation} \left(\frac{z^{\Delta s}+z^{-\Delta s}}{2}\right)^{t/\Delta t},\tag{2} \end{equation} Replacing $z$ with $e^{-i\omega}$, we get the generating function described by the Fourier transform: \begin{equation} \left(\frac{e^{i\omega\Delta s}+e^{-i\omega\Delta s }}{2}\right)^{t/\Delta t},\tag{3} \end{equation} Similarly, the coefficient of $e^{-i\omega x}$ represents the probability, but now the coefficient must be obtained through the inverse Fourier transform. As $\Delta t, \Delta s \to 0$, using Euler's formula for further simplification, we get \begin{equation} \left(\frac{e^{i\omega\Delta s }+e^{-i\omega\Delta s }}{2}\right)^{t/\Delta t}= \cos^{t/\Delta t}\left(\omega\Delta s \right)\approx\left(1-\frac{\omega^2 \Delta s ^2 }{2}\right)^{t/\Delta t},\tag{4} \end{equation} To obtain a result with clear meaning, we set $\Delta s^2 = \alpha \Delta t$ and let $\Delta t \to 0$, reaching \begin{equation} \exp\left(\frac{-\omega^2 \alpha t }{2}\right),\tag{5} \end{equation} The above equation is the result of the Fourier transform of the probability distribution for the random walk problem. That is, if after $t$ seconds, the probability of the particle being at $[x, x+dx]$ is $P(x,t)dx$, then we have \begin{equation} \exp\left(\frac{-\omega^2 \alpha t }{2}\right)=\int_{-\infty}^{+\infty} P (x,t) \exp\left(-i\omega x\right)dx,\tag{6} \end{equation} Through the inverse Fourier transform, we obtain \begin{equation} P (x,t)=\frac{1}{\sqrt{2\pi \alpha t}}\exp\left(-\frac{x^2}{2\alpha t }\right).\tag{7} \end{equation}
This is the probability distribution for a random walk, which is consistent with the results in existing literature [2]. The result shows that the particle's position follows a normal distribution. In probability theory, we already know that the normal distribution is widely applied, which indirectly reflects the significant importance of the random walk model.
In the example of the previous section, every step was an independent repeated experiment, i.e., the probability of moving left or right was $\frac{1}{2}$, so we could obtain the probability distribution through the limit method. Now consider that when the particle is at $(x,t)$, it moves left by $\Delta s$ with probability $\frac{1-p(x,t)\Delta s/\alpha}{2}$ and moves right by $\Delta s$ with probability $\frac{1+p(x,t)\Delta s/\alpha}{2}$ (Why not integrate $/\alpha$ directly into the definition of $p(x,t)$? This actually involves dimensional considerations; the author defines it this way so that $p(x,t)$ has the dimensions of velocity, thus aligning with the results of stochastic differential equations later). At this point, the process can no longer be described as an independent repeated experiment, but the Fourier transform method still applies.
For convenience, denote the Fourier transform of $P(x,t)$ as \begin{equation} \mathcal{F}_{ P } (t)=\mathcal{F}[ P (x,t)]=\int_{-\infty}^{+\infty} P (x,t)e^{-i\omega x}dx .\tag{8} \end{equation} If the particle is currently at $(x,t)$, then its next step of random walk can be described (approximately) by the following generating function \begin{equation} \begin{aligned}&\left(\frac{1-p(x,t)\Delta s/alpha}{2}\right)e^{i\omega \Delta s}+\left(\frac{1+p(x,t)\Delta s/\alpha}{2}\right)e^{-i\omega \Delta s}\\ =&\cos\omega \Delta s-i p(x,t)\Delta s \sin\omega\Delta s/\alpha\\ \approx &1-\frac{\omega^2 \Delta s^2}{2}-i \omega p(x,t)\Delta s^2/\alpha\\ =&1-\frac{\omega^2 \alpha \Delta t}{2}-i \omega p(x,t)\Delta t\end{aligned} .\tag{9} \end{equation} The multiplication of generating functions corresponds to the synthesis of probabilities; therefore \begin{equation} \mathcal{F}_{ P } (t+\Delta t)\approx\int_{-\infty}^{+\infty}\left[1-\frac{\omega^2 \alpha \Delta t}{2}-i \omega p(x,t)\Delta t\right] P (x,t)e^{-i\omega x}dx ,\tag{10} \end{equation} Taking the limit yields \begin{equation} \frac{\partial \mathcal{F}_{ P }(t)}{\partial t}= -\frac{\omega^2 \alpha }{2}\mathcal{F}_{ P }(t)-i \omega \mathcal{F}[p(x,t) P (x,t)] ,\tag{11} \end{equation} Performing the inverse Fourier transform, we get \begin{equation} \frac{\partial P }{\partial t}= \frac{\alpha }{2}\frac{\partial^2 P }{\partial x^2}-\frac{\partial}{\partial x}(p P ) .\tag{12} \end{equation} Specifically, for a symmetric random walk where $p \equiv 0$, the above equation becomes the diffusion equation \begin{equation} \frac{\partial P }{\partial t}= \frac{\alpha }{2}\frac{\partial^2 P }{\partial x^2}. .\tag{13} \end{equation}
Considering a simplified problem, transformations can be used to eliminate the first-order partial derivative term of $P$ with respect to $x$. From $(12)$ we get \begin{equation} \alpha\frac{\partial P }{\partial t}= \frac{\alpha^2}{2}\frac{\partial^2 P }{\partial x^2}-\alpha \frac{\partial p}{\partial x} P -\alpha p\frac{\partial P }{\partial x} ,\tag{14} \end{equation} Let $P(x,t) = \phi(x,t) \xi(x,t)$. Substituting this in, we yield \begin{equation} \begin{aligned} \alpha\frac{\partial \phi}{\partial t}\xi=& \frac{\alpha^2}{2}\left(\frac{\partial^2 \phi}{\partial x^2}\xi+2\frac{\partial \phi}{\partial x}\frac{\partial \xi}{\partial x}+\phi\frac{\partial^2 \xi}{\partial x^2}\right)\\ &-\alpha \frac{\partial p}{\partial x}\phi\xi-\alpha p\left(\frac{\partial \phi}{\partial x}\xi+\frac{\partial \xi}{\partial x}\phi\right)-\alpha\phi\frac{\partial \xi}{\partial t}\\ =&\left(\frac{\alpha^2}{2}\frac{\partial^2 \phi}{\partial x^2}+\eta(x,t)\frac{\partial \phi}{\partial x}+V(x,t)\phi\right)\xi\end{aligned} ,\tag{15} \end{equation} where \begin{equation} \begin{aligned}&\eta(x,t)=\alpha^2\frac{1}{\xi}\frac{\partial \xi}{\partial x}-\alpha p,\\ &V(x,t)=-\frac{1}{\xi}\left(\alpha\frac{\partial p}{\partial x}\xi+\alpha p\frac{\partial \xi}{\partial x}-\frac{1}{2}\alpha^2\frac{\partial^2 \xi}{\partial x^2}+\alpha\frac{\partial \xi}{\partial t}\right)\end{aligned},\tag{16} \end{equation} Letting $\eta(x) \equiv 0$, we obtain \begin{equation} \xi(x,t)=\exp\left(\frac{1}{\alpha}\int p(x,t) dx\right),\tag{17} \end{equation} and we find \begin{equation} V(x,t)=-\frac{1}{2}\left(\alpha\frac{\partial p}{\partial x}+p^2\right)-\int \frac{\partial p}{\partial t} dx ,\tag{18} \end{equation} At this point, the equation for $\phi$ is \begin{equation} \alpha\frac{\partial \phi}{\partial t}=\frac{\alpha^2}{2}\frac{\partial^2 \phi}{\partial x^2}+ V\phi .\tag{19} \end{equation} This is a form that is widely studied and relatively easier to research, corresponding to the Schrödinger equation in quantum mechanics. Of course, $\phi(x,t)$ can also be thought of as a relative probability distribution, but it must be clear that $P$ is the true probability distribution.
If $p$ is independent of $t$, then \begin{equation} V(x)=-\frac{1}{2}\left(\alpha\frac{\partial p}{\partial x}+p^2\right),\tag{20} \end{equation} In particular, if $p=0$, it leads to $V=0$, thus obtaining the diffusion equation \begin{equation} \frac{\partial \phi}{\partial t}=\frac{\alpha }{2}\frac{\partial^2 \phi}{\partial x^2}.\tag{21} \end{equation}
Since the random walk corresponds to the partial differential equation $(19)$, and the random walk is easy to implement in programming, using the method of simulating random walks to solve the numerical approximation of the partial differential equation $(19)$ is very effective in many cases. The book "Stochastic Simulation Methods and Applications" by Xiao Liuqing and Zhou Shipeng has such cases in the chapter on random walks.