Skip to main content
109 votes

"Surprising" examples of Markov chains

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 ...
Carlo Beenakker's user avatar
30 votes
Accepted

"Surprising" examples of Markov chains

I believe that if $(X_n)$ is a biased simple random walk on $[-N,N]$, then $|X_n|$ is a Markov chain.
Anthony Quas's user avatar
  • 22.6k
27 votes

"Surprising" examples of Markov chains

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 ...
Nawaf Bou-Rabee's user avatar
22 votes

"Surprising" examples of Markov chains

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 ...
john mangual's user avatar
  • 22.7k
16 votes
Accepted

Direct proof of unique invariant distribution for ergodic, positive-recurrent Markov chain

Yes, uniqueness can be proved without appealing to probabilistic arguments. Generally speaking, one can study properties of Markov chains by arguments from functional analysis and operator theory, ...
Jochen Glueck's user avatar
13 votes

One observation of special type of square matrix exponentiation

The answer is quite simple. First observe that $A$ is triangular, hence the spectrum is on the diagonal. From your assumptions, $1$ is a simple eigenvalue and the other eigenvalues belong to $[0,1)$. ...
Denis Serre's user avatar
  • 51.8k
12 votes
Accepted

what is the number of paths returning to 0 on the hexagonal lattice

This is answered by Ian Agol here, with the reference "All Roads Lead to Rome-Even in the Honeycomb World", Brani Vidakovic, Amer. Statist. 48 (1994) no. 3, 234-236. An exact formula is $$ p(n) = \...
Harry Richman's user avatar
11 votes
Accepted

An interesting Markov chain with uniform marginals

Since I was requested to elaborate, here goes. First, let's look at the automorphism of the unit circle induced by this mapping (written in the least revealing way). With $z=e^{it}$, as usual, we have ...
fedja's user avatar
  • 60.6k
11 votes

Reference Request: Theoretical Mixing Times Research in Machine Learning / Artificial Intelligence (AI)

The question as asked is rather broad, because there are several works in ML/AI dedicated to mixing time analysis, as well as to detecting if mixing has happened. I would not draw too sharp a boundary ...
Suvrit's user avatar
  • 28.5k
10 votes
Accepted

Random walk to stay in an interval forever

Yes. Indeed, if $s = \sum_{i \geq 1} t_i^2 <1$, then $$ \mathbb{P}[ \ \ \forall n, \sum_{i=1}^n X_i \in [-1,1] \ \ ] \geq 1-s > 0. $$ To see this, note that $M_n = |\sum_{i=1}^n X_i|$ is a ...
js21's user avatar
  • 7,209
10 votes

"Surprising" examples of Markov chains

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=|...
Serguei Popov's user avatar
9 votes

All two-point correlations equal to $0$, three-point correlation not $0$?

I think you could make such an example by choosing any normal sequence $S$ on the alphabet $\{0,1,2,3\}$, and then applying the letter-to-word substitution $\tau$ defined by $0 \mapsto +++$, $1 \...
Ronnie Pavlov's user avatar
9 votes
Accepted

Average and max. hitting time to a specific vertex

Notation: Let $G=(V,E)$ be an undirected simple graph of $n$ nodes. If $\tau_x$ is the (random) time it takes the walk to reach the node $x$, then write $H(v,x)=E_v(\tau_x)$. Denote $H_{\max}(x):=\...
Yuval Peres's user avatar
  • 14.1k
8 votes
Accepted

How to sample a uniform random polyomino?

The following Markov chain Monte Carlo algorithm would suffice, as it satisfies detailed balance and is ergodic. It may suffer from some sort of "critical slowing down" as the proportion of moves ...
Nathan Clisby's user avatar
8 votes
Accepted

Does Lackenby's polynomial bound on knot moves imply polynomial mixing in "Quantum Money From Knots?"

Thanks to HJRW2 for the flattering invitation here, and I will give an answer, but it might be not all that deep. In fact I haven't been on MO much lately; maybe I should visit it more. I don't see ...
Greg Kuperberg's user avatar
8 votes

