54
$\begingroup$

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.

$\endgroup$

10 Answers 10

25
$\begingroup$

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

$\endgroup$
  • 9
    $\begingroup$ Isn't this obviously a Markov chain? Am I missing something? $\endgroup$ – Wojowu Oct 22 '16 at 10:36
  • 15
    $\begingroup$ @Wojowu --- the "surprising" aspect is that the random walk is biased (with prob. for a step $p$ to the right different from the prob. of a step $q$ to the left), so one would surmise that to find the prob. to move further from the origin, increasing the distance from the origin $|X_n|\mapsto |X_{n+1}|$, knowledge of $|X_n|$ by itself is not enough but one also needs to know the sign of $X_n$. Surprisingly, that surmise is wrong, because if $|X_n|=i$ is given the prob. that $X_n=i$ rather than $-i$ is known (equal to $p^i/(p^i+q^i)$). This is explained in the book cited by Serguei Popov. $\endgroup$ – Carlo Beenakker Oct 22 '16 at 13:52
  • 3
    $\begingroup$ Actually this statement is wrong as stated as it requires an additional assumption that the random walk is started from the point 0. Even with this additional assumption I find it completely misleading as it totally distorts the natural notion of a quotient Markov chain (which $|X_n|$, of course, is not). However, it definitely qualifies as a "curiosity". $\endgroup$ – R W Nov 13 '16 at 1:56
  • 4
    $\begingroup$ @RW: I'm not sure if I understand your comment. It's a natural stochastic process; it's not a quotient Markov chain; hence it's surprising that it is a Markov Chain. This is (as I understood it) what the OP was asking for. $\endgroup$ – Anthony Quas Nov 13 '16 at 6:53
  • $\begingroup$ @Anthony Quas I agree - but still I wouldn't call it a natural "Markov chain" as it has a fixed initial state. $\endgroup$ – R W Nov 13 '16 at 10:06
92
$\begingroup$

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. [source of figure]

$\endgroup$
  • 8
    $\begingroup$ This is an incredible (hi)story! Thanks for sharing! $\endgroup$ – Sam Hopkins Oct 21 '16 at 1:40
  • 8
    $\begingroup$ This is only tangentially related (if that), but it has brought me such satisfaction, I thought I might share it. The following article gives an algorithm for turning a written work into a chess strategy, allowing you to pit two authors against each other. article: cabinetmagazine.org/issues/35/burnett_walter.php $\endgroup$ – David Steinberg Oct 21 '16 at 16:29
28
$\begingroup$

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:

enter image description here

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.)

enter image description here

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.

$\endgroup$
  • 1
    $\begingroup$ Metropolis-Hastings is indeed a beautiful and surprising result. To my mind, the surprising and amazing thing about it is not that it is Markovian, but that it has the specified stationary distribution. Doesn't the fact that it is Markovian follow from the fact that the transition probabilities do not depend on past states? In any case, it is a classic. $\endgroup$ – Adam Smith Oct 22 '16 at 2:16
  • 1
    $\begingroup$ @AdamSmith Using your notation, the Metropolis-Hasting algorithm transforms a given Markov chain Y (the proposal chain) into a Markov chain X (the Metropolized chain) that preserves a given probability distribution $\nu$ by making it $\nu$-reversible. In a finite state space, this viewpoint is refined in the given reference by Billera and Diaconis, where they show that this transformation is a projection onto the set of $\nu$-reversible Markov chains that minimizes the $L^1$ distance. It's not so immediately obvious that this transformation preserves the Markov property ... $\endgroup$ – Nawaf Bou-Rabee Oct 22 '16 at 13:41
  • $\begingroup$ ... In fact, in every step of the method, it almost seems like the update rule involves two steps of the chain as the acceptance probability depends on the current state and the proposed state. However, as I say in my answer, the surprise wears off once one realizes that the proposed state is an auxiliary state that is just used to calculate the actual update. This point becomes a bit more clear in generalizations of the method, e.g., in multiple-try Metropolis or extra chance Metropolis-Hastings, where there are multiple proposed moves. ... $\endgroup$ – Nawaf Bou-Rabee Oct 22 '16 at 14:19
  • 1
    $\begingroup$ @Ian Typically one is given a way to generate samples from a proposal Markov chain, not the acceptance probability. One then has to evaluate the Metropolis-Hastings ratio to determine the acceptance probability function. This function takes as inputs the current state of the chain and the proposed move. This is where it may appear non-Markov because it looks like a two-step update rule. However, as I state above, the proposed move is not the actual updated state. This "non-Markov feel" becomes a bit more clear in the generalizations of the method mentioned above. $\endgroup$ – Nawaf Bou-Rabee Oct 22 '16 at 17:03
  • 1
    $\begingroup$ OK, yes, I phrased it poorly. The point is that the chain itself has the selection probabilities and acceptance probabilities given. The algorithm computes $q_{ij}$ but this is truly just a function of $(i,j)$, even though it is generated only as needed instead of stored in advance. In other words to me the non-Markov feel is just that the algorithm "takes a shortcut": it would not look non-Markov if you precomputed $q_{ij}$ before running the algorithm. This would just be an absolutely awful thing to do in most situations (e.g. for the Ising model with Glauber dynamics). $\endgroup$ – Ian Oct 22 '16 at 17:09
20
$\begingroup$

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

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]n 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.

$\endgroup$
10
$\begingroup$

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"].

$\endgroup$
  • 2
    $\begingroup$ Is this the same as Anthony Quas's slightly earlier answer? $\endgroup$ – LSpice Oct 21 '16 at 17:40
  • 2
    $\begingroup$ basically, yes. Seems we typed it roughly at the same time... $\endgroup$ – Serguei Popov Oct 21 '16 at 19:07
  • 1
    $\begingroup$ This is a nice example. I "accepted" the previous answer (because it was technically earlier). $\endgroup$ – Adam Smith Oct 22 '16 at 2:39
7
$\begingroup$

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).

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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)

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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