106 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 ...
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.
  • 21.9k
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 ...
21 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 ...
  • 21.9k
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) = \...
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 ...
  • 54.3k
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 ...
  • 28k
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 ...
  • 7,129
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=|...
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 \...
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):=\...
  • 13.2k
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 ...
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 ...
7 votes

Can ergodic theory help to prove ergodicity of general Markov chain?

OK - so you are talking about the ergodicity of a Markov chain with respect to a finite stationary measure. One general result you should be aware of is that in this situation ergodicity of the time ...
  • 15.8k
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.
7 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 ...
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 ...
  • 448
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 ...
  • 1,010
6 votes
Accepted

Equalizing Geometric means of Graph Cycles

I am not 100% sure I am not misusing the Perron-Frobenius Theorem, but I think that it justifies all the assumptions I am going to make in the following. The final construction itself is very simple. ...
  • 1,129
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 ...
  • 1,354
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 ...
6 votes
Accepted

Markov chain and random iteration of functions

It is much more natural and convenient to metrize the weak topology on the space of measures with the transportation (aka Kantorovich-Rubinshtein, aka 1-Wasserstein) metric, especially in what ...
  • 15.8k
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 ...
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 ...
  • 13.2k
5 votes

Does every (generalized?) Markov chain admit transition probabilities?

Under mild conditions on the state space $(S, \mathcal{S})$, it is true. For instance, it is sufficient that it be standard Borel. In that case, each $\xi_k$ admits a regular conditional ...
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$...
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 ...
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 ...
  • 15.8k
5 votes

Markov Process, Markov Chain

These terms (Markov chain / Markov process) seems to be mostly interchangeable, especially if one cares to specify whether the time is discrete or continuous. I would prefer "chain" to mean discrete ...
5 votes
Accepted

Does MCMC overcome the curse of dimensionality?

You need a global convexity to enjoy the optimal convergence rate, otherwise even local convexity will almost surely(not in probabilistic sense) lead to the worst rate you pointed out. MCMC(Markov ...
  • 7,583

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