All two-point correlations equal to $0$, three-point correlation not $0$?

$\def\ZZ{\mathbb{Z}}\def\RR{\mathbb{R}}$Here is a suggestion, with some details missing. Let $\theta$ be an irrational number and set $r_n = \{ \theta n^2 \}$, where $\{ \alpha \}$ is the fractional ...
David E Speyer's user avatar
7 votes

Random walk to stay in an interval forever

The crucial requirement is that $\sum_{i=0}^\infty t_i^2 < \infty$. See Kolmogorov's two-series theorem and also the more general Kolmogorov's three-series theorem.
Ori Gurel-Gurevich's user avatar
7 votes

"Surprising" examples of Markov chains

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 ...
Olivier's user avatar
  • 468
7 votes

what is the number of paths returning to 0 on the hexagonal lattice

If you want a rough answer, it is something of the order of $\frac{3^n}{n}$. This random paths are easier than self avoiding walks, you can think of these paths in this way: If you consider the even ...
shurtados's user avatar
  • 1,019
7 votes

Direct proof of unique invariant distribution for ergodic, positive-recurrent Markov chain

I came across another proof, by chance, for finite $I$. I saw this in old lecture notes by Peres on mixing times: Mixing for Markov Chains and Spin Systems (2005). Definition (Harmonic). A function $...
user24601's user avatar
  • 165
6 votes

"Surprising" examples of Markov chains

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 ...
Oliver Nash's user avatar
  • 1,424
6 votes

First passage time of a 1D simple random walk in a discrete time infinite markov chain

There's a standard result that says, in your notation, that the probability $P(\tau = n)$ of hitting 1 for the first time at time $n$ is $\frac{|m-1|}{n} P(i_n = 1)$. See MR2456097 van der ...
Nate Eldredge's user avatar
6 votes
Accepted

Lower bound on the entries of the Perron vector

This seems to be answered in the accepted answer to this question: The height of the Perron-Frobenius eigenvector For convenience, here is the estimate:
Igor Rivin's user avatar
  • 95.7k
6 votes
Accepted

English translation of a Russian paper by Gordin and Lifšic

This journal was transllated into English as Soviet Mathematics. Doklady Many US libraries subscribed it. If you have access to a university library, and it does not have it, use ILL. Here is the ...
Alexandre Eremenko's user avatar
6 votes

All two-point correlations equal to $0$, three-point correlation not $0$?

Let $\{b_n\}_{n \ge 1}$ be a sequence of independent random variables taking the values $\pm 1$ with probability $1/2$ each. Define $\{a_n\}_{n \ge 1}$ by $a_n=b_{n-1} b_{n-2}$ if $\; n \equiv 0 \mod ...
Yuval Peres's user avatar
  • 14.1k
6 votes
Accepted

Random walk on $\mathbb{Z}^3$. Expected number of visits and probability of return

This is a a general fact about transient Markov chains and the random walk on $\mathbb{Z}^3$ is transient. Denote by $T_0$ the moment of first return to the origin. (The moment $t=0$ is not ...
Liviu Nicolaescu's user avatar
5 votes

How to sample a uniform random polyomino?

Here is an approach to estimating parameters of uniformly random polyominoes of $n$ squares without generating random ones uniformly. First define a rooted tree whose root is the single square and ...
Brendan McKay's user avatar
5 votes

Frequency of visiting states in Markov chains

An ergodic finite Markov chain satisfies a $0-1$ law. If it is possible (i.e. probability $> 0$) to have more than $b$ visits to state $m$ in a time interval of length $a$, then with probability $1$...
Robert Israel's user avatar
5 votes
Accepted

Ergodicity of the product Markov chain

No - this is not true. The minimal example is provided by the deterministic Markov chain with two states (so that the state space is $\mathbb Z_2=\{0,1\}$) with the deterministic transitions $x\mapsto ...
R W's user avatar
  • 16.8k
5 votes

"Surprising" examples of Markov chains

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 ...
Leonid Petrov's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible