Markov walk

Perikinetic motion of small particles (known as colloids ) in a liquid is easily observed under the optical microscope or in a shaft of sunlight through a dusty room - the particles moving in a somewhat jerky and chaotic manner known as the random walk caused by particle bombardment by the fluid molecules reflecting their thermal energy. Einstein propounded the essential physics of perikinetic or Brownian motion (Furth, 1956). Brownian motion is stochastic in the sense that any earlier movements do not affect each successive displacement. This is thus a type of Markov process and the trajectory is an archetypal fractal object of dimension 2 (Mandlebroot, 1982). 

Random walks are often called Markov random walks. A Markov chain is a sequence of random events described in terms of a probability that the event under scmtiny evolved from a defined predecessor. In effect there is no memory of any preceding step in a Markov chain. Hidden Markov processes involve some short-term memory of preceding steps. 

Brown, S., Head-Cordon, T. Cool walking a new Markov chain Monte Carlo sampling method. J. Comput. Chem. 2003, 24, 68-76. 

Exercise. Should the random walk with persistence (1.7.8) be called a Markov process [The answer is given in IV.5.]... 

Exercise. Formulate the random walk problem in 1.4 as a Markov chain. There is no normalized ps owing to the infinite range. Remedy this flaw by considering a random walk on a circular array of N points, such that position JV + 1 is identical with 1. Find ps for this finite Markov chain. Is it true that every solution tends to ps ... 

Random walks on square lattices with two or more dimensions are somewhat more complicated than in one dimension, but not essentially more difficult. One easily finds, for instance, that the mean square distance after r steps is again proportional to r. However, in several dimensions it is also possible to formulate the excluded volume problem, which is the random walk with the additional stipulation that no lattice point can be occupied more than once. This model is used as a simplified description of a polymer each carbon atom can have any position in space, given only the fixed length of the links and the fact that no two carbon atoms can overlap. This problem has been the subject of extensive approximate, numerical, and asymptotic studies. They indicate that the mean square distance between the end points of a polymer of r links is proportional to r6/5 for large r. A fully satisfactory solution of the problem, however, has not been found. The difficulty is that the model is essentially non-Markovian the probability distribution of the position of the next carbon atom depends not only on the previous one or two, but on all previous positions. It can formally be treated as a Markov process by adding an infinity of variables to take the whole history into account, but that does not help in solving the problem. 

Exercise. The transition matrix (5.5) for the random walk with persistence acts in too large a space, because only the states with m = n + 1 have a meaning. Find a simpler reduction of the random walk with persistence to a Markov chain by adding a second variable Y2 which takes only two values. 

A very important application of the Markov dynamics is random walk. In the special case of random walk/(x) = 0 and g(x) = 1, then the diffusion equation for a random walk in one dimension is... 

Levy diffusion is a Markov process corresponding to the conditions established by the ordinary random walk approach with the random walker making jumps at regular time values. To explain why the GME, with the assumption of Eq. (112), yields Levy diffusion, we notice [50] that the waiting time distribution is converted into a transition probability n(x) through... 

Enumeration of Random Walks. Counting simple random walks was reported by Klein et al.216 In parallel to the generation of walks from the powers of the adjacency matrix (see, for example, our Report in ref. 2) that may be viewed as an identification of the distribution for equipoise random walks, Klein et al.216 generated the distribution for simple random walks by powers of a Markov matrix M with elements that are probabilities for associated... 

D. Aldous and J. Fill, Reversible Markov Chains and Random Walks on Graphs. www.stat.berkeley.edu/users/aldous/. 

Markov Chains and Random Walks in Energy Space.601... 

---