38. Markov Chains

There are certain events which are independent of each other, like subsequent coin tosses and their results, throw of dice. But there are others where the next event or state is dependent on current state.

Sort of current state changes the probability of next state. Such sequences are called Markov chain. 

Markov chains, named after Andrey Markov, are mathematical systems that hop from one "state" (a situation or set of values) to another. For example, if you made a Markov chain model of a baby's behavior, you might include "playing," "eating", "sleeping," and "crying" as states, which together with other behaviors could form a 'state space': a list of all possible states. In addition, on top of the state space, a Markov chain tells you the probabilitiy of hopping, or "transitioning," from one state to any other state---e.g., the chance that a baby currently playing will fall asleep in the next five minutes without crying first.

In independent chains, there is no 'memory'. In markov chains, there is memory in the system, or perhaps the system trains, adapts, learns.

Markov chain is conditioned on only one current state. 

A Markov chain has short-term memory, it only remembers where you are now and where you want to go next.

This means the path you took to reach a particular state doesn’t impact the likelihood of moving to another state. The only thing that can influence the likelihood of going from one state to the other is the state you are currently in.

 

Sequences of repetitions such as these where it is assumed that:

• the probability of each possible outcome is conditional only on the immediately preceding outcome, and
• the conditional probabilities for each possible outcome are the same on each occasion (that is the same matrix is used for each transition)

are called Markov chains, named after a Russian mathematician

In general, a Markov chain is defined by:

• a transition matrix, T, which for a situation that has m outcomes or states is a square matrix of dimension m × m. The elements of the transition matrix are conditional probabilities.
• an initial state vector, S0, which has dimension m × 1, and gives information about the Markov chain at the beginning of the sequence, or step 0. The elements of the initial state vector may be numbers, percentages or the results of an individual trial.

Here this article is very helpful to understand the basics and construction.

The next thing you do is to encode the dependencies between states, using conditional probabilities. In the context of Markov models, these conditional probabilities are called transition probabilities. Transition probabilities describe the transition between states in the chain as a conditional probability.

With two states (A and B) in our state space, there are 4 possible transitions (not 2, because a state can transition back into itself). If we're at 'A' we could transition to 'B' or stay at 'A'. If we're at 'B' we could transition to 'A' or stay at 'B'. In this two state diagram, the probability of transitioning from any state to any other state is 0.5.

Of course, real modelers don't always draw out Markov chain diagrams. Instead they use a "transition matrix" to tally the transition probabilities. Every state in the state space is included once as a row and again as a column, and each cell in the matrix tells you the probability of transitioning from its row's state to its column's state. So, in the matrix, the cells do the same job that the arrows do in the diagram.

A characteristic of what is called a regular Markov chain is that, over a large enough number of iterations, all transition probabilities will converge to a value and remain unchanged[5]. This means that, after a sufficient number of iterations, the likelihood of ending up in any given state of the chain is the same, regardless of where you start.

So, when the chain reaches this point, we can say the transition probabilities reached a steady-state.

This is what Markov ultimately wanted to prove!

Only regular Markov chains converge over time. And if your Markov Chain does not converge, it has a periodic pattern.

In Markov chains that have periodicity, instead of settling on a steady-state value for the likelihood of ending in a given state, you’ll get the same transition probabilities from time to time.

This other place also explains it visually. And other ideas.

A Markov chain is a stochastic model that uses mathematics to predict the probability of a sequence of events occurring based on the most recent event. A common example of a Markov chain in action is the way Google predicts the next word in your sentence based on your previous entry within Gmail. 

A Markov chain is a stochastic model created by Andrey Markov that outlines the probability associated with a sequence of events occurring based on the state in the previous event. It’s a very common and easy-to-understand model that’s frequently used in industries that deal with sequential data such as finance. Even Google’s page rank algorithm, which determines what links to show first in its search engine, is a type of Markov chain. Through mathematics, this model uses our observations to predict future events.

The main goal of the Markov process is to identify the probability of transitioning from one state to another. One of the primary appeals to Markov is that the future state of a stochastic variable is only dependent on its present state. An informal definition of a stochastic variable is described as a variable whose values depend on the outcomes of random occurrences.