"Surprising" examples of Markov chains

Question

I am looking for examples of Markov Chains which are surprising in the following sense: a stochastic process $X_1,X_2,...$ which is "natural" but for which the Markov property is not obvious at first glance. For example, it could be that the natural definition of the process is in terms of some process $Y_1,Y_2,...$ which is Markovian and where $X_i=f(Y_i)$ for some function $f$.

Let me give you an example which is slightly surprising, but not surprising enough for my taste. Suppose we have $n$ bins that are initially empty, and at each time step $t$ we throw a ball into one of the bins selected uniformly at random (and independently of previous time steps). Let $X_t$ be the number of empty bins at time $t$. Then $X_1,X_2,...$ form a Markov chain.

Are there good, more surprising examples? I apologize if this question is vague.

Answer 1

I believe that if $(X_n)$ is a biased simple random walk on $[-N,N]$, then $|X_n|$ is a Markov chain.

Answer 2

I could go back to Markov himself, who in 1913 applied the concept of a Markov chain to sequences of vowels and consonants in Alexander Pushkin's poem Eugene Onegin. In good approximation, the probability of the appearance of a vowel was found to depend only on the letter immediately preceding it, with $p_{\text{vowel after consonant}}=0.663$ and $p_{\text{vowel after vowel}}=0.128$. These numbers turned out to be author-specific, suggesting a method to identify authors of unknown texts. (Here is a Mathematica implementation.) Brian Hayes wrote a fun article reviewing how "Probability and poetry were unlikely partners in the creation of a computational tool"

The first 100 cyrillic letters of 20,000 total letters compiled by Markov from the first one and a half chapters of Pushkin's poem. The numbers surrounding the block of letters were used to demonstrate that the appearance of vowels is a Markov chain.

Answer 3

Consider the Metropolis-Hastings algorithm which is an MCMC method, i.e., a general purpose Monte Carlo method for producing samples from a given probability distribution. The method works by generating a Markov chain from a given proposal Markov chain as follows. A proposal move is computed according to the proposal Markov chain, and then accepted with a probability that ensures the Metropolized chain (the one produced by the Metropolis-Hastings algorithm) preserves the given probability distribution.

This Metropolized chain is a "surprising example of a Markov chain" because the acceptance probability at every step of the chain depends on both the current state of the chain and the proposed state. However, the surprise wears off a bit once one realizes that the next state of the Metropolized chain does not necessarily coincide with the proposed move, and that the next state of the chain could in fact be the current state of the chain if the proposed move is rejected.

For an expository intro to Metropolized chains, check out The MCMC Revolution by P. Diaconis, and see also, A Geometric Interpretation of the Metropolis-Hasting Algorithm by L. J. Billera and P. Diaconis. Here is a quote from the latter.

The [Metropolis-Hastings] algorithm is widely used for simulations in physics, chemistry, biology and statistics. It appears as the first entry of a recent list of great algorithms of 20th-century scientific computing. Yet for many people (including the present authors) the Metropolis-Hastings algorithm seems like a magic trick. It is hard to see where it comes from or why it works.

ADD

Other "surprising" (and related) examples are given by MALA, Hamiltonian Monte-Carlo, Extra Chances Hamiltonian Monte-Carlo, Riemann Manifold Langevin and Hamiltonian Monte Carlo, Multiple-try Metropolis and Parallel Tempering, which are all MCMC methods. Like the above example, these chains are unexpectedly Markovian because their acceptance probabilities (the probabilities that determine the actual update of the chain) are functions of the current state of the chain and the proposed move(s).

Let me elaborate a bit on the parallel tempering method and what makes it a surprising example. The aim of the method is to sample from a probability distribution with a multi-modal energy landscape, which one can regard as a high-dimensional version of:

The difficulty with sampling from a probability distribution with an energy landscape like this one is not only the fact that there are many modes, but that the energy barriers between these modes may be too high for a simple MCMC method to overcome. Simply put, even computing the mean and variance of this distribution might be impractical to do using simple MCMC methods.

The basic idea in parallel tempering is to introduce a fictitious temperature parameter that flattens the desired probability distribution, and hence, makes it easier to sample from using a simple MCMC method. Then one constructs a sequence of distributions from a sufficiently flat distribution (at high temperature) to the desired probability distribution (at lower temperature). Then one runs a sequence of chains to sample from this sequence of distributions.

Each of these chains evolves at its own temperature, but occasionally one swaps the states between these chains so that the chain running at the lowest temperature explores its landscape more efficiently. (Unfortunately the samples generated at the higher temperatures cannot be directly used to sample from the desired distribution at the lowest temperature in the sequence.)

