One very important concept within probability theory is the Markov Chain. A Markov Chain is a stochastic model that describes a sequence of states in which the probability of moving to the next state only depends on the current state, not on the history of previously visited states. This is called the Markov (or memoryless) property.
A trivial situation that can be modeled with a Markov Chain would be a coin flip. Let state represent ‘heads’ and state represent ‘tails’. Thus the system has exactly two possible states.
The next and certainly more interesting question is concerned about the possible transitions between those states. In our case this is very easy. On each flip we can either remain in the current state or we can transition into the other state. Famously, the probability of each of those outcomes is , assuming the coin is fair.
Those transitions between the states can now be displayed in a so called Transition Matrix. The Transition Matrix alone completely specifies a Markov Chain, together with an initial distribution. The accompanying directed graph (displayed above) is simply a visual representation of the non‑zero entries of that Matrix.
Of course there is a lot more to Markov Chains. They can be used for very interesting things. For instance they are used to determine the "Page Rank" of websites in the internet on Google. In order to determine the Page Rank, they modeled the web by adding a Vertex (state) for each website and an Edge (transition) for each link between the websites. They went on, simulating a walk through the web by utilizing a "surfer" that "surfs" the web. There is alot more to it, but this process results in a distrubution of probabilities for the surfer to arrive at each of the websites which is then used to rank the websites. More probable websites were deemed to be more relevant than the ones with less probability for the surfer to arrive at them.
Because a single Matrix captures the entire dynamics, Markov Chains provide a compact yet powerful framework for modelling anything that evolves step‑by‑step from flipping coins to navigating the entire web.