a discrete-time Markov chain
/ MAR-kov /
A discrete-time Markov chain is the simplest and most useful memoryless process: a thing that hops, step by step, among a set of states, choosing each next state at random in a way that depends only on where it currently sits. Picture a token wandering a network of rooms, where each room posts the odds of going to each neighbouring room — and those odds never depend on how the token arrived.
Three ingredients define it. First, a state space: the set of possible states, here finite or countable, such as {sunny, rainy} or the integers. Second, the Markov property: the next state depends on the present state only. Third, transition probabilities P(i, j) = P(X_(n+1) = j given X_n = i), the chance of going from state i to state j in one step. When these probabilities do not change with time n (the usual case) the chain is called time-homogeneous, and the whole dynamics is captured by a single fixed table of one-step probabilities.
From those simple rules an astonishing amount follows: where the chain spends its time in the long run, whether it returns to where it started, how long until it first reaches a goal, and what equilibrium it settles into. Markov chains are the workhorse of stochastic modelling — they describe weather, web surfing (PageRank), queues, genetics, board games, and the sampling algorithms behind modern statistics.
Two-state weather: if today is sunny, tomorrow is sunny with probability 0.8 and rainy with 0.2; if rainy, rainy with 0.6 and sunny with 0.4. That is a complete Markov chain. To simulate it, start somewhere, then at each step roll against the current state's two probabilities to pick tomorrow — never looking further back than today.
A chain is fully specified by its states and its one-step transition probabilities — nothing else is needed.
Discrete-time means the chain advances in whole steps (step 0, 1, 2, ...), not that the state space is discrete — though it usually is. A chain over continuous states in discrete time is still discrete-time. Do not confuse the time index with the state space.