Bernoulli processes, random walks, Markov chains, Poisson processes, and waiting times — probability that evolves over time
"Randomness is not merely an imperfection in our knowledge. It is woven into the fabric of how systems change over time."
Every model studied so far in this book has treated randomness as something that happens once. A coin flip produces a single outcome. A continuous random variable takes on a value drawn from a density function. A sample yields data used to estimate a parameter. In each case, randomness occurs and then the story ends.
But many of the most important processes in science, finance, engineering, biology, and computing involve randomness that unfolds over time. A stock price does not simply land on a value; it rises and falls through each trading hour. An epidemic does not reach its size in an instant; it spreads from person to person across days and weeks. Customers do not all arrive at a counter simultaneously; they stream in one by one as time passes.
These are stochastic processes: collections of random variables indexed by time. Chapter 13 develops the mathematical foundations of stochastic processes at a level appropriate for a first calculus-based course. The chapter begins by defining what a stochastic process is, then builds three fundamental classes of models — Bernoulli processes and random walks, Markov chains, and Poisson processes — before connecting them to waiting time distributions, reliability, queueing, and applications across science and computing.
A machine in a factory can be Working, Under Repair, or Failed on any given day. Each day, there is a chance the machine transitions between these states. In the long run, what fraction of days is the machine Working? What fraction is it Failed? By the end of this chapter, you will have the tools to answer such questions exactly — and to understand why the answers do not depend on what state the machine is in today.
A stochastic process asks a different kind of question from a single random variable. Instead of one random outcome, we have an entire trajectory: how does the system evolve? What is the probability of visiting certain states? Where does the process end up in the long run?
A stochastic process is a collection of random variables {X(t) : t ∈ T} defined on a common probability space, where T is an index set representing time.
When T = {0, 1, 2, …} the process is discrete-time. When T = [0, ∞) the process is continuous-time. The set of values each X(t) can take is the state space.
| Time Index | State Space | Example |
|---|---|---|
| Discrete | Discrete | Markov chain — weather states each day |
| Discrete | Continuous | Random walk on the real line |
| Continuous | Discrete | Poisson process — count of arrivals up to time t |
| Continuous | Continuous | Brownian motion — particle position at each instant |
For a fixed outcome ω in the sample space, the function t ↦ X(t, ω) is called a sample path or realization of the process. When you watch a stock price move through a trading day, you are observing one sample path drawn from a probability model governing all possible paths.
For a stochastic process, we need a way to describe how random variables at different times relate to one another. Two key structural properties appear in the most important processes.
Stationary increments: The distribution of X(t+s) − X(t) depends only on s, not on where in time t we are. What happens over any interval of length s looks the same statistically.
Independent increments: For non-overlapping intervals [t₁,t₂] and [t₃,t₄], the changes X(t₂)−X(t₁) and X(t₄)−X(t₃) are independent. Knowing what happened in one interval tells you nothing about a separate interval.
E[X(n)] = 0 for all n.Each step has expected change 0; the walk is centered at the origin.Var(X(n)) = n.The spread grows. After 100 steps the standard deviation is √100 = 10; after 10,000 steps, √10,000 = 100.The Bernoulli process is the simplest discrete-time stochastic process. It is built entirely from the Bernoulli trials studied in Chapter 3: independent coin flips with the same bias at every step.
A Bernoulli process is a sequence of independent Bernoulli random variables X₁, X₂, X₃, … each with P(Xₙ = 1) = p and P(Xₙ = 0) = 1 − p = q for some fixed p ∈ (0, 1).
| Quantity | Distribution | Mean | Variance |
|---|---|---|---|
| Successes in n trials: Sₙ = X₁ + … + Xₙ | Binomial(n, p) | np | npq |
| Time of first success: T = min{n ≥ 1 : Xₙ = 1} | Geometric(p) | 1/p | q/p² |
| Time between the (k−1)-th and k-th successes | Geometric(p) | 1/p | q/p² |
E[T] = 1/p = 1/0.75 = 4/3 ≈ 1.33 shots.
E[S₁₀] = 10(0.75) = 7.5.
P(S₁₀ ≥ 8) = C(10,8)(0.75)⁸(0.25)² + C(10,9)(0.75)⁹(0.25)¹ + C(10,10)(0.75)¹⁰
≈ 0.2816 + 0.1877 + 0.0563 ≈ 0.5256.
The Bernoulli process is the building block for random walks (sums of ±1 outcomes), the discrete analogue of the Poisson process, and the simplest example of a process with independent, identically distributed components. Every result here will reappear in continuous-time versions later in the chapter.
A random walk models motion through discrete steps where each step is determined by a random variable. The running sum S₀ = 0, Sₙ = Z₁ + Z₂ + ⋯ + Zₙ with i.i.d. steps Zₙ is the general form. The most studied case is the simple symmetric random walk on the integers, where P(Zₙ = +1) = P(Zₙ = −1) = 1/2.
E[Sₙ] = 0 The walk is centered at 0 for all n. Steps average to zero.
Var(Sₙ) = n Standard deviation is √n. The walk spreads at rate √n, not n.
Sₙ/√n → N(0,1) By the CLT, properly scaled walks converge to standard normal.
E[Zₙ] = p − q = 2p − 1. E[Sₙ] = n(2p − 1).If p > 1/2 the walk drifts right; if p < 1/2 it drifts left.Var(Sₙ) = 4npq.P(reach N before 0 | S₀ = k) = (1 − (q/p)^k) / (1 − (q/p)^N)
q/p = 0.52/0.48 ≈ 1.0833
(q/p)^10 ≈ 2.158, (q/p)^50 ≈ 60.34
P = (1 − 2.158) / (1 − 60.34) = −1.158 / −59.34 ≈ 0.0195.
A striking result: the simple symmetric random walk in one dimension is recurrent — it returns to the origin with probability 1. No matter how far it strays, it always comes back. In three or more dimensions, the walk has positive probability of wandering off to infinity and never returning (transient). The boundary is dimension 2, which is also recurrent but barely.
Do not confuse the expected position E[Sₙ] = n(2p−1) with the spread Var(Sₙ) = 4npq. For a symmetric walk (p = 1/2), the expected position is always 0, but the walk still spreads — the standard deviation grows as √n. "Expected to return to 0" does not mean "stays near 0."
The random walk has independent steps. But many real-world processes have a weaker structure: the future depends on the past, but only through the present. Weather tomorrow depends on weather today, not on weather three weeks ago. This is the Markov property.
A discrete-time process {Xₙ} with state space S satisfies the Markov property if for all n ≥ 0 and all states i, j, i₀, …, iₙ₋₁ in S:
P(Xₙ₊₁ = j | Xₙ = i, Xₙ₋₁ = iₙ₋₁, …, X₀ = i₀) = P(Xₙ₊₁ = j | Xₙ = i).
A process satisfying the Markov property is called a Markov chain. The transition probability pᵢⱼ = P(Xₙ₊₁ = j | Xₙ = i) gives the probability of moving from state i to state j in one step. For a time-homogeneous chain, these probabilities do not depend on n.
The Markov property is weaker than independence. In a Markov chain, X₀ and X₂ are not generally independent — knowing X₀ gives information about X₁, which gives information about X₂. The Markov property says only that given X₁, knowing X₀ adds nothing. Correlation across time is allowed; only long-range memory is excluded.
From W: p_WW = 0.90, p_WU = 0.07, p_WF = 0.03
From U: p_UW = 0.60, p_UU = 0.30, p_UF = 0.10
From F: p_FW = 0.00, p_FU = 0.40, p_FF = 0.60
When the state space S = {1, 2, …, k} is finite, all transition probabilities can be organized into a transition matrix P, where entry pᵢⱼ in row i, column j gives the probability of moving from state i to state j in one step. Every row must sum to 1.
P = | 0.8 0.2 |
| 0.5 0.5 |
Row 1 = Sunny, Row 2 = Rainy.
P² = | 0.74 0.26 |
| 0.65 0.35 |
P³ = | 0.722 0.278 |
| 0.695 0.305 |
The rows are converging — the chain is "forgetting" its starting state.
For a time-homogeneous Markov chain with transition matrix P, the probability of going from state i to state j in exactly n steps is the (i, j) entry of Pⁿ:
P(Xₙ = j | X₀ = i) = (Pⁿ)ᵢⱼ.
The state distribution after n steps is π⁽ⁿ⁾ = π⁽⁰⁾ Pⁿ, where π⁽⁰⁾ is the initial distribution row vector.
As n → ∞, the entries of Pⁿ often converge to limiting values. These represent the long-run fraction of time the chain spends in each state, regardless of starting state. Whether this happens depends on two structural properties.
| Property | Definition | Why It Matters |
|---|---|---|
| Irreducible | Every state can be reached from every other state. | Ensures the chain does not get trapped in a subset of states. |
| Aperiodic | No state has a period greater than 1. (Return is possible at consecutive times.) | Ensures probabilities converge rather than oscillate. |
| Absorbing state | A state i with pᵢᵢ = 1 — once entered, never left. | Absorbing chains require a different analysis (absorption probabilities). |
Let {Xₙ} be an irreducible, aperiodic Markov chain with finite state space. Then:
lim_{n→∞} p_{ij}^{(n)} = πⱼ for all states i and j,
where π = (π₁, π₂, …, πₖ) is the unique probability distribution satisfying πP = π and Σⱼ πⱼ = 1. The chain converges to π regardless of starting state.
The stationary distribution π satisfies πP = π: if the chain starts in distribution π, it remains there forever. To find π, solve the balance equations πP = π together with the normalization condition Σⱼ πⱼ = 1.
π_S = 0.8π_S + 0.5π_R
π_R = 0.2π_S + 0.5π_R
2.5π_R + π_R = 1 → π_R = 2/7 ≈ 0.286, π_S = 5/7 ≈ 0.714.
(5/7)(0.8) + (2/7)(0.5) = 4/7 + 1/7 = 5/7 = π_S. ✓
(5/7)(0.2) + (2/7)(0.5) = 1/7 + 1/7 = 2/7 = π_R. ✓
π_W = 0.90π_W + 0.60π_U + 0.00π_F → 0.10π_W = 0.60π_U → π_W = 6π_U
π_F = 0.03π_W + 0.10π_U + 0.60π_F → 0.40π_F = 0.28π_U → π_F = 0.70π_U
6π_U + π_U + 0.70π_U = 1 → 7.70π_U = 1 → π_U ≈ 0.1299.
π_W ≈ 0.779, π_U ≈ 0.130, π_F ≈ 0.091.
Mistake 1: Reading the stationary distribution directly from a row of P. A row gives transition probabilities from one state, not the long-run balance. Solve πP = π.
Mistake 2: Forgetting normalization. The equations πP = π alone do not uniquely determine π — one equation is redundant and must be replaced by Σⱼ πⱼ = 1.
The Poisson process is the continuous-time analogue of the Bernoulli process. Instead of checking for events at each integer time step, events can occur at any moment t ≥ 0, at a constant average rate λ, and what happens in non-overlapping intervals is independent.
A stochastic process {N(t) : t ≥ 0} is a Poisson process with rate λ > 0 if:
1. N(0) = 0.
2. Independent increments: changes over non-overlapping intervals are independent.
3. Stationary increments: the distribution of N(t+s) − N(t) depends only on s.
4. For small h: P(N(h) = 1) = λh + o(h) and P(N(h) ≥ 2) = o(h).
Under these conditions, N(t) − N(s) ~ Poisson(λt) for any interval of length t − s.
The number of events in any interval of length t follows a Poisson distribution:
P(N(t) = k) = e^{-λt}(λt)^k / k! for k = 0, 1, 2, …
E[N(t)] = λt, Var(N(t)) = λt.
The parameter λ is the rate: the expected number of events per unit time.
P(N(0.5) = 3) = e^{-2.5}(2.5)³ / 3! ≈ (0.0821)(15.625)/6 ≈ 0.2138.
E[N(2)] = λ · 2 = 5 × 2 = 10.
P(N(0.25) = 0) = e^{-1.25} ≈ 0.2865.
If N₁(t) and N₂(t) are independent Poisson processes with rates λ₁ and λ₂, their superposition N(t) = N₁(t) + N₂(t) is Poisson with rate λ₁ + λ₂. Conversely, if events from a Poisson process with rate λ are independently classified as Type 1 (probability p) or Type 2 (probability 1−p), the two types form independent Poisson processes with rates λp and λ(1−p).
The Poisson count and the waiting time between events are two views of the same process. The interarrival time T₁ is the time until the first event; T₂ the time between the first and second; and so on. A fundamental theorem connects these waiting times to the exponential distribution.
In a Poisson process with rate λ, the interarrival times T₁, T₂, T₃, … are independent and identically distributed Exponential(λ) random variables.
P(T₁ > t) = P(N(t) = 0) = e^{-λt}.
E[Tₖ] = 1/λ, Var(Tₖ) = 1/λ².
The time until the n-th event, Sₙ = T₁ + … + Tₙ, follows a Gamma(n, λ) distribution with E[Sₙ] = n/λ.
For an Exponential(λ) waiting time T:
P(T > s+t | T > s) = P(T > t) for all s, t > 0.
If you have already waited s units of time for the next event, the additional waiting time still has the same Exponential(λ) distribution. The distribution has no memory of the time already elapsed. This is the continuous-time analogue of the geometric distribution's memoryless property.
P(T > 1/12) = e^{-2 · (1/12)} = e^{-1/6} ≈ 0.8465.
E[S₁₀] = 10/λ = 10/3 ≈ 3.33 seconds.
P(N(4) ≥ 10) = 1 − Σₖ₌₀⁹ e^{-12}(12)^k/k! ≈ 0.7576.
These two facts are equivalent and can be used interchangeably: P(N(t) < n) = P(Sₙ > t). "Fewer than n events by time t" is the same event as "the n-th event occurs after time t." This duality lets you switch between the Poisson CDF and the Gamma CDF depending on which is easier to compute.
Let T be the lifetime of a component. The reliability function is R(t) = P(T > t) = 1 − F(t). The hazard rate h(t) = f(t)/R(t) gives the instantaneous failure rate at time t given survival to t.
| Distribution | Hazard Rate h(t) | Interpretation |
|---|---|---|
| Exponential(λ) | λ (constant) | Memoryless — equally likely to fail at any age. Models electronic components without wear. |
| Weibull (β > 1) | Increasing in t | Components wear out — more likely to fail with age. Standard in reliability engineering. |
| Weibull (β < 1) | Decreasing in t | Infant mortality — high early failure rate that decreases over time. |
R_series(t) = (e^{-0.01t})³ = e^{-0.03t}.
Mean system lifetime = 1/0.03 ≈ 33.3 hours.
R_parallel(t) = 1 − (1 − e^{-0.01t})³.
At t = 50: R_parallel(50) = 1 − (1 − e^{-0.5})³ ≈ 1 − (0.3935)³ ≈ 0.939.
The M/M/1 queue has Poisson arrivals (rate λ), exponential service (rate μ), and one server. The key parameter is the traffic intensity ρ = λ/μ. The queue is stable — waiting times stay bounded — if and only if ρ < 1.
Stationary distribution: πₙ = (1−ρ)ρⁿ for n = 0, 1, 2, … (geometric)
Expected number in system: E[L] = ρ/(1−ρ)
Expected number in queue: E[L_q] = ρ²/(1−ρ)
Little's Law: L = λW where W is the expected time in the system.
E[L] = ρ/(1−ρ) = (2/3)/(1/3) = 2 customers.
Correct: X₀ and X₂ are conditionally independent given X₁, not marginally independent. The Markov property restricts long-range memory, not correlation.
Correct: A row gives transition probabilities from one state, not the long-run distribution. Solve πP = π with normalization Σⱼ πⱼ = 1.
Correct: From π₁ = 2π₂ and π₁ + π₂ = 1, conclude π₂ = 1/3 and π₁ = 2/3. The balance equations alone never determine π uniquely.
Correct: Rate λ = 4 calls/hr means average waiting time = 1/λ = 1/4 hour = 15 minutes. Rate and mean waiting time are reciprocals.
Correct: By the memoryless property, P(T > s+t | T > s) = P(T > t). Additional waiting time has exactly the same Exponential distribution regardless of how long you have already waited.
Correct: Row i of P gives the outgoing transition probabilities from state i. The equation is πP = π (row vector π left-multiplied). Columns need not sum to 1.
Correct: First check irreducibility and aperiodicity. Chains with absorbing states are not irreducible. Compute absorption probabilities instead.
Correct: A stationary distribution always exists for a finite irreducible chain. But convergence to it requires aperiodicity as well. A periodic irreducible chain has a unique stationary distribution but does not converge to it.
Chapter 13 is an entry point into a vast landscape. The vocabulary established here — process, state space, Markov property, transition matrix, stationary distribution, Poisson arrivals, interarrival times — is the foundation for many directions of further study.
| Topic | What It Builds On | Where It Leads |
|---|---|---|
| Continuous-Time Markov Chains | Markov chains, Poisson process | Holding times in states are Exponential; described by a generator matrix Q rather than P. Used in M/M/1 and epidemic models. |
| Brownian Motion and Stochastic Calculus | Random walks, CLT | The continuous limit of the random walk. Itô's formula extends calculus to stochastic differential equations. Foundation for financial mathematics. |
| Martingales | Conditional expectation | Processes where E[Xₙ₊₁ | X₀, …, Xₙ] = Xₙ. Powerful tools for convergence theorems and stopping times. |
| Hidden Markov Models | Markov chains, conditional probability | Observed data are noisy functions of a hidden state. Viterbi and Baum-Welch algorithms. Used in speech recognition and bioinformatics. |
| MCMC | Stationary distributions, Bayesian inference | Design Markov chains whose stationary distribution is the target posterior. Metropolis-Hastings, Gibbs sampling. Workhorse of Bayesian computation. |
| Reinforcement Learning | Markov chains, expected value | Agent navigates a Markov Decision Process to maximize long-run reward. Q-learning and policy gradient methods. |
The central insight of this chapter is that randomness can be structured. A stochastic process is not chaos; it is uncertainty organized by rules. Those rules — the Markov property, independent increments, the Poisson rate — make processes mathematically tractable while remaining rich enough to model the real world. Students who have worked through this chapter can describe how uncertainty evolves, analyze long-run behavior, compute probabilities for random arrivals and waiting times, and connect the mathematics to applications across science and computing.
Each problem shows a student's work. Identify the error and write the correct solution.
Identify the error. Write and compute the correct probability.
Explain why this is wrong. Find the correct stationary distribution.
Identify the error and compute the correct system reliability at t = 50.
What step did the student omit? Write the correct stationary distribution.
Identify the probabilistic error. What is the correct additional expected waiting time?
Chapter 13 showed that probability is not only about single draws from a distribution — it is also the language of systems that evolve over time. Markov chains, Poisson processes, and random walks are structures that govern how uncertainty unfolds, step by step or moment by moment.
Chapter 14 closes the book by drawing all the threads together. The question is no longer "how do we model one phenomenon" but "how do we think about modeling itself." Chapter 14 covers model selection, assumption checking, quantifying uncertainty, decision-making under uncertainty, reproducibility, ethics in statistical practice, and communication of results. Stochastic process ideas reappear there — MCMC is a tool of Bayesian computation; simulation of Markov chains supports assumption checking; dynamic models appear in the capstone data analysis project. Students who have worked through Chapter 13 are prepared to engage with probability and statistics as a complete, unified system for reasoning about an uncertain world.