Today we end Nerd Week for Eponymy in August with the Markov Chain.
Andrey Markov was a professor of mathematics at St Petersburg University from 1880 until 1910, when he was removed from his professorship after he would not comply with an order to monitor his students (stemming from the student riots in 1908). In 1917 he was reinstated and continued lecturing on differential calculus and probability until his death in 1922.
The Markov Chain is a probabilistic state machine that uses the current state of a system (i.e. the values of all random variables) to generate a new state. What separates Markov chains from similar state machines is that they are “memoryless;” any previous state the machine had before the current one is forgotten when choosing a state transition. The probability of moving to any given future state is expressed as a function of the current state.
One common use of the Markov Chain is generative text. Using a corpus of existing text, each word is indexed by the probability of other words occurring after it. The text is then generated by a random walk from each word to a possible next word. The results can sometimes sound like human writing and sometimes very much not, the distinction embodied in the tweet linked here.
