Markov Models

I used to have a monthly habit tracker where the days of the month are the columns, and the rows are an activity one wants to track. I had one for exercise, where I would mark an x every day I managed to get a run or a workout done. Reviewing the data at the end of the month, I observed a distinct pattern. I would transition from days of being inactive to being active, stay in the active state for a few days, then transition back to being inactive, with this pattern repeating itself. It appeared to be quite like a Markov process. It felt like an epiphany at the moment for I had never considered Markov processes or models beyond the domain of technical applications where I had encountered them.

From its origins in language modeling, today Markov processes can be found in a host of different applications across technology (reinforcement learning, Google’s PageRank algorithm), linguistics (identifying authorship), politics (modeling political regimes, forecasting conflict), biology (modeling genetic drift), public health (evaluation of healthcare interventions), finance (modeling market regimes), and many more ^[1]. But what exactly is a Markov Chain and how did it enter the lexicon?

Definition¶

Markov models capture the transition probabilities between a finite set of states, including to the same state. Returning to my example of tracking workouts, on any given day, I could be in one of 2 states - active or inactive. Let’s suppose I start in the active state (i.e. I have completed an activity today). The transition probabilities now tell me how likely I am to remain in that state, or transition to the inactive state the next day. In other words, given that I have completed a workout today, the model tells me how likely am I to workout tomorrow. These probabilities are derived from my history of prior activity, such as the patterns of Xs and blanks in my planner. Given the states and probabilities, one only needs to know what state I am in today, to predict what state I will be in tomorrow. As an example, if I am inactive today, let’s suppose we derive from the historic data that I have a 90% chance (probability = 0.9) of staying inactive tomorrow, and a 10% chance of transitioning to an active state i.e working out tomorrow. If I am active today, I have a 70% chance of remaining active tomorrow, or a 30% chance of transitioning to being inactive. This is represented in the figure below:

These state transitions can be represented as a matrix as below. Let’s call this matrix $P$

The above matrix can be thought of as representing the transitions from today (rows) to tomorrow (columns). So 0.3 above represents the probability of me being inactive tomorrow, given that I am active today. This matrix can be used to get the probabilities for states for any day in the future. For e.g. to get the likelihood of me being active or inactive 2 days from now, I simply take a dot product of the matrix with itself i.e. $P.P=P^2$

If we want to see what the transition probabilities look like a week from now, we evaluate $P^7$

For 2 weeks from today, the transition probabilities are given by $P^{14}$

As we go further out in time, we see the rows having the same values i.e. independent of what state I am in today, my likelihood of being active 2 weeks from now is ~0.25 and of being inactive is ~0.75. The Markov model is said to be in equilibrium, where the probabilities don’t change from day to day, and they converge to long term average values of being active and inactive. To verify that this is the case, I have calculated below the long term average by generating the state on each day using our transition probability matrix $P$ for 10000 days, and count the number each state occurs.

We observe that the long term averages correspond to a probability of being active ~25% of the time, and inactive 75% of the time, which lines up with the equilibrium Markov transition probabilities.

We can also derive the probability of being active in theory. It is given by

where $P(active|inactive)$ is the transition probability from inactive to active which is 0.1 in our example, and P(active|active) is the self-transition probability to being active which is 0.7 in our example.

We can therefore show that

History¶

The idea of chain dependence of probabilities that we now refer to as Markov Chains was outlined in a 1906 paper by the Russian mathematician, Andrei Andreevich Markov (1856-1922). A. A. Markov got his PhD in 1884 under Pafnuty Chebyshev (of the Chebyshev’s inequality fame), and subsequently became a faculty at St. Petersburg University, teaching courses in probability theory, analysis and calculus. At the time of publication of his 1906 paper, Markov was 50 and had retired.

The motivation for Markov’s paper appears to have been a paper published in 1902 by Pavel Nekrasov, a theologian turned mathematician. In the paper, Nekrasov claimed that independence is a necessary condition for the law of large numbers. There appears to have been a theological parallel to this assertion in that the independence of events suggests the existence of free will. Markov’s opinion of Neskarov’s work and how this motivated his paper on chain dependence of probabilities comes from a correspondence to A. A Chuprov in 1910 where he writes^[2]

