You've seen how individual random events occur (Poisson processes) and how sequences of random steps can lead to unpredictable paths (random walks). Now, let's combine these ideas to model systems that transition between different "states" based on probabilities. This is the core concept behind Markov Chains.
A Markov chain is a stochastic process that moves from one state to another on a state space. The key, and often unsettling, property of a simple Markov chain is that the probability of moving to the next state depends only on the current state, not on the sequence of events that preceded it. This is known as the Markov property, and it implies a certain lack of memory in the system.
Think about your digital life as a series of states: "Scrolling Social Media," "Working," "Feeling Anxious," "Watching Cat Videos." A Markov chain can model the probabilities of transitioning between these states. From "Scrolling Social Media," you might have a high probability of transitioning to "Watching Cat Videos," a moderate probability of transitioning to "Feeling Anxious," and a low probability of transitioning to "Working." The crucial (and depressing) part is that, in a simple Markov model, this probability only depends on you currently being in the "Scrolling Social Media" state, not on how you got there.
Algorithms use concepts similar to Markov chains to model your likely next action or state based on your current one. If you're in the "Watching Cat Videos" state, they know you're highly likely to go to the "Scrolling Social Media" state next, and they prepare accordingly. Understanding this helps you see how your behavior is being modeled as a series of predictable (to them) transitions.
Let's visualize a simple Markov chain with a few states and transitions. Click on a state to see its outgoing transitions. Click the background to reset.
A Markov chain exists within a set of possible states. These are the distinct conditions the system can be in. We can denote the set of states as $S = \{s_1, s_2, \dots, s_N\}$.
In our visualization, the amber circles represent the different states in our simple Markov chain.
At each time step, the system can transition from its current state to another state (which could be the same state). These movements are called transitions.
The blue arrows in the visualization represent possible transitions between states.
Each possible transition has a transition probability. This is the likelihood of moving from state $s_i$ to state $s_j$. We denote this probability as $P(s_j | s_i)$, meaning the probability of being in state $s_j$ given that the system is currently in state $s_i$.
The crucial Markov property states that the probability of transitioning to the next state depends only on the current state:
$P(X_{t+1} = s_j | X_t = s_i, X_{t-1} = s_{k}, \dots) = P(X_{t+1} = s_j | X_t = s_i)$
Where $X_t$ is the state of the system at time $t$. This means the past history doesn't matter, only the present state.
In the visualization, the numbers on the arrows represent these transition probabilities. The sum of probabilities of all outgoing transitions from a state must equal 1.
The transition probabilities between all states can be organized into a transition matrix, often denoted by $T$. If there are $N$ states, $T$ is an $N \times N$ matrix where the element in row $i$ and column $j$ is the probability of transitioning from state $s_i$ to state $s_j$.
$T_{ij} = P(s_j | s_i)$
This matrix completely defines the dynamics of the Markov chain. By raising the transition matrix to a power, you can calculate the probability of being in any state after multiple time steps. This is how algorithms can predict your likely state in the near future based on your current digital activity.