The author has found that many probability problems, especially those involving independent repeated trials, become particularly convenient when approached using the method of generating functions. The “Random Walk” problem discussed in this article is one such example. It is also vividly known as the “Drunkard’s Walk” problem. In essence, it is a binomial distribution, but due to the limit taken, many new properties and applications emerge. Let us first consider the following problem:
Consider a particle on the real axis. At time t=0, it is located at the origin. Every second, it moves either one step forward (+1) or one step backward (-1). What is the probability distribution of its position after n seconds?
It is not difficult to see that this problem is identical to a binomial distribution. If we metaphorically compare this particle to a “drunk person,” then the movement described above is similar to the walking problem of a completely intoxicated drunkard. (Of course, a drunkard walks in three-dimensional space; for simplicity, we only describe the one-dimensional case here.) This is an independent repeated trial. The movement of each second can be described by the function \frac{1}{2}(z+z^{-1}). Thus, the distribution of motion after n seconds can be described by: \frac{1}{2^n}(z+z^{-1})^n The coefficient of z^i (where i = -n, -n+1, \dots, n-1, n) represents the probability that the particle is located at position i.
Random Walk (Wiener Process)
Next, we consider a more detailed random walk problem, which leads to our fundamental results regarding “Random Walks.”
Consider a particle on the real axis. At time t=0, it is located at the origin. Every \Delta t seconds, it moves either \Delta s steps forward (+\Delta s) or \Delta s steps backward (-\Delta s). Consider the limit as \Delta t, \Delta s \to 0. What is the probability distribution of its position after t seconds?
Following a similar approach to the one 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 substitute z with e^{-i\omega} to obtain the generating function described by the Fourier transform: \frac{1}{2^{t/\Delta t}}\left(e^{-i\omega\Delta s }+e^{i\omega\Delta s }\right)^{t/\Delta t} Simplifying using Euler’s formula, we get: \cos^{t/\Delta t}\left(\omega\Delta s \right) \approx \left(1-\frac{\omega^2 \Delta s^2}{2}\right)^{t/\Delta t} To obtain a result with clear physical meaning, we set \Delta s^2 = \alpha \Delta t and let \Delta t \to 0, yielding: \exp\left(\frac{-\omega^2 \alpha t}{2}\right) According to our derivation process, this is the Fourier transform of the probability distribution for the random walk problem. That is to say, if the probability of the particle being located in the interval [x, x+dx] after t seconds 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
By applying the inverse Fourier transform, we obtain: P(x) = \frac{1}{\sqrt{2\pi \alpha t}} \exp\left(-\frac{x^2}{2\alpha t}\right) This is the probability distribution of a random walk. The result indicates that the position of the particle follows a normal distribution. The above results can be easily generalized to higher dimensions.
Random Walk (RW) is a mathematical statistical model composed of a series of trajectories, where each step is random. It can be used to represent irregular forms of change, such as the record of a random process formed by a person walking aimlessly after drinking. It was first proposed by Karl Pearson in 1905. Random walk is the mathematical foundation for many physical phenomena. For example, in the production of a product, if the error of each step is approximately the same, the final error is a random walk problem. Similar phenomena include Brownian motion, diffusion laws, etc. Even the Schrödinger equation in quantum mechanics is, in a sense, a type of random walk. However, since \Delta t \propto \Delta s^2, it surprisingly implies an infinite velocity! The underlying meaning of this still leaves the author in confusion, but we will return to this topic again soon.
When reprinting, please include the original address: https://kexue.fm/archives/2573
For more detailed information regarding reprinting, please refer to: Scientific Space FAQ