The unique service of P. A. Nekrasov, in my opinion, is namely this: he brings out sharply his delusion, shared, I believe, by many, that independence is a necessary condition for the law of large numbers. This circumstance prompted me to explain, in a series of articles, that the law of large numbers and Laplace’s formula can apply also to dependent variables... I considered variables connected in a simple chain and from this came the idea of the possibility of extending the limit theorems of the calculus of probability also to a complex chain.

In a Markov chain, each state depends on the prior state, and so each “draw” of a state value using this model is not independent. Yet over a large number of such draws, they converge to the long term averages for each state, as we have seen in our earlier example.

Markov subsequently published additional papers on chains, and in 1913, in the 3rd edition of his book on Probability Theory, he applied his work on chains to the sequence of 20,000 letters from Alexander Pushkin’s classic novel in verse, Eugene Onegin. Here, Markov counted the number of vowels(v) and consonants(c), and also their combinations - vv, vc, cv, cc - a manual and tedious process. He was able to show that the probability of two vowels occuring together is far lower than if they were treated as independent events, suggesting that the letter probabilities are not independent.

I will try to replicate Markov’s analysis of Eugene Onegin, with a few variations. I will use the English translation from Gutenberg by Henry Spalding, and will follow the description of the analysis specified in an article referencing his work by Brian Hayes. There are 2 parts to the analysis according to Hayes. In the first part, Markov used the first 20,000 letters of the poem after removing all punctuation and whitespace, so they are a long sequence of letters. He then split it into 200 blocks of 10x10 characters and calculated the mean number of vowels for each of these block and the variance. In the second part, he calculated the frequency of vowels (v) and consonants (c), and pairs of vowel-vowel (vv), vowel-consonant (vc), consonant-vowel (cv), and consonant-consonant (cc) in the 20,000 letter sample. He used this values to check for independence.

We begin by reading in the text, cleaning it up to remove irrelevant notes and references and other artifacts, and also spaces and punctuation, to get to a long string of letters. We then keep the first 20,000 characters, and map them to vowels (v) and consonants(c). An example of the cleaned text, and its mapped version to v and c is shown below

For Part 1, we split the text into 200 blocks of 100 characters each, calculate the mean number of vowels in each of them, and compare it with mean for the entire sample

The plot above shows the mean vowel % for the entire sample (red dashed line) and those for each of the individual 100-character blocks. The sample has 37.8% vowels. This is lower than the 43.2% observed by Markov. Baring any errors above, this could be due to difference in language and/or how the texts were preprocessed.

For part 2, we will track the counts for each combination of vowels and consonants, along with the expected counts and proportions assuming independence of characters in each pair.

We observe 1229 double vowel pairs (6.1% of all pairs). If the vowels were independent, then the expected proportion of 2 vowel pairs will be (0.378)x(0.378) = 0.143 i.e 14.3%. In the 19999 possible pairs of 20000 characters, we would expect to see 0.143x19999 or about 2857 vowel pairs. We observe only 1229. We observe similar disparities in the proportions for the remaining pairs. For e.g. we observe much higher proportions of vowel-consonant sequences than would have been predicted were they independent. This suggests that the sequence of letters in the text are not independent.

We have reached similar conclusions to Markov, with less than 100 lines of code that allows us to escape the tedium of doing all this by hand, as Markov had laboriously done over a century ago.

Hidden Markov Models¶

Hidden Markov Models (HMMs) are a type of Markov Models where the states are hidden, and all we see are observations (sometimes referred to as emissions), based on which we can try to infer the hidden states. Using our workout-tracking example from before, for each day I have a cross (X) in our planner for when I am active, and a blank (O) for when I am inactive. In explaining Markov chains, we had used ‘active’ and ‘inactive’ as our states. Now, let’s suppose that whether I am active or inactive on any given day depends on an underlying process, say the weather. If the weather is sunny then I am 90% likely to be active. If it is cloudy, then I am 50% likely to be active, and if it is rainy then I am 10% likely to be active. In an HMM formulation of this problem, we would seek to model the underlying process of the weather on any given day and the transitions in weather from one day to another between the states of ‘sunny’, ‘cloudy’ and ‘rainy’. However, we don’t know what the weather is like on any given day. All we observe is whether I was active or not. Hence the weather on each day i.e. ‘sunny’, ‘cloudy’ and ‘rainy’ are referred to as hidden states. A visual representation of this example is shown below

An HMM is characterized by the following parameters ^[3]:

