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

- 155k

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

- 5,690

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

- 2,025

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

- 1,767

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

- 1,469

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

- 54.5k

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

- 142k

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.

- 6,561

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

- 376

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

- 27.9k

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

- 81.4k

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

- 27.9k

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

- 51.8k

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

- 34.8k

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

- 1,620

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

#### Related Tags

markov-chains × 492pr.probability × 324

stochastic-processes × 166

random-walks × 55

reference-request × 41

measure-theory × 32

ergodic-theory × 32

st.statistics × 30

probability-distributions × 29

linear-algebra × 27

graph-theory × 27

fa.functional-analysis × 22

co.combinatorics × 21

matrices × 20

sp.spectral-theory × 13

stochastic-calculus × 13

semigroups-of-operators × 12

ds.dynamical-systems × 11

oc.optimization-and-control × 11

inequalities × 10

it.information-theory × 10

stochastic-differential-equations × 10

hidden-markov-models × 10

limits-and-convergence × 9

operator-theory × 8