Can somebody provide some sort of crash course on random walk and its problems at the level of a beginning undergraduate student in physics? [closed]

Question

I really need some very simple discussions of random walk (probability). Couldn't get anything from class, more so from Reif. Thanks!

Answer 1

Random walk is intimately connected with diffusion, heat equation, Laplacian, harmonic functions, quadratic forms and Gaussian distribution. Here's a sketch of the relationship in the discrete case (continuous case is conceptually similar but requires much more familiarity with probability theory). I'll try to be as consice as possible since there is too much going on.

Consider some connected subset $S$ of a square lattice and suppose there is a random process such that in each time step the particle can jump to a neighboring site (with probability of jumps being uniform for simplicity). This can be considered as an operator (more precisely a probability kernel) $P$ acting on probability measures on $S$ (so called transition operator in the theory of Markov processes). As this is essentialy linear algebra we obviously want to find eigenstates of this operator. So, if $f$ is a stationary distribution w.r.t. this walk, it must be the case that $$\sum_{j \in n(i)} {1 \over 4} f(j) = f(i)$$ where $n(i)$ is the set of neighbors of the site $i$. In other words, such a function must be (discretely) harmonic $\Delta f = 0$ where $\Delta$ is a discretized Laplacian. Since we now have eigenstates we can also consider evolution of the distribution under time in a macroscopic description and this will bring us to the heat equation $\partial_t f = k \Delta f$, $k$ being some coefficient of diffusion or conduction or whatever it is we are trying to model.

Now, there is another nice connection between this random process and certain difference equation Feynman-Kac formula (here shown in the continuous version -- stochastic process and PDE). This formula tells us that a solution to this equation can be written as a sum over all paths of the random walk. Incidentally, the equation we are interested in is given by a quadratic potential between nearest neighbors (this in turn leads to Gaussian measures since the Hamiltonian $H$ is quadratic and the equilibrium measure is given by usual Boltzmann formula $p \sim \exp(-\beta H)$). The condition on being a solution is then that the function is harmonic.

As for the problems and topics, one is interested in things such as recurrence (whether the random walk ever returns to origin with positive probability), exit times, etc. If the RW is recurrent one can study the average time of recurrence. Note that these questions are not that hard on square lattice with uniform probability but become harder on arbitrary graphs with arbitrary probability assignments. We can again study stationary measures, evolution of macroscopic observables, Gaussian distributions, etc. (and essentialy these become tools that can tell us something about the properties of graphs).

On a square lattice in 1D and 2D the random walk is recurrent ("drunkard finds his way home") but in 3D it isn't. This is connected to the fact that Coulomb potential (recall the relationship with harmonics!) in 2D is logorithmic while in 3D it has a power law. Another very close relation is that there are no equilibrium Gibbs states for a massive free field in dimensions less than 3.