• N: the number of states in the model (in our example, we have 3 different states i.e. types of weather - rainy, cloudy, and sunny). The individual states are labeled as $\{1,2,..,N\}$ with the state at time $t$ being denoted by $q_t$

• M: the number of distinct observation symbols per state (in our example, we have 2 distinct observation symbols - active and inactive). We denote the individual symbols as $V = \{v_1, v_2,...,v_M\}$

• A: the state transition probability distribution, i.e. $A=\{a_{ij}\}$ where $a_{ij} = P[q_{t+1} = j|q_t = i]$, $1{\le}i,j{\le}N$ (in our example, this represents the transitions between the states of ‘sunny’, ‘cloudy’ and ‘rainy’ from one day to another)

• B: the observation symbol probability distribution, i.e. $B=\{b_j(k)\}$ where $b_j(k)=P[o_t=v_k|q_t=j]$, $1{\le}k{\le}M$ (in our example, this will be the likelihood, say, of being active, given that the weather is sunny)

• ${\pi}$: the initial state distribution, $\pi = \{\pi_i\}$ where $\pi_i = P[q_1=i]$, $1{\le}i{\le}N$ (in our example this is the probability of the initial state being ‘sunny’, ‘cloudy’ or ‘rainy’)

Since $A$,$B$ and $\pi$ encapsulate the values of N and M, we use the notation $\lambda=(A,B,\pi)$ to refer to the complete parameter set of the model. Once these parameters are specified, we can use it to generate a sequence. We will do so for our example.

We specify the state transition probabities $A$ as below

The observation symbol probability $B$ for each state is given below

Finally, the initial state distribution is specified below

Now that we have the parameter set for the model, we are ready to generate a sequence of observations. We do so as follows:

1. We start by picking an initial state based on the initial state distribution $\pi$.

2. We set the time $t=1$

3. Next we pick an observation based on the observation symbol probability for that state in $B$. This is our observation for time $t$.

4. Now, we transition to the next state using the state transition probability $A$

5. We increment our time $t=t+1$ and return to step 3 if $t<T$, otherwise stop

6. We repeat steps 2

We will generate a sequence of length 8 (i.e. T=8) for ease of display below

Going from a model to a sequence is straightforward, however going from a sequence to a model is not. There are 3 basic problems HMMs need to solve to be useful.

1. Given the observation sequence $O$ and a model $\lambda$ how do we compute the probability that the sequence was produced by the model i.e. $P(O|\lambda)$?. This is referred to as the evaluation problem i.e. one of evaluating how well the model matches the observations.

2. Given the observation sequence $O$ and a model $\lambda$ how do we choose a corresponding state sequence $Q$ which best explains the observations? This problem looks to uncover the hidden states corresponding to the observations, given the model.

3. How do we adjust the model parameters $\lambda$ so as to best describe the observation sequence $O$ i.e. how do we maximize $P(O|\lambda)$? This is referred to as the training problem where we use the observation sequence to train an HMM model.

The evaluation problem can be solved by considering combinations of all possible states and calculating the likelihood of the observation given each state $P(O|Q,\lambda)$, and the probability of the state sequence given the model $P(Q|\lambda)$. Multiplying these two terms gives us $P(O,Q|\lambda)$ for each state sequence combination, and summing this over all possible state sequences gives us $P(O|\lambda)$. This approach is computationally complex. For N possible states and T time steps, we have $N^T$ possible state sequences for which we have to evaluate the likelihood of the observed values. For 5 states and 100 observations, we have $5^{100} = 7.8*10^{69}$ possible combinations. A less computationally intensive approach is to use the forward and backward procedure that works through each time step calculating probabilities and accumulating them.

For solving the second problem of identifying the best hidden states that match the observations, one simple approach is to pick a state that maximizes the probability of the observation. In our example, if the observation sequence we are given is $[inactive,active,inactive]$, then looking at the observation symbol probabulity $B$, we see that ‘inactive’ has the highest probability in state ‘rainy’ and ‘active’ has the highest probability in state ‘sunny’. So one guess for the states corresponding to the sequence of observations is $[rainy,sunny,rainy]$. One of the shortcomings is that it does not account for state transitions. For e.g. if the transition probability going from ‘rainy’ to ‘sunny’ were 0, the above sequence of states would not be valid. A better approach is the Viterbi algorithm that tracks the state with the best ‘score’ in each time step, uses the score in getting the best state and score in the next time step and so on. After the final time step, we have a sequence of states with the best score along each step in the sequence. The score accounts for transtion probabilities, avoiding the caveat in the prior approach.

