102

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


27

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.


26

Update The Coursera course I recommended long ago has now gone offline, although you can find links to the slides and videos on Hinton's home page. In any case, the field has continued to advance dramatically and there are new results and more up-to-date expository work; see any of the more recent answers. For what it's worth, in the six years since I wrote ...


21

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


12

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

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/


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

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


9

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 \mapsto +--$, $2 \mapsto -+-$, $3 \mapsto --+$. (I'm abbreviating $1$ by $+$ and $-1$ by $-$.) The twofold independence comes from normality of $S$; you basically ...


8

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


8

$\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 part of $\alpha$. Then I claim that the pairs $(r_n, r_{n+j})$ are equidistributed in $(\RR/\ZZ)^2$, but $(r_n, r_{n+1}, r_{n+2})$ is not equidistributed in $(\...


7

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


7

You don't find much about time-inhomogeneous Markov chains because it's extremely difficult to prove anything about them without strong additional assumptions, and it's not clear what additional assumptions make sense. The only literature I'm aware of is some quite recent papers by Jessica Zúñiga and Laurent Saloff-Coste; see this page for links. (If there ...


7

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


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

Recently uploaded paper in Arxiv (1512.06293). This paper formalize concepts and proves them. And few others that you might check out: J. Bruna and S. Mallat, “Invariant Scattering Convolution Networks,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 35, no. 8, pp. 1872–1886, Aug. 2013. for Covnet A. Choromanska, M. Henaff, M. ...


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

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

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

Since this question got bumped up to the front page somehow, I'm taking the liberty to suggest a partial introduction to the "Math of Deep Learning" given in the following article: The Modern Mathematics of Deep Learning.


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