When Probability Meets Complex Analysis: The Basic Formula of Random Walks
I've found that many probability problems, especially those involving repeated independent trials, become particularly convenient to handle using generating functions. The "random walk" problem discussed in this post is one such example. It's also vividly called the "drunkard's problem." At its core it's a binomial distribution, but because a limit is taken, a number of new properties and applications emerge. Let's first consider the following problem:
Consider a particle on the real number line. At time $t=0$ it sits at the origin, and every second it either moves one step forward (+1) or one step backward (-1). What is the probability distribution of its position after $n$ seconds?
It's not hard to see that this problem is essentially the same as the binomial distribution. If we picture this particle vividly as a "drunk person," then the walking pattern above resembles a completely intoxicated drunkard walking about. (Of course, a drunkard walks in three-dimensional space, but here, for simplicity, we only describe the one-dimensional case.) This is a sequence of independent repeated trials, and each second's step can be described by the function $\frac{1}{2}(z+z^{-1})$. So the distribution of the motion after $n$ seconds can be described using
$$\frac{1}{2^n}(z+z^{-1})^n$$
where the coefficient of $z^i(i=-n,-n+1,\dots,n-1,n)$ represents the probability that the particle is located at $i$.
Random Walk (Wiener Process)
Next let's consider a more refined random walk problem, one that leads us to the basic result concerning "random walks."
Consider a particle on the real number line. At time $t=0$ it sits at the origin, and every $\Delta t$ seconds it either moves forward $\Delta s$ steps ($+\Delta s$) or moves backward $\Delta s$ steps ($-\Delta s$). Taking $\Delta t,\Delta s\to 0$, what is the probability distribution of its position after $t$ seconds?
Following the same approach as above, we obtain the generating function
$$\frac{1}{2^{t/\Delta t}}\left(z^{\Delta s}+z^{-\Delta s}\right)^{t/\Delta t}$$
Since $\Delta t,\Delta s\to 0$, we replace $e^{-i\omega}$ with $z$, obtaining a generating function described via a Fourier transform:
$$\frac{1}{2^{t/\Delta t}}\left(e^{-i\omega\Delta s }+z^{i\omega\Delta s }\right)^{t/\Delta t}$$
Simplifying using Euler's formula gives
$$\cos^{t/\Delta t}\left(\omega\Delta s \right)\approx\left(1-\frac{\omega^2 \Delta s ^2 }{2}\right)^{t/\Delta t}$$
To arrive at a result with a clear meaning, we take $\Delta s^2 =\alpha \Delta t,\Delta t\to 0$, which gives
$$\exp\left(\frac{-\omega^2 \alpha t }{2}\right)$$
Based on our derivation, this is the Fourier transform of the probability distribution of the random walk problem. That is, if after 1 second the probability that the particle is located at $[x,x+dx]$ is $P(x)dx$, then we have
$$\exp\left(\frac{-\omega^2 \alpha t }{2}\right)=\int_{-\infty}^{+\infty}P(x) e^{-i\omega x}dx$$
Applying the inverse Fourier transform gives
$$P(x)=\frac{1}{\sqrt{2\pi \alpha t}}\exp\left(-\frac{x^2}{2\alpha t }\right)$$
This is the probability distribution of the random walk, and the result shows that the particle's position follows a normal distribution. The above result can be extended to higher dimensions without much difficulty.
A random walk (RW) is a mathematical and statistical model consisting of a series of trajectories, each of which is random. It can be used to represent irregular patterns of variation, like the recorded random process of a person stumbling about after drinking. It was first proposed by Karl Pearson in 1905. Random walks form the mathematical foundation of many physical phenomena. For instance, in manufacturing a product, if the error at each step is roughly the same, then the final error follows a random-walk problem. Similar examples include Brownian motion and diffusion laws, and even, in a certain sense, the Schrödinger equation of quantum mechanics can be regarded as a kind of random walk. However, owing to $\Delta t \propto \Delta s ^2$, it turns out to have an infinite velocity! The meaning behind this still leaves me puzzled, but we'll return to this topic again soon.
Translated automatically with claude-sonnet-5; all equations are reproduced verbatim from the source. Copyright remains with the original author.