Take the 2-minute tour ×
Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. It's 100% free, no registration required.

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

share|improve this question
After having provided an answer (necessarily very general and very sketchy one), is there anything specific you'd like to know? The field is huge with connections to all areas of mathematics and physics (e.g. quantum mechanics and quantum field theory can, via Wick rotation and Feynman path integral, be considered a theory of "complex random walk") and elsewhere (finance, biology, etc.). –  Marek Jul 25 '11 at 15:23
I think this question is too broad to be appropriate here - as the FAQ says, "You should only ask practical, answerable questions...," and also that we want direct questions, not discussions. A question on this site isn't meant to be a crash course in a whole subject, it should be more specific. –  David Z Jul 25 '11 at 21:12
add comment

closed as not a real question by David Z Jul 25 '11 at 21:07

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

1 Answer

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.

share|improve this answer
Hm and if anyone thinks there is too much going on, I completely forgot to mention Fourier analysis! After all, Fourier invented this tool precisely to study the heat equation. This works since the square lattice is also a group $(\mathbb Z^2, +)$ (in continuous case we have the Lie group $(\mathbb R^2, +)$). More generally, people study random walks on arbitrary groups since here they can use Pontryagin duality and character theory (in the abelian case) or representation theory as a generalization of Fourier analysis. –  Marek Jul 25 '11 at 14:33
Is the discretized Laplacian you mention a version of the graph Laplacian? In particular the graph Laplacian associated with random walks. A reference to the particular graph Laplacian is found on pg. 5 of this tutorial on spectral clustering kyb.mpg.de/fileadmin/user_upload/files/publications/attachments/… @Marek –  sunspots Apr 3 at 3:04
@sunspots: yes, it's a graph Laplacian for the special case of the graph a square lattice. In this case every vertex has four neighbors, so the matrix $W$ in $\Delta = D - W$ is $1/4$ precisely for the pairs of neighboring vertices and $0$ otherwise. That's precisely what's written in the averaging equation for harmonics above. –  Marek Apr 3 at 10:23
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.