The random walk model has a simple form, but it can derive rich results. It is one of the foundations of various diffusion models in physics and is equivalent to Brownian motion in stochastic processes.
The literature reviewed by the author indicates that mathematicians have fully studied the symmetric random walk problem [2], explored the relationship between the random walk problem and partial differential equations [3], and also studied the asymmetric random walk problem [4]. However, the shortcomings of existing results are: 1. In deriving the probability distribution or partial differential equations of the random walk problem, the methods used are not concise and clear enough; 2. More general asymmetric random walk problems have not been studied.
This chapter makes up for this deficiency. First, through the methods of generating functions and Fourier transforms, the partial differential equations satisfied by the asymmetric random walk problem are derived. Furthermore, it is proposed that since random walks are easy to simulate via computer, simulating the solutions of partial differential equations through random walks is an effective numerical approach.
Model Introduction
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 time t=0, it is located at the origin. Every second, it moves one step forward or backward with equal probability (+1 or -1). What is the probability distribution of its position after n seconds?
This is an independent repeated trial, which can be solved using the generating function method. The movement of each 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 a probability of \frac{1}{2}, and \frac{1}{2}z^{-1} represents moving 1 unit in the negative direction with a probability of \frac{1}{2}. Since the movements are independent and repeated, the distribution of movement after n seconds can be described by: \left(\frac{z+z^{-1}}{2}\right)^n = \sum_{k=0}^{n} \frac{1}{2^n} \binom{n}{k} z^{2k-n} \tag{1} The coefficient \frac{1}{2^n} \binom{n}{k} of z^{2k-n} indicates that the probability of the particle being at 2k-n 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 number axis. At time t=0, it is located at the origin. Every \Delta t seconds, it moves \Delta s steps forward or backward with equal probability (+\Delta s or -\Delta s), consider the limit \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: \left(\frac{z^{\Delta s} + z^{-\Delta s}}{2}\right)^{t/\Delta t} \tag{2} Replacing z with e^{-i\omega}, we get the generating function described by the Fourier transform: \left(\frac{e^{i\omega \Delta s} + e^{-i\omega \Delta s}}{2}\right)^{t/\Delta t} \tag{3} Similarly, the coefficient of e^{-i\omega x} represents the probability, but at this time, the coefficient must be obtained through the inverse Fourier transform. Since \Delta t, \Delta s \to 0, using Euler’s formula for further simplification, we get: \left(\frac{e^{i\omega \Delta s} + e^{-i\omega \Delta s}}{2}\right)^{t/\Delta t} = \cos^{t/\Delta t}(\omega \Delta s) \approx \left(1 - \frac{\omega^2 \Delta s^2}{2}\right)^{t/\Delta t} \tag{4} To obtain a result with clear physical meaning, let \Delta s^2 = \alpha \Delta t and \Delta t \to 0, yielding: \exp\left(-\frac{\omega^2 \alpha t}{2}\right) \tag{5} The above equation is the result of the Fourier transform of the probability distribution for the random walk problem. That is to say, if after t seconds, the probability of the particle being at [x, x+dx] is P(x,t)dx, then we have: \exp\left(-\frac{\omega^2 \alpha t}{2}\right) = \int_{-\infty}^{+\infty} P(x,t) \exp(-i\omega x) dx \tag{6} Through the inverse Fourier transform, we obtain: P(x,t) = \frac{1}{\sqrt{2\pi \alpha t}} \exp\left(-\frac{x^2}{2\alpha t}\right) \tag{7}
This is the probability distribution of the random walk, which is consistent with the results in existing literature [2]. The results show that the position of the particle follows a normal distribution. In probability theory, we already know that the normal distribution is widely applied, which reflects the significant importance of the random walk model from another perspective.
Asymmetric Random Walk
In the example of the previous section, each step was an independent repeated trial, meaning the probabilities of moving left and right were both \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 \Delta s to the left with probability \frac{1 - p(x,t)\Delta s/\alpha}{2} and moves \Delta s to the right with probability \frac{1 + p(x,t)\Delta s/\alpha}{2} (The author defines it this way so that p(x,t) has the dimensions of velocity, thereby aligning with the results of stochastic differential equations later on). In this case, the process can no longer be described as independent repeated trials, but the Fourier transform method is still applicable.
For convenience, let the Fourier transform of P(x,t) be: \mathcal{F}_P(t) = \mathcal{F}[P(x,t)] = \int_{-\infty}^{+\infty} P(x,t) e^{-i\omega x} dx \tag{8} If the particle is currently at (x,t), its next step in the random walk can be described (approximately) by the following generating function: \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} The multiplication of generating functions corresponds to the composition of probabilities; therefore: \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} Taking the limit gives: \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} Performing the inverse Fourier transform, we get: \frac{\partial P}{\partial t} = \frac{\alpha}{2} \frac{\partial^2 P}{\partial x^2} - \frac{\partial}{\partial x}(p P) \tag{12} In particular, for a symmetric random walk where p \equiv 0, the above equation becomes the diffusion equation: \frac{\partial P}{\partial t} = \frac{\alpha}{2} \frac{\partial^2 P}{\partial x^2} \tag{13}
Simplified Form
Considering a simplified problem, the first-order partial derivative of P with respect to x can be eliminated through a transformation. From (12), we have: \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}
Let P(x,t) = \phi(x,t) \xi(x,t). Substituting this in, we get: \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} where \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} Setting \eta(x,t) \equiv 0, we obtain: \xi(x,t) = \exp\left(\frac{1}{\alpha} \int p(x,t) dx\right) \tag{17} and we find: 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} At this point, the equation for \phi is: \alpha \frac{\partial \phi}{\partial t} = \frac{\alpha^2}{2} \frac{\partial^2 \phi}{\partial x^2} + V \phi \tag{19} This is a form that has been studied extensively and is relatively easy 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: V(x) = -\frac{1}{2} \left(\alpha \frac{\partial p}{\partial x} + p^2\right) \tag{20} In particular, if p=0, then V=0, leading to the diffusion equation: \frac{\partial \phi}{\partial t} = \frac{\alpha}{2} \frac{\partial^2 \phi}{\partial x^2} \tag{21}
Computer Simulation
Since the random walk corresponds to the partial differential equation (19), and random walks are easy to implement in programming, solving for numerical approximations of the partial differential equation (19) through random walk simulation is very effective in many cases. The book Stochastic Simulation Methods and Applications by Xiao Liuqing and Zhou Shipeng contains such cases in the chapter on random walks.
When reposting, please include the original address: https://kexue.fm/archives/3750
For more detailed reposting matters, please refer to: Scientific Space FAQ