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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

### 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:

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

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

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

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

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

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

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

#### Related Tags

markov-chains × 545pr.probability × 353

stochastic-processes × 185

random-walks × 60

reference-request × 48

measure-theory × 37

ergodic-theory × 35

st.statistics × 32

linear-algebra × 30

probability-distributions × 29

graph-theory × 28

fa.functional-analysis × 24

matrices × 24

co.combinatorics × 21

stochastic-calculus × 16

ds.dynamical-systems × 15

sp.spectral-theory × 13

stochastic-differential-equations × 13

semigroups-of-operators × 13

limits-and-convergence × 12

it.information-theory × 12

hidden-markov-models × 11

inequalities × 10

oc.optimization-and-control × 10

spectral-graph-theory × 9