98

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 probability of the appearance of a vowel was found to depend only on the letter immediately preceding it, with $p_{\text{vowel after consonant}}=0.663$ and $p_{\text{...


28

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 generating a Markov chain from a given proposal Markov chain as follows. A proposal move is computed according to the proposal Markov chain, and then accepted with a ...


27

I believe that if $(X_n)$ is a biased simple random walk on $[-N,N]$, then $|X_n|$ is a Markov chain.


22

If you have time, I highly recommend this Coursera course. The videos are available for free and are truly excellent. The teacher is Geoffrey Hinton, who is one of the main players in the area, and he does an excellent job of providing both clear definitions and useful intuition. In general, I wouldn't expect to see perfect theorem-lemma-proof exposition ...


20

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 $b$ with digits chosen uniformly random, the carries form a markov chain 1 12021 01111 11111 11111 11011 10111 01111 11111 21011 1112. 43935 23749 58561 ...


12

EDIT2. (5th Nov, 2014). Based on Darij's comments, am editing the answer to improve its clarity. The answer below shows how to get both eigenvalues and eigenvectors (my original answer was just for eigenvectors). Eigenvalues The key idea is to consider $P^{-1}$. Some (Markovian) guessing leads us to the following subdiagonal matrix: \begin{equation*} L_n ...


11

I think the expected time for stumbling across the solution is roughly proportional to the number of configurations. The process you describe is walking randomly on a Cayley graph. The limiting distribution is uniform, so after a large number of steps you will be in approximately a random place and the chance of that being the solution is the reciprocal of ...


11

Chris Olah has a great blog post on how topology relates to machine learning ("machine learning untangles highly kneaded spaces"). I will let him summarize: While it is challenging to understand the behavior of deep neural networks in general, it turns out to be much easier to explore low-dimensional deep neural networks – networks that only have ...


11

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 $2\cos t=z+z^{-1}, 2i\sin t=z-z^{-1}$, so for positive $3+\sqrt 2$ (I absolutely loved this red herring) the direction is that of $z+\delta z^{-1}$ with $|\...


11

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 about whether the work is in the ML domain or in a closely related domain. Though, I agree, in ML, often MCMC is used with Bayesian methods, and given the ...


11

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) = \sum_{k=0}^m \binom{2k}{k} \binom{m}{k}^2$$ if $n= 2m$ is even, and $0$ otherwise. This is sequence A002893 on OEIS. According to OEIS, the number of paths is ...


10

I have a blog post which discusses some of the connections between deep learning and advanced theoretical physics such as spin funnels and the renormalization group http://charlesmartin14.wordpress.com/2015/03/25/why-does-deep-learning-work/ http://charlesmartin14.wordpress.com/2015/04/01/why-deep-learning-works-ii-the-renormalization-group/


10

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 nonnegative submartingale, so that Doob's martingale inequality yields $$ \mathbb{P}[ \max_{1 \leq j \leq n} M_j > 1 ] \leq \mathbb{E}[M_n^2] = \sum_{i=1}^n t_i^...


10

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=|S_n|$ is still a Markov chain. See e.g. Proposition 4.1.1 of [S.Ross, "Stochastic Processes"].


9

Not a complete answer, but some further numerical observations. We know that the eigenvector for $\lambda = 1$ is $(1,1,1,\ldots,1)$. David Speyer notes in a comment that experimentation with small $n$ suggests the following generalization: the eigenvector for $\lambda_i = (-1)^{i-1}/i$ has $j$-th coordinate a polynomial of degree $i-1$ in $j$. For each $i$...


7

This is not so surprising, and is related to the lack of phase transition in the one dimensional Ising model. Consider first why the mixing time might be large. If $\beta$ is very high, and we start with a configuration where half the circle is + and half -, it will take a fairly long time for the chain to converge to one of the extreme states. (Roughly $d^...


7

By definition, the transition probability of a Feller process depends continuously on the starting point (in topology of weak convergence of measures, but maybe you don't have to say this in your pedagogical context). So if you change the starting point just a little bit, the distribution at, say, time $1$ will also be deformed only a bit. An example of a ...


7

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 shift in the path space (this is essentially the definition you use - you just refer to the corresponding ergodic theorem) is equivalent to "irreducibility" (...


7

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

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 which are legal might decay as a power of the system size, but I don't have clear intuition about this. I don't know if there's anything better in the literature. ...


7

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 nice examples within the 61 references citing this paper on MathSciNet). The theorem says that 2 times the supremum of a random walk minus that random walk is ...


7

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 any basis to say that Lackenby's result proves the mixing property of the quantum mixing proposal. There are many graphs where the diameter is better ...


7

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 steps, these paths describe a random walk in a triangular lattice, which is a bit easier to describe. Each step $X_i$ is given by adding a sixth root of unity $\...


6

Oops, too long for a comment: The expectation of the time until you reach a given point other than the origin is infinite already in one dimension. To see this, let $T$ be the expected time until you get from 0 to 1 (in the obvious 1-dimensional setting). The first step is either to the left or to the right, and if you go to $-1$, the expected remaining ...


6

1) No, it won't. Suppose $\mu_j(t)$ is the probability vector at time $t$. Let explosions happen at rate $r(t)$ at time $t$. Then we should have $$ \dfrac{d}{dt} \mu_j(t) = -3^j \mu_j(t) + (2/3) 3^{j-1} \mu_{j-1}(t) + (1/3) 3^{j+1} \mu_{j+1}(t) + r(t) \pi_j $$ where the first term on the right represents jumps out of state $j$, the second and third ...


6

From the physics point of view, the answer to your question is an immediate "yes": a nonunique Gibbs measure arises if there is a phase transition into a phase with multiple ground states (say, a phase transition into a ferromagnetic state with all spins aligned either up or down). A finite system has no phase transitions, there is a unique equilibrium state,...


6

A practical way to solve my question is using SAGE (however, I think the code is not suitable on this website). I got easily a nice picture for a Markov partition for the toral automorphism that lifts to the linear map on $\mathbb{R}^2$ with matrix $M=(1,1,1,0).$


6

Stroock's Markov processes book is, as far as I know, the most readily accessible treatment of inhomogeneous Markov processes: he does all the basics in the context of simulated annealing, which is neat. Kleinrock's volume 1 is also of interest, though "buggy" IIRC. In my experience the key object is the propagator $U(t) := \mathcal{TO}^* \int_0^t Q(s) \ ds$...


6

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. Let $V$ denote the vertex set of the underlying graph and let $A$ be the adjacency matrix, that is $A_{v,w} = 1$ if $v \to w$ and otherwise $A_{v,w} = 0$. This ...


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