All tracks

Discrete Stochastic Processes

Markov chains, random walks, martingales, optimal stopping.

Prerequisites: Probability complete

0 of 10 lessons completed

Start the first lesson
  1. 1Random WalksA drunk on a 100 m bridge: why spread grows like √n, and why twice as far takes four times as long.
  2. 2Markov ChainsA frog that forgets where it has been: one equation per state, and the chain solves itself.
  3. 3Conditional Expectation and the Tower PropertySeeing the first die rules out 30 of 36 worlds and moves the expected sum away from 7, yet averaged over every face you might see, the forecast is still 7.
  4. 4Martingales and Optional StoppingThe fair game that predicts the future, and why no stopping rule can beat it.
  5. 5The Coupon CollectorHow many draws to collect all n types? Each new type is its own geometric wait.
  6. 6HTH or HHT? Coin Patterns and Penney's GameTwo three-flip patterns with the same odds take different times to appear, and in a head-to-head race HHT beats HTH two times out of three.
  7. 7The Reflection Principle and the Ballot ProblemA candidate who wins 52 to 48 has only a 4% chance of leading all the way through the count, and reflecting paths at their first touch of zero shows why.
  8. 8Optimal Stopping and the 37% RuleInterview 100 candidates you can't call back: skip the first 37, take the next one who beats everyone before them, and you land the very best about 37% of the time.
  9. 9Betting Systems and the Kelly CriterionDoubling after every loss wins a dollar almost every time and loses everything once in a while; when you do have an edge, Kelly tells you what fraction of your bankroll to bet.
  10. 10The Poisson ProcessArrivals at random: Poisson counts, exponential gaps that forget the past, and streams you merge by adding rates and split by scaling them.

Practice

The problem bank has 23 interview problems on this material, with hints and full solutions.

Practice 23 related problems