Probability Ladder¶
This ladder covers contest probability where:
- the randomness is in the statement
- the state space is finite or bounded
- the answer is one exact probability or expected value
Use it when a problem asks you to analyze a random process exactly, not to design a randomized algorithm.
Recommended Route¶
- bounded-sum distribution DP
- expectation from a known PMF
- expectation through linearity / independence
- harder process models only after the first three feel routine
Anchor Problems¶
- Dice Probability: the repo's exact first route, one PMF DP over repeated fair-die throws
Retrieval / Build Path¶
- topic page -> Probability
- hot sheet -> Probability hot sheet
- starter -> probability-distribution-dp.cpp
Compare Points¶
- Candy Lottery: expectation from a derived distribution of the maximum
- Moving Robots: repeated transition probabilities plus independence/complements
- Randomized Algorithms: anti-cue when the randomness belongs to the algorithm rather than the statement
Exit Criteria¶
You are ready to leave this ladder when you can:
- decide whether to build a PMF or compute expectation directly
- use linearity of expectation without needing the full joint process
- recognize when simulation is the wrong instinct
- separate probability-in-the-problem from randomized-algorithm analysis