Probability and expected value calculations

A probability problem asks for the likelihood of an event; an expected-value problem asks for the average outcome if the same random process ran many times. Linearity of expectation is what makes many of these problems tractable: the expected value of a sum is the sum of the expected values, even when the individual quantities being summed depend on each other.

Why this matters in contests

A contest problem involving randomness usually wants an exact fraction, or a decimal rounded to a stated precision. Python's floating-point arithmetic is precise enough for almost every such problem, as long as the algorithm avoids rounding until the very last step.

The most useful simplification is almost always the same one: recognize that a complicated total is a sum of several simpler pieces, and that the expected value of the sum is the sum of each piece's own expected value, whether or not those pieces influence each other.

Linearity of expectation

If a quantity X is the sum of several random variables, X = X1 + X2 + ... + Xn, then E[X] = E[X1] + E[X2] + ... + E[Xn], no matter how the individual Xi depend on each other. This holds even when knowing the value of X1 changes what you would guess for X2.

Take a shop where each customer independently orders a dish with some probability. The expected total revenue is the sum, over every customer, of that customer's own expected revenue, which is the probability that customer orders multiplied by the dish's price. Linearity of expectation holds here even if one customer's order somehow changed the probability of the next customer's order, since it never actually requires the terms to be independent.

A worked example, first with independence, then without

Five customers each have a 60% chance of ordering a dish that costs 10.

1import sys2
3
4def main() -> None:5    data = sys.stdin.read().split()6    n = int(data[0])7    prob_order = float(data[1])8    cost = float(data[2])9
10    # By linearity of expectation, the expected total is just n times the11    # expected revenue from a single customer, even though a real shop's12    # customers might influence each other's choices.13    expected_per_customer = prob_order * cost14    expected_total = n * expected_per_customer15
16    print(f"{expected_total:.1f}")17
18
19if __name__ == "__main__":20    main()

5 0.6 10

30.0

Each customer's expected revenue is 0.6 * 10 = 6, and with five independent customers, the expected total is 5 * 6 = 30, matching the program's output.

Now suppose the first customer's choice affects the second: if the first orders, the second orders with probability 0.7; if the first does not order, the second orders with probability 0.4. The first customer's expected revenue is unchanged, still 0.6 * 10 = 6. The second customer's expected revenue has to account for both of the first customer's outcomes: with probability 0.6, the first customer ordered and the second orders with probability 0.7, contributing 0.6 * 0.7 * 10 = 4.2; with probability 0.4, the first customer did not order and the second orders with probability 0.4, contributing 0.4 * 0.4 * 10 = 1.6. The second customer's expected revenue is 4.2 + 1.6 = 5.8, and the total expected revenue across both customers is 6 + 5.8 = 11.8, even though the two customers are no longer independent.

Computing probabilities backwards

Some problems are much easier to reason about starting from the end state and working backwards, rather than tracking every path forward from the start.

Take a coin that lands heads with probability p. How many flips, on average, until the first heads? Reasoning forward means summing over every possible number of flips before the first heads, weighted by its probability, an infinite sum. Reasoning backward is shorter: let E be the expected number of flips remaining, starting fresh. One flip happens for certain. With probability p, that flip was heads, and you are done. With probability 1 - p, that flip was tails, and you are back to exactly the same situation you started in, still needing E more flips on average. That gives the equation E = 1 + (1 - p) * E, which solves to E = 1 / p. With p = 0.25, the expected number of flips is 1 / 0.25 = 4. Nothing about this argument required tracking how many flips had already happened; it only needed the observation that "waiting for heads" looks identical no matter how many tails came before it.

This pattern, defining a state's answer in terms of the states it can lead to, and solving from a known base case backward, extends directly into dynamic programming: whenever the forward branching is complex but the backward recurrence collapses to a small, self-referential equation, work backward instead of enumerating every forward path.

Common mistakes

Multiplying probabilities without conditioning correctly is the most common error. If event A's probability depends on event B, the right computation is P(A) = P(A | B) * P(B) + P(A | not B) * P(not B), summing over every case for B; skipping a case, or conditioning on the wrong event, gives an answer that looks plausible but is wrong.

Rounding intermediate results is another. Floating-point error accumulates across many operations, so keep full precision until the final print statement, and only round there.

A third mistake is missing an opportunity to apply linearity of expectation. Any time the target quantity is a sum, even a sum of dependent pieces, decomposing it into E[X1] + E[X2] + ... + E[Xn] is worth trying first, since it often turns an intractable joint computation into several small, independent-looking ones.

Why this works, and the cost

Linearity of expectation is a property of expectation as a mathematical operation, not a coincidence that depends on the variables being independent; it holds unconditionally for any finite sum of random variables. The work in applying it is entirely in finding the right decomposition, after which each piece is usually a short, direct computation.

Working backwards is not a different kind of correctness, just a different order of computation. It pays off exactly when the number of paths forward from the start would be enormous, but the recurrence relating a state to what follows it stays small and self-contained.

Floating-point precision

Print a floating-point answer with the precision the problem statement asks for, and read that requirement carefully: some problems want absolute error within 1e-6, others want relative error within 1e-9, and those are different bars to clear. f"{value:.9f}" prints nine digits after the decimal point; format strings using the older % syntax work too, but ruff and this course's style both prefer the newer f-string form.