Markov chain - Fundamental Concepts

Overview of Markov Chains What is a Markov Chain? A Markov chain is a mathematical model for systems that evolve randomly over time. The key idea is remarkably simple and powerful: the future depends only on the present, not on the past. More formally, a Markov chain is a stochastic process—a sequence of random events unfolding over time—that satisfies the Markov property (also called memorylessness). This property states that given the current state of the system, all previous states contain no additional information about what happens next. Imagine you're tracking the weather: if you know it's raining today, the probability of rain tomorrow depends only on the fact that it's raining now. Historical information about whether it rained last week or last month doesn't matter. The diagram above illustrates a simple Markov chain with two states (E and A) and labeled transition probabilities. Notice how each arrow shows the probability of moving from one state to another in the next time step. This is the essence of a Markov chain in action. Discrete-Time vs. Continuous-Time Chains Markov chains are classified based on how time progresses: Discrete-Time Markov Chains (DTMC) proceed in steps—like turning pages in a book. At each discrete moment $t = 0, 1, 2, \ldots$, the system occupies a state. The system transitions from one state to another at each step according to transition probabilities. Most introductory problems involve discrete-time chains. Continuous-Time Markov Chains (CTMC) unfold continuously over real time. Rather than discrete jumps, the system can transition at any moment. These are more sophisticated and described using different mathematical tools (transition rate matrices instead of probability matrices). For now, the focus is on discrete-time chains, which are more intuitive and commonly taught first. State Space: What States Are Possible? The state space is simply the set of all possible states the system can occupy. For the weather example, the state space might be {Sunny, Rainy, Cloudy}. State spaces come in different sizes: Finite state space: The system can be in only finitely many states. Example: a coin that can be Heads or Tails (2 states). Countably infinite state space: The system can be in infinitely many distinct states, but they can be listed in a sequence like the positive integers. Example: the number of customers in a queue (0, 1, 2, 3, ...). Uncountable state space: The system can be in infinitely many states that cannot be counted sequentially. Example: the position of a particle in continuous space. (These are less commonly studied in introductory courses.) The structure of the state space determines which mathematical tools we use to analyze the chain. Transition Probabilities and the Transition Matrix In a discrete-time Markov chain, transitions between states are governed by transition probabilities. Let $P{ij}$ denote the probability of moving from state $i$ to state $j$ in one time step. When the state space is finite, all these probabilities can be organized into a transition matrix $P$, where: Row $i$ contains all transition probabilities starting from state $i$ Column $j$ contains all probabilities leading to state $j$ Entry $P{ij}$ is the probability of moving from state $i$ to state $j$ A crucial property: each row of the transition matrix must sum to 1, because from any given state, the system must transition somewhere (including possibly staying in the same state). Also, all entries are non-negative probabilities between 0 and 1. A matrix with these properties is called a right stochastic matrix or probability matrix. For example, if we have states A and E as shown in the diagram earlier, the transition matrix would look like: $$P = \begin{pmatrix} 0.3 & 0.7 \\ 0.4 & 0.6 \end{pmatrix}$$ where the first row represents transitions from E, and the second row represents transitions from A. <extrainfo> Countable and Infinite State Spaces For systems with countably infinite state spaces (like queue lengths), we still use transition matrices, but they're infinite-dimensional. The same principle applies: each row sums to 1, and all entries are non-negative. The mathematics becomes more subtle, but the core idea remains unchanged. </extrainfo> <extrainfo> Continuous-Time Markov Chains In a continuous-time Markov chain, the system can jump between states at any moment in time. Rather than transition probabilities, these chains are described by a transition rate matrix (also called the generator matrix or infinitesimal generator). In this matrix: Off-diagonal entries represent non-negative transition rates (how fast the system moves from one state to another) Diagonal entries are chosen so that each row sums to zero The continuous-time version is more mathematically involved and typically covered in advanced courses, so we don't need to focus on it here. </extrainfo> Key Takeaways The foundation of Markov chains rests on three pillars: The Markov property: The future depends only on the present state, not on history. The state space: The set of all possible configurations the system can occupy. Transition probabilities: The likelihood of moving from one state to another, organized in a transition matrix for finite state spaces. These concepts form the foundation for analyzing how systems evolve probabilistically over time.