Skip to content
Tutorials Center
My learning

Topics

Lesson 33 of 46 ยท Stochastic Models and Simulation

Random walks and Markov chains

Model step-by-step randomness: random walks spread like the square root of time, gambler's ruin has a neat formula, and Markov chains settle into a long-run distribution.

Many random processes are built from simple steps. A drunk person staggers left or right. A gambler wins or loses one coin at a time. Tomorrow's weather depends on today's. Each step is random, yet the long-run behaviour follows clean laws. In this lesson you will meet two classical models: the random walk and the Markov chain, and use simulation to check the formulas.

Three circles labelled Sunny, Cloudy and Rainy joined by arrows labelled with transition probabilities, next to the transition matrix.
A Markov chain: each arrow is the probability of moving from one state to another in one step. The arrows leaving a state add to 1.

What you will learn

  • Why a random walk's spread grows like โˆšn, not like n.
  • How to compute and simulate gambler's ruin probabilities.
  • How to write a Markov chain as a transition matrix and find its long-run distribution.
  • How to check a formula by simulating the process.

Key terms

Random walk: a path built from independent random steps, such as ยฑ1 with equal probability.

Gambler's ruin: the problem of whether a gambler with a finite fortune reaches a target before going broke.

Markov property: the next state depends only on the present state, not on the past.

Stationary distribution: a probability vector ฯ€ with ฯ€ยทP = ฯ€; the chain's long-run fractions of time in each state.

Random walks

Start at 0. Each second, move +1 or โˆ’1 with equal probability. After n steps the position is the sum of n independent steps. Each step has mean 0 and variance 1, and variances of independent quantities add, so the position has mean 0 and variance n. Its standard deviation is โˆšn.

So after 100 steps a typical walker is about 10 units from the start, not 100. After 10,000 steps, about 100. Randomness spreads out slowly, like the square root of time. This โˆšn law is behind diffusion (a drop of dye spreading in water), measurement noise averaging out, and the 1/โˆšN rule from the Monte Carlo lesson.

Gambler's ruin

You start with k coins and play a game that wins one coin with probability p and loses one with probability q = 1 โˆ’ p. You stop when you reach N coins (success) or 0 (ruin). The probability of reaching N is

  • if p = 0.5: k/N
  • if p โ‰  0.5: (1 โˆ’ (q/p)^k) / (1 โˆ’ (q/p)^N)

With k = 3, N = 10 and a fair game, you succeed with probability 0.3. Even a tiny disadvantage hurts a lot over long games: with p = 0.48 the success probability falls noticeably below 0.3 (you will compute it below). The casino does not need big edges, only many rounds.

Python Spread of a random walk and gambler's ruin

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Markov chains

Suppose the weather each day is Sunny, Cloudy or Rainy, and the chance of tomorrow's weather depends only on today's. The transition matrix P collects those chances; row i is "today is state i", column j is "tomorrow is state j":

Today \ Tomorrow Sunny Cloudy Rainy
Sunny 0.7 0.2 0.1
Cloudy 0.3 0.4 0.3
Rainy 0.2 0.4 0.4

Every row sums to 1. If ฯ€ is today's probability vector (as a row), tomorrow's is ฯ€ยทP, and the day after is ฯ€ยทPยฒ. Remarkably, for chains like this one, the rows of Pโฟ all converge to the same vector, no matter where you start. That limit is the stationary distribution, the solution of ฯ€ยทP = ฯ€ with ฮฃฯ€ = 1. It tells you the long-run fraction of sunny, cloudy and rainy days.

Another useful fact: the number of consecutive days a chain stays in a state with self-transition probability a is geometric, with mean 1/(1 โˆ’ a). A sunny spell lasts 1/(1 โˆ’ 0.7) = 3.33 days on average.

Python Long-run weather: three ways

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Common misconceptions

"After a run of losses, a win is due." Each step of a random walk is independent. The walk has no memory, and nothing is "due".

"A fair game means you will end up even." In a fair game the average gain is zero, but the spread of results grows like โˆšn, and gambler's ruin shows you can still go broke.

"The Markov property means the past is irrelevant." It means the past matters only through the present state. If your model needs yesterday's weather to predict tomorrow, define the state as the last two days.

Simulating a game with a hidden advantage

The last demo is a small exploration: change p and watch the proportion of successful gamblers. Because the plot uses the exact formula, it also shows how a 2 percent edge compounds with the target size.

Python Ruin probability against the odds

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A symmetric random walk takes 400 steps. About how far from the start is a typical walker?

    The standard deviation of the position is sqrt(400) = 20.
  2. 2. In a fair game you start with 3 coins and stop at 10 or 0. What is the chance of reaching 10?

    For p = 0.5 the success probability is k/N = 3/10.
  3. 3. What does the Markov property say?

    Given the present, the past does not add information about the next step.
  4. 4. The rows of a transition matrix must:

    Each row is a probability distribution over tomorrow's state.
  5. 5. A state has self-transition probability 0.8. How long does a stay in it last on average?

    The stay is geometric with mean 1/(1 - 0.8) = 5.

Summary

  • A random walk's spread grows like โˆšn.
  • Gambler's ruin: k/N for a fair game, a geometric formula otherwise; small edges compound.
  • A Markov chain is a transition matrix; rows of Pโฟ converge to the stationary distribution ฯ€ = ฯ€P.
  • Simulation and formulas should agree; use one to check the other.

Next: Queue simulation