Markov Chain

A Markov Chain is a mathematical system that models a sequence of possible events, where the probability of the next event occurring depends only on the state attained in the immediately preceding event. This property is known as the Markov property or memorylessness. In other words, the chain’s future evolution is independent of its past history, given the present state.

Markov Chains are used to model systems that exhibit discrete transitions between a finite number of states, driven by probabilistic rules.

Context: Relation to LLMs and Traditional Language Modeling

The concept of the Markov Chain is fundamental to understanding the history and mechanics of language modeling, even though modern Large Language Models (LLMs) have moved far beyond the restrictive Markov property.

• Traditional Language Modeling: Before the deep learning revolution, text generation was often accomplished using a form of Markov Chain.
  • State and Transition: In this context, a state is a word or a short sequence of words (an N-gram), and the transition probability is the likelihood of one word following another.
  • Example (First-Order Markov Chain): The probability of the next word ($w_{i}$) depends only on the current word ($w_{i-1}$): $P(w_i | w_1, \dots, w_{i-1}) \approx P(w_i | w_{i-1})$. If the current state is “The cat sat on the”, a first-order chain would only look at “the” to predict the next word.
• Limitations and the Shift to Transformers: The inherent limitation of the Markov property is that human language requires long-range dependencies. The meaning of a sentence often depends on words far removed from the current position.
  • Short-Term Memory: Simple Markov models have extremely short “memory” (only remembering the last $N-1$ words).
  • Modern LLMs: Modern LLMs, built on the Transformer Architecture, overcome this by using the Attention Mechanism to process the entire Context Window simultaneously. This allows the model to capture dependencies that span hundreds or thousands of tokens, making the model non-Markovian and vastly superior at coherent Natural Language Generation (NLG).
• Modern Applications (Google PageRank): A famous, non-textual application of Markov Chains relevant to search is the original Google PageRank algorithm. PageRank models the internet as a massive Markov Chain, where each webpage is a state, and a hyperlink is a possible transition. The final PageRank score of a page is its steady-state probability (the long-term likelihood that a random web surfer would be on that page).

Key Components of a Markov Chain

1. States: A finite set of conditions the system can be in.
2. Transitions: The movement from one state to another.
3. Transition Probabilities: The probability associated with each transition, which depends only on the current state. This is often represented by a Transition Matrix.

For a first-order Markov Chain, the probability of the sequence $(S_1, S_2, S_3, \dots, S_n)$ is calculated as:

$$P(S_1, S_2, \dots, S_n) = P(S_1) \times P(S_2|S_1) \times P(S_3|S_2) \times \dots \times P(S_n|S_{n-1})$$

Related Terms

• N-gram: The sequential unit used in early, Markov-based language models.
• Attention Mechanism: The feature that allows modern LLMs to break the Markov property and model long-range dependencies.
• Recurrent Neural Network (RNN): An intermediate-era deep learning architecture that partially improved upon Markov Chains but still struggled with long-range dependencies compared to Transformers.