The solution to the third problem, one of training the HMM, requires us to start with an initial model $\lambda$ and then iteratively re-estimate the parameters using the Baum-Welch Method (a form of expectation-maximization), to come up with an updated model $\bar{\lambda}$ such that $P(O|\bar{\lambda})>P(O|{\lambda})$. The method uses the forward and backward procedure referenced in the solution to the evaluation problem.

Applications

HMMs have been used extensively in speech recgonition. An example is training an HMM for each word in a vocabulary where the states can be the number of phonemes in the world, and the training data involves utterances of the word by different speakers. If there are 100 words in the vocabulary, this would involve 100 different HMM models. At inference time, an observed speech signal $O$ is evaluated against the HMM for each word in the vocabulary $P(O|{\lambda}^i)$, and the model that has the highest probability of generating the signal is identified. The word associated with the model is output as the recognized word. Other applications include computational biology, finance, and robotics.

Markov Decision Process¶

A Markov Decision Process (MDP) introduces the concept of actions and rewards to the standard Markov model. At each time step, a decision maker (i.e. agent) finds itself in a certain state, based on which it selects an action. As a consequence of the action, the agent receives a reward, and finds itself in a new state. The transition probabilities depend on the prior state and action, as do the rewards. The set of unique states characterize the environment in which the agent operates. The states satisfy the Markov property, in that the transition to a given state depends only on the prior state and action, with the prior state assumed to include all information on past agent-environment interactions.

To illustrate an MDP, we will work with a variation of our activity example. Let’s suppose that being active or inactive are actions I take based on my health. If I am healthy, I can choose to be active (for which I get a positive reward $R$), or inactive (for which I get a small reward for being healthy $0.25R$). In being active, there is a small probability $\alpha$ that I may get injured. In the injured state, the only possible action is being inactive (i.e. resting), with a probability $\beta$ I may return to the healthy state, and a probability $1-\beta$ where I stay in the injured state. For each day in the injured state, I receive a negative reward ($-2R$). The set of start states, actions, end states, transition probabilities, and rewards are shown below. The notation $s$ refers to the current state, $a$ to the action taken from the current state, $s'$ to the next state, $p(s'|s,a)$ to the state transition probability to the next state given the current state and action, and $r(s,a,s')$ to the reward associated with the current state, action, and next state.^[4]

An illustration of the MDP process with states, actions and transition probabilities and rewards is shown below

Our goal in the MDP process is to take actions starting from an initial state that maximizes our total reward. We do so by navigating these loops (or rather specifying a simulation with an agent that navigates these loops) so that we can learn the optimal policy i.e. the action we need to take in each state to maximize our rewards.

MDPs are an integral part of reinforcement learning (RL), and therefore play a role in the development of large language models (LLMs) where RL is used to improve the fine-tuning and reasoning capabilities of LLMs. They have also been applied to medical decision making and finance, among others.

MDP and HMMs come together in Partially Observable Markov Decision Process (POMDP) which is like an MDP with rewards and actions, except the states are hidden, and we only have observations emitted by the states, much like what we have seen in HMMs. A grid explaining the distinction is shown below ^[5]

A detailed list of applications for POMDP can be found in this survey by Anthony Cassandra.

Wrap-up¶

Markov models span over a 100 year timeline starting with A. A. Markov’s first paper in 1906 to settle a mathematical (and possibly theological) score with a rival, to its varied manifestations and wide use today across technology, medicine, finance and society. Markov’s application of his chained probabilities to the text of Eugene Onegin stands as a precursor to its subsequent use in speech and language modeling, most recently in the refinement of large language models (LLMs) using reinforcement learning.

A quick note on references: I have linked to relevant papers and texts where I have mentioned them. There are a few that bear a particular mention. Brian Hayes article titled First Links in the Markov Chain in the March-April 2013 issue of American Scientist is an excellent introduction to Markov Chains and its history. The Life and Work of A.A. Markov by Basharin, Langville, and Naumov presents a detailed biography of A. A. Markov, as does Markov and the Birth of Chain Dependence Theory by E. Seneta, which further delves into the mathematical details of Markov’s 1906 paper. A description to Hidden Markov Models (HMM) would be incomplete without a reference to A tutorial on Hidden Markov Models and Selected Applications in Speech Recognition by L. Rabiner.