Markov Chain

Definition

A Markov Chain is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. This is known as the Markov Property (“memorylessness”).

Why It Matters

Markov chains allow us to model systems where the future depends only on the present; they are the mathematical engine behind everything from Google’s PageRank to the predictive text on your phone, making them essential for navigating the probabilistic nature of the world.

Core Concepts

• State Space: The set of all possible states the system can occupy (e.g., the number of customers in a queue: 0, 1, 2, …).

• Transition Probability: The probability of moving from state $i$ to state $j$ in a single step.

  • How to read: “The probability of transitioning from state i to state j.”
  • Meaning: Transition probability from state $i$ to state $j$—the one-step chance of landing in $j$ given the system is currently in $i$.

• Steady State: A condition where the probability distribution of the states remains constant over time.

• Application in Queuing: Used for the analytical solution of simple queues (e.g., M/M/1), where the number of customers increases based on arrival rate ($\lambda$) and decreases based on service rate ($\mu$).

  • How to read: “The arrival rate lambda and the service rate mu.”
  • Meaning / when to use: $\lambda$ is the arrival rate (how fast customers enter); $\mu$ is the service rate (how fast one server finishes). Their ratio determines queue length and wait time.

Connected Concepts

• Queuing Systems (M&S)
• Kendall’s Notation
• Stochastic Process
• Probabilistic Thinking