Markov chain
A random process where the next state depends only on the current state; in machine learning, the basis of MCMC sampling, early n-gram language models, and slow iterative generators that GANs were designed to avoid.
A Markov chain is a random process with the Markov property: the next state depends only on the present state, not on the full history. Andrei Markov analysed such sequences in a 1906 paper; his 1913 study of vowel and consonant patterns in Pushkin’s Eugene Onegin is a classic early example.
In machine learning, Markov chains underpin MCMC procedures and generative models such as Boltzmann machines and deep belief networks, which often need many sampling steps and are slow at generation. That cost is one reason the 2014 GAN paper stresses training without Markov chains. The same idea also drives simple n-gram language models and word-by-word text generation, as in Claude Shannon’s 1948 experiments. Yoshua Bengio and colleagues later showed that neural networks could learn word embeddings while predicting the next word (article). See the GAN article for the adversarial approach that does without Markov chains.