As a concrete example, consider applying parallel tempering to a 15 degree of freedom pentane molecule. The goal here is to sample from the equilibrium distribution of this molecule in the plane defined by its two dihedral angles (these are certain internal degrees of freedom of the molecule). This distribution has nine modes (corresponding to different molecular conformations). Here is a picture showing the sequence of probability distributions where the dots represent the states of the MCMC chains at four different temperature levels. (The parameter $\beta$ is the inverse temperature.)

It's easy to eyeball the plane at the highest temperature (lowest $\beta$), since the dots are more spread out in that plane. Back to the point, not all swaps are accepted, and the probability of swapping between chains at different temperatures in parallel tempering depends on both the current and swapped states of the chain. Moreover, as in plain vanilla Metropolis-Hastings, the probability of accepting a proposed move for the chains at different temperatures also depends on both the current and proposed state of the chain. This dependence is essential for the chain to preserve the correct probability distribution in the enlarged space. So, at first glance, it may seem like the parallel tempering chain is not Markov. However, as in Metropolis-Hastings, one can explicitly show that the transition probability of the parallel tempering chain only depends on its current state.

Answer 4

One example I enjoy is that if you add a list of numbers, the carries form a markov chain

• Carries, Shuffling and An Amazing Matrix
• Carries, shuffling, and symmetric functions

If $n$ integers in base $b$ with digits chosen uniformly random, the carries form a markov chain

1 12021 01111 11111 11111 11011 10111 01111 11111 21011 1112.

  43935 23749 58561 74916 62215 47448 33196 51990 19807 27075
  48537 53642 77448 32760 14421 72142 82116 37225 43300 51498
  33618 41327 41561 16257 43616 55134 82714 63369 87142 45607
-------------------------------------------------------------
1 26091 18719 77571 23934 20253 74725 98027 52585 50250 24180

---

Another important example is random walk on the cube [0,1]ⁿ and it's projection is the Ehrenfest Urn

• start at $\vec{v} = (0,\dots, 0) \in \{ 0,1\}^n$ and at each time step change $0 \leftrightarrow 1$ for one of the coordinates.
• If we take the inner product $\vec{v} \cdot (1,\dots, 1) = v_1 + \dots v_n \in \mathbb{N}$ this is also a Markov chain.
• We could have spots $0, 1, \dots, n$ and if $X_t = k$ we can jump to the left with probability $\frac{k}{n}$ and to the right with probability $\frac{n-k}{n}$ and this is a Markov chain.

I had to verify my logic was correct it's in Markov Chains and Mixing Times.

Answer 5

Let $S_n$ be the one-dimensional nearest neighbor random walk with $ 1-q=p=P[S_{n+1}=x+1\mid S_n=x]=1-P[S_{n+1}=x-1\mid S_n=x]$, where $p\neq q$. Then, there is a (rather surprising) fact that $Y_n=|S_n|$ is still a Markov chain. See e.g. Proposition 4.1.1 of [S.Ross, "Stochastic Processes"].

Answer 6

An (admittedly conjectural) instance that I found extremely surprising when I first saw it was the appearance of Markov chains when studying the factorization of iterates of quadratic polynomials over finite fields, discussed in [1, 2].

[1] Boston, Jones, "Settled polynomials over finite fields", Proc. Amer. Math. Soc. 140 (2012), 1849–1863.

[2] Boston, Goksel, Xia, "A refined conjecture for factoring iterates of quadratic polynomials over finite fields", Experimental Mathematics , Vol 24 (3), 304–311, 2015.

Answer 7

Pitman 2M-X theorem (which has a nice and very simple discrete version) stimulated a lot of research and the discovery of further intertwined Markov semigroups (it would be interesting to trace the nice examples within the 61 references citing this paper on MathSciNet).

The theorem says that 2 times the supremum of a random walk minus that random walk is again a Markov chain (the random walk conditioned to be non negative).

Answer 8

Take $N$ independent walkers on the one-dimensional lattice $\mathbb{Z}$ (i.e., independent random walks, biased or not). Condition that these walkers do not collide till the end of time. Then the conditioned process is a Markov chain! (e.g. http://projecteuclid.org/euclid.ejp/1463434878)

Answer 9

The Dyson Brownian motion. Take a random matrix whose entries perform independent standard Brownian motions, subject to the condition that the matrix stays Hermitian, so that entries above diagonal perform Brownian motions in the complex plane, the diagonal entries perform a BM on the real line, and the entries below the diagonal are complex conjugates of the ones above that diagonal.

Then, the eigenvalue process $(\lambda_1(t),\dots,\lambda_n(t))$ of this random matrix is Markov. This is closely related to the example mentioned in Leonid Petrov's answer, but I think the reasons for this "surprising Markov property" are rather different in the two cases.

Answer 10

A more humorous example of a "naturally occurring" Markov chain (generated diagram).