Path Integrals Series: 2. The Random Walk Model

路径积分系列：2.随机游走模型 苏剑林 · 2016-05-30 · Mathematics path integral random walk

The random walk model is simple in form, but it can be used to derive a wealth of results. It is one of the foundations of various diffusion models in physics, and it is also equivalent to Brownian motion in stochastic process theory.

The literature I have consulted shows that mathematicians have already thoroughly studied the symmetric random walk problem [2], and have also explored the relationship between random walk problems and partial differential equations [3], as well as studied the asymmetric random walk problem [4]. However, the existing results have the following shortcomings: 1) the methods used to derive the probability distribution or the partial differential equation for the random walk problem are not sufficiently concise and clear; 2) the more general asymmetric random walk problem has not been studied.

This chapter aims to remedy this shortcoming. First, using the method of generating functions and the Fourier transform, we derive the partial differential equation satisfied by the asymmetric random walk problem. We also point out that, since random walks are easy to simulate on a computer, using random walks to simulate solutions of partial differential equations is an effective numerical approach.

Introducing the Model

This section introduces the random walk via a "walking on a grid" problem that is essentially a binomial distribution.

Consider a particle on the real number line. At time $t=0$ it is located at the origin. Each second, it moves one step forward or backward ($+1$ or $-1$) with equal probability. 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. Each second's movement can be described by the function $\frac{1}{2}z+\frac{1}{2}z^{-1}$, where the term $\frac{1}{2}z$ represents moving 1 in the positive direction with probability $\frac{1}{2}$, and $\frac{1}{2}z^{-1}$ represents moving 1 in the negative direction with probability $\frac{1}{2}$. Since the motion is independently repeated, the distribution of motion 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}$$

where the coefficient $\frac{1}{2^n}\binom{n}{k}$ of $z^{n-2k}$ represents the probability that the particle is located at $n-2k$, namely $\frac{1}{2^n}\binom{n}{k}$. As we can see, this is a binomial distribution problem.

The random walk model is a refinement of the above problem:

Consider a particle on the real number line. At time $t=0$ it is located at the origin. Every $\Delta t$ seconds, it moves $\Delta s$ steps forward or backward ($+\Delta s$ or $-\Delta s$) with equal probability. Considering 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}$$

Substituting $e^{-i\omega}$ for $z$, we obtain the generating function described via the Fourier transform:

$$\left(\frac{e^{i\omega\Delta s}+e^{-i\omega\Delta s }}{2}\right)^{t/\Delta t},\tag{3}$$

Likewise, the coefficient of $e^{-i\omega x}$ represents the probability, but this time the coefficient must be obtained via the inverse Fourier transform. Since $\Delta t,\Delta s\to 0$, using Euler's formula to simplify further, we get

$$\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}$$

To obtain a result with clear physical meaning, we take the limit $\Delta s^2 =\alpha \Delta t,\Delta t\to 0$, giving

$$\exp\left(\frac{-\omega^2 \alpha t }{2}\right),\tag{5}$$

The above 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 that the particle is located 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\left(-i\omega x\right)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 matches the result found in the 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 has extremely broad applications, and this in turn reflects the significance of the random walk model.

Asymmetric Random Walk

In the example in the previous section, each step is an independent repeated trial, i.e., the probability of moving left or right is both $\frac{1}{2}$, so we could obtain the probability distribution by taking a limit. Now consider a particle at position $(x,t)$ that 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 directly incorporate $/\alpha$ into the definition of $p(x,t)$? This actually involves a question of dimensional analysis — I define it this way so that $p(x,t)$ has the dimension of velocity, which will be consistent with the results of the stochastic differential equations discussed later). At this point, the process described above can no longer be described as an independent repeated trial, but the Fourier transform method still applies.

For convenience, let us denote the Fourier transform of $ P (x,t)$ as

$$ \mathcal{F}_{ P } (t)=\mathcal{F}[ P (x,t)]=\int_{-\infty}^{+\infty} P (x,t)e^{-i\omega x}dx .\tag{8}$$

Suppose the particle is currently located at $(x,t)$. Then its next random-walk step can be (approximately) described via 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}$$

Multiplication of generating functions corresponds to the composition of probabilities, so

$$\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 obtain

$$\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 the symmetric random walk we have $p\equiv 0$, and the above equation becomes the diffusion equation

$$\frac{\partial P }{\partial t}= \frac{\alpha }{2}\frac{\partial^2 P }{\partial x^2}. .\tag{13}$$

A Simplified Form

Let us consider a simplified problem, where we can eliminate the first-order partial derivative term of $ P $ with respect to $x$ via a transformation. From $(12)$ we get

$$\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)$, and 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}$$

Letting $\eta(x)\equiv 0$, we obtain

$$\xi(x,t)=\exp\left(\frac{1}{\alpha}\int p(x,t) dx\right),\tag{17}$$

and further 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$ becomes

$$\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 study, corresponding to the Schrödinger equation in quantum mechanics. Of course, we could also think of $\phi(x,t)$ as a relative probability distribution, but it must be made clear that $ P $ is the actual probability distribution.

If $p$ does not depend on $t$, then

$$V(x)=-\frac{1}{2}\left(\alpha\frac{\partial p}{\partial x}+p^2\right),\tag{20}$$

In particular, if $p=0$, this leads to $V=0$, giving us 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 code, we can solve for a numerical approximation of the partial differential equation $(19)$ by simulating the random walk — and in many cases this proves to be highly effective. The chapter on random walks in Xiao Liuqing and Zhou Shipeng's book Stochastic Simulation Methods and Applications contains just such an example.