Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 63 ยท Math for Contests

Probability and Expected Value

Contest probability in Python: indicator variables, linearity of expectation, expected-value DP and equations, and printing exact answers as fractions modulo a prime.

Probability problems in contests are rarely about dice for their own sake. They ask for "the expected number of operations", "the probability that the process ends in state X", or "the expected score of a random strategy", and then ask you to print the answer as a fraction modulo 998244353. The underlying math is small: a few rules about expectation, a dynamic programming habit, and the modular inverse you already know.

You will learn the one rule that solves most of them (linearity of expectation), how to write expected values as DP over states, how to handle processes that loop back to themselves, and how to print exact answers modulo a prime. Everything is tested against exhaustive enumeration, so you can see that the formulas are right and not just plausible.

Expected value and indicator variables

The expected value of a random quantity X is the sum over outcomes of value * probability. The most useful fact about it is linearity:

E[X + Y] = E[X] + E[Y], always, even when X and Y depend on each other.

That fact turns hard counting into easy bookkeeping. Write the total as a sum of simple 0/1 indicator variables, one per thing that could happen. The expectation of an indicator is just the probability of its event, so E[total] is the sum of those probabilities. You never need the joint distribution.

Example: shuffle n cards and count the cards that land in their original position. Let I_i be 1 if card i stays put. Then P(I_i = 1) = 1/n for each card, so the expected count is n * (1/n) = 1, whatever n is. The counts are strongly dependent (if n - 1 cards are fixed, so is the last), and linearity does not care.

Python Linearity of expectation, verified by enumeration

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.

The pattern for these problems is always the same: name the events, find each probability, add. When a statement says "expected number of pairs / positions / elements such that...", reach for indicators first.

flowchart LR
    A["Count something random"] --> B["Split into 0/1 indicators"]
    B --> C["P(indicator) for each"]
    C --> D["Add the probabilities"]
    D --> E["That is E[count]"]

Linearity: the answer is a sum of probabilities, no joint distribution needed.

Expected value as a DP

When the process has stages, define E[state] as the expected remaining cost from that state and write one equation per state. If every transition goes to a "later" state, you can fill the table backward, exactly like a normal DP.

Example: roll a fair die repeatedly and add the results. What is the expected number of rolls until the running sum reaches at least target? Let E[s] be the expected rolls remaining when the sum is s. Then E[s] = 0 for s >= target, and otherwise E[s] = 1 + (E[s+1] + ... + E[s+6]) / 6. Compute s from target - 1 down to 0.

Use Fraction while exploring, so you see exact values and can compare with a formula. Switch to modular arithmetic only for the final submission.

Processes that loop back

Some states can return to themselves or to an earlier state, so there is no clean order. Then you keep the unknowns as variables and solve the equation.

Example: flip a fair coin until two heads in a row appear. State 0 means "no useful progress", state 1 means "the last flip was heads". Then

  • E0 = 1 + E1/2 + E0/2 (tails keeps you in state 0)
  • E1 = 1 + 0/2 + E0/2 (heads ends, tails sends you back to state 0)

Substituting E1 into the first equation and solving gives E0 = 6. For a bigger system, eliminate variables one at a time, or run a few thousand rounds of "value iteration" to check a closed form. When the structure is a chain with a self-loop, the standard trick is to move the self-loop term to the left: E = 1 + p*E + (rest) becomes E = (1 + rest) / (1 - p).

Python Expected-value DP and a self-loop equation

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.

The coupon collector formula is worth memorizing: to see all n types, when each draw is uniform, you wait n/n + n/(n-1) + ... + n/1 = n * H_n draws on average. The argument is again linearity: after you hold k types, the next new one takes n/(n-k) draws on average, and the stages simply add up.

Probabilities modulo a prime

Contest answers are usually "print p * q^-1 mod 998244353", where the true answer is the reduced fraction p/q. This is safe as long as q is not divisible by the modulus. The rules:

  • A probability like 1/6 becomes pow(6, -1, MOD).
  • Add and multiply probabilities with ordinary modular operations.
  • Never compare modular probabilities with < or >; the residues carry no ordering. If the problem needs a comparison, you must use exact fractions or floats.
  • Do not mix floats into a modular computation. Convert every rational to its residue as early as possible.

Precompute inverses of small integers (1 to n) in a list if you divide by them inside a loop; a call to pow per division is slower, and a table of inverses is a standard part of any template (see Modular Arithmetic).

Python Exact fractions and the same answer modulo a prime

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.

Multiplying the residue back by the denominator is a cheap way to debug: if r * q % MOD does not give p, the inverse was applied wrong.

A workflow for probability problems

  1. Decide whether the answer is a probability or an expectation. Expectations are usually easier because of linearity.
  2. If the quantity is a count, try indicators first. If it is a time or cost, define E[state].
  3. Check the structure of the states: if transitions only move forward, fill a table backward; if there are loops, write equations and solve.
  4. Test the formula on tiny inputs by full enumeration or fractions before converting to modular form.
  5. Convert to modular arithmetic last, and verify that the denominator never hits a multiple of the modulus.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which statement about linearity of expectation is true?

    Linearity of expectation needs no independence. That is what makes indicator variables so powerful. The product rule, by contrast, does need independence.
  2. 2. What is the expected number of fixed points of a uniformly random permutation of n elements?

    Each position is a fixed point with probability 1/n, so by linearity the expected count is n * (1/n) = 1 for every n.
  3. 3. A process stays in state 0 with probability p and otherwise moves on; each step costs 1. If the rest costs R after leaving, what does E0 = 1 + p*E0 + (1-p)*R solve to?

    Move p*E0 to the left: E0 * (1 - p) = 1 + (1-p)*R, then divide by (1 - p). Equivalently E0 = 1/(1-p) + R.
  4. 4. Why should you avoid comparing two probabilities that are stored modulo 998244353?

    A residue is just a representative of an equivalence class, so a larger residue does not mean a larger probability. Compare with exact fractions if the problem needs it.

Summary

  • Expectation is linear: split counts into 0/1 indicators and add their probabilities.
  • Expected cost over stages is a DP: E[state] = cost + sum of probability * E[next], filled in dependency order.
  • Self-loops and cycles give equations; solve for the unknowns, moving the loop term to the left.
  • The coupon collector needs n * H_n draws on average.
  • Print answers as p * q^-1 mod M, test with Fraction first, and never compare residues.

Next: Bit Tricks and XOR Problems