# Tag Info

### "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 ...
• 182k
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.
• 22.6k

### "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 ...
• 6,015

### "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 ...
• 22.7k
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, ...
• 11.7k

### 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)$. ...
• 51.8k
Accepted

• 7,209

• 2,503
Accepted

• 165

### "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,424

### 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 ...
• 29.5k
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:
• 95.7k
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 ...
• 89.8k
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 ... • 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 ... • 34.2k 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 ... • 37.4k 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$... • 53.9k 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 ...
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 ...