SyntaxPilot
Courses/Competitive Programming/Lesson 40
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 40 of 90

DP 9: probability and expected-value DP

queued

These are the notes for Competitive Programming episode 40, part nine of the dynamic programming section. At the village mela, Rohan's dice game has cells 0 … n: you roll a fair die and move forward, but a roll that would pass cell n is wasted. An original problem, Exact Finish, asks for the expected (average) number of rolls, with an error of at most 10^−6. Simulating a million games is close but wrong in the 4th decimal, and far too slow for n = 10^6. The expected value splits into one roll plus the average of the possible futures: E[i] = 1 + (1/6) Σ E[next], filled from the finish backwards. The trap: a wasted roll leads back to the same cell, so E[i] depends on itself. Recursion then never ends (SIGSEGV) and a plain loop uses E[i] = 0. A line of algebra solves it: E[i] = (6 + sum) / (6 − stay). Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook

Rohan charges per roll at his mela stall. Players start at cell 0 and must land exactly on cell n; a roll that overshoots is wasted and the player stays. Players want to know how many rolls a game takes on average, so they know what it will cost.

Problem Q · Exact Finish

(Written for this course, in the style of an AtCoder Beginner Contest problem.)

Cells 0 … n; start at 0. Each turn roll a fair six-sided die showing d: if i + d ≤ n move to i + d, otherwise stay at i. Print the expected number of rolls until you stand on cell n.

  • Input: n (1 ≤ n ≤ 10^6).
  • Output: the expected number of rolls; an absolute error of at most 10^−6 is accepted.
Input Output
1 6.000000
8 7.166667
10 7.587963
1000000 285719.047619

Expected value = the average over infinitely many games. If an outcome x happens with probability p(x), the expected value is Σ p(x) · x.

Attempt 1: simulate a million games (not exact, and TLE)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    mt19937 rng(40);
    int games = 1000000;
    ll rolls = 0;
    for (int g = 0; g < games; g++) {      // play a million games
        int at = 0;
        while (at < n) {
            int d = rng() % 6 + 1;
            if (at + d <= n) at += d;       // overshoot: stay
            rolls++;
        }
    }
    printf("%.6f\n", (double)rolls / games);
    return 0;
}

n = 10 prints 7.587807, but the exact answer is 7.587963: wrong in the 4th decimal (an error of 1.6 · 10^−4, far above 10^−6). A simulation's error shrinks like 1/√games, so a million games give about three correct digits. For n = 10^6 each game is about 2.9 · 10^5 rolls: Time Limit Exceeded.

Step 1: one roll plus the rest

Like a bus ride (time home = this stop + time from the next stop), the rolls needed from cell i are one roll now plus the average of the six equally likely futures:

E[i] = 1 + (1/6) · Σ over d = 1 … 6 of E[next(i, d)], next(i, d) = i + d if i + d ≤ n, else i

Base: E[n] = 0 (finished). Every move goes forward, so fill from the finish backwards. This uses linearity of expectation (episode 28): the expectation of "1 + rolls from the next cell" is 1 + the average of the next cells' expectations.

The self-loop trap

Near the end some faces are wasted, so next(i, d) = i: E[i] appears on both sides. On a track of 8, cell 7 moves only on a 1:

E[7] = 1 + (1/6) · (E[8] + 5 · E[7])

A dependency that points back at itself is a self-loop: there is no smaller state to compute first.

Recursion straight from the formula (infinite recursion)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n;
vector<double> memo;
vector<bool> seen;

double E(int i) {                         // expected rolls from cell i
    if (i == n) return 0;
    if (seen[i]) return memo[i];
    double sum = 0;
    for (int d = 1; d <= 6; d++)
        sum += E(i + d <= n ? i + d : i);   // overshoot: stay at i
    seen[i] = true;
    return memo[i] = 1 + sum / 6;
}

int main() {
    cin >> n;
    memo.assign(n + 1, 0);
    seen.assign(n + 1, false);
    printf("%.6f\n", E(0));
    return 0;
}

n = 8: Runtime Error (SIGSEGV). E(7) rolls a 2 (wasted), calls E(7) again before it is marked as seen, and so on until the stack is exhausted.

A backwards loop that uses E[i] = 0 for itself (wrong)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    vector<double> E(n + 1, 0);   // E[n] = 0
    for (int i = n - 1; i >= 0; i--) {
        double sum = 0;
        for (int d = 1; d <= 6; d++)
            sum += E[i + d <= n ? i + d : i];   // E[i] is still 0 here!
        E[i] = 1 + sum / 6;
    }
    printf("%.6f\n", E[0]);
    return 0;
}

n = 8 prints 2.775231 (expected 7.166667): every wasted roll was treated as "zero more rolls", as if the game had ended.

Step 2: solve for E[i]

Let stay be the number of faces that overshoot and sum the total of E over the faces that move. Then

E[i] = 1 + (sum + stay · E[i]) / 6 6 · E[i] − stay · E[i] = 6 + sum E[i] = (6 + sum) / (6 − stay)

stay ≤ 5 (a roll of 1 always moves when i < n), so we never divide by zero, and E[i] now depends only on cells after i.

Trace for n = 8:

cell 0 1 2 3 4 5 6 7 8
wasted faces 0 0 0 1 2 3 4 5 –
E 43/6 ≈ 7.166667 7 6 6 6 6 6 6 0

Cells 2 … 7 all give exactly 6: from each, exactly one face lands on 8 and the other moves keep you within six cells of the end. Cell 1: (6 + 6 · 6) / 6 = 7. Cell 0: (6 + 7 + 5 · 6) / 6 = 43/6.

The accepted solution

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    vector<double> E(n + 1, 0);           // E[n] = 0: already finished
    for (int i = n - 1; i >= 0; i--) {     // from the finish backwards
        double sum = 0;
        int stay = 0;                        // rolls that overshoot
        for (int d = 1; d <= 6; d++) {
            if (i + d <= n) sum += E[i + d];
            else stay++;
        }
        // E[i] = 1 + (sum + stay * E[i]) / 6   →   solve for E[i]
        E[i] = (6 + sum) / (6 - stay);
    }
    printf("%.6f\n", E[0]);
    return 0;
}
Input Output
8 7.166667
10 7.587963
1 6.000000
1000000 285719.047619 (instant)

For large n the answer is close to n / 3.5 (the average roll is 3.5) plus a small end correction: 10^6 / 3.5 ≈ 285714.3.

Checking doubles: compare with a tolerance

A stress test with doubles cannot demand an exact match. Here the formula is compared with 2 · 10^6 simulated games for boards 1 … 8:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    // the formula against a long simulation, for small boards
    mt19937 rng(7);
    for (int n = 1; n <= 8; n++) {
        vector<double> E(n + 1, 0);
        for (int i = n - 1; i >= 0; i--) {
            double sum = 0;
            int stay = 0;
            for (int d = 1; d <= 6; d++) { if (i + d <= n) sum += E[i + d]; else stay++; }
            E[i] = (6 + sum) / (6 - stay);
        }
        ll rolls = 0;
        int games = 2000000;
        for (int g = 0; g < games; g++)
            for (int at = 0; at < n; rolls++) {
                int d = rng() % 6 + 1;
                if (at + d <= n) at += d;
            }
        printf("n=%d  dp %.4f  simulated %.4f\n", n, E[0], (double)rolls / games);
    }
}

Output:

n=1  dp 6.0000  simulated 5.9946
n=2  dp 6.0000  simulated 6.0006
n=3  dp 6.0000  simulated 6.0037
n=4  dp 6.0000  simulated 5.9928
n=5  dp 6.0000  simulated 6.0026
n=6  dp 6.0000  simulated 5.9940
n=7  dp 7.0000  simulated 6.9992
n=8  dp 7.1667  simulated 7.1625

They agree to about two decimals, which is all a simulation can give; the DP gives every digit.

A second question: forward probability DP

Cell k has a chai stall. What is the probability that you ever stand on cell k? Expected values flow backwards from the finish; probabilities flow forwards from the start (p[0] = 1). Wasted rolls only repeat the turn, so when you finally move, each of the moves = min(6, n − i) real moves is equally likely:

p[i + d] += p[i] / moves for d = 1 … moves

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n, k;
    cin >> n >> k;
    vector<double> p(n + 1, 0);            // p[i] = chance to ever stand on cell i
    p[0] = 1;
    for (int i = 0; i < n; i++) {
        int moves = min(6, n - i);           // rolls that really move
        for (int d = 1; d <= moves; d++)
            p[i + d] += p[i] / moves;        // wasted rolls just repeat: each real move is equally likely
    }
    printf("%.6f\n", p[k]);
    return 0;
}

10 7 prints 0.296489. Far from the start the chance tends to 1 / 3.5 ≈ 0.2857, because you land on about one cell in every 3.5.

Complexity vs the constraints

Approach Time Verdict
simulate 10^6 games ≈ 3 · 10^11 rolls at n = 10^6 TLE, and only ~3 digits
recursion as written never ends Runtime Error (SIGSEGV)
loop with E[i] = 0 for itself O(6n) wrong (2.775231)
solved backwards DP O(6n) = 6 · 10^6 accepted, exact

Common mistakes (and the real outputs)

Mistake What you see Why Fix
simulate and average 7.587807 (exact 7.587963) random error ~1/√games compute the expectation
E(i) calls E(i) on a wasted roll Runtime Error (SIGSEGV) infinite recursion solve for E[i] first
E[i] = 0 inside its own formula 2.775231 (expected 7.166667) the self term is not known yet E[i] = (6 + sum) / (6 − stay)
printf("%.2f") or plain cout 7.17 / 7.16667 too few digits printf("%.6f") or cout << fixed << setprecision(6)
int division 1 / 6 0 integer division 1.0 / 6
forward DP for an expectation with a fixed end hard to set up expectations depend on the future expectations backwards, probabilities forwards

Mini project

Build a "board game analyser": a track of n cells with snakes and ladders (jump[i] = where you end up after landing on i). Compute the expected number of rolls to finish with the backwards DP when all jumps go forward. When a snake goes back, the equations form a system with cycles: solve it with Gaussian elimination for n ≤ 100, and compare with a simulation of 10^6 games.

Practice

  1. Add snakes: landing on cell s sends you back to t < s.

    Answer Now E[s] = E[t] and the dependencies have cycles bigger than one cell, so the backwards loop no longer works. For small n write the n linear equations and solve them with Gaussian elimination (O(n³)); with special structure (few snakes) iterate value updates until they converge.

  2. A die with faces 1 … k.

    Answer E[i] = (k + Σ_{valid d} E[i + d]) / (k − stay), with a sliding-window sum to keep it O(n) for large k. With k = 2 and n = 1: <b>2</b> (wait for a 1).

  3. The answer modulo 998244353 (as P · Q^−1).

    Answer Replace division by multiplication with a modular inverse (episode 22): E[i] = (6 + sum) · inv(6 − stay). For n = 1 the answer is <b>6</b>; for n = 8 it is 43 · inv(6) mod 998244353 = <b>166374066</b>.

  4. The probability of finishing within m rolls.

    Answer Forward DP over (rolls used, cell): P[r + 1][next] += P[r][i] / 6, wasted rolls staying at i. The answer is P[m][n] (cell n absorbs). For n = 1, m = 1: <b>1/6 ≈ 0.166667</b>.

Quick quiz

You toss a fair coin. Heads: you are done. Tails: the toss is wasted and you toss again. How many tosses on average?

A) 1 · B) 1.5 · C) 2 · D) it never ends

Answer

C. E = 1 + (1/2) · 0 + (1/2) · E, so E/2 = 1 and E = 2. The same self-loop trick.

Interview questions

  1. What is an expected value? The probability-weighted average of the outcomes, Σ p(x) · x; the long-run average over many trials.
  2. Why compute expectations backwards? E at a state is defined by the states after it; the end state has a known value (0 more steps).
  3. What is the self-loop trick? When E[i] depends on itself with coefficient c/k, move that term to the left: E[i] · (1 − c/k) = rest, then divide.
  4. When do you use forward probability DP? For "probability of reaching/visiting a state": start with probability 1 at the start and push it along the transitions.
  5. How do you print doubles for a 10^−6 tolerance? printf("%.6f") or cout << fixed << setprecision(6) (or more digits; never the default 6 significant digits).
  6. Why not simulate? Monte Carlo error falls like 1/√trials: 10^12 games for 6 digits.

Glossary

Term Meaning Example
Probability How often an outcome happens, from 0 to 1 a die shows 6: 1/6
Expected value The probability-weighted average outcome E[0] = 7.166667 rolls
Linearity of expectation E[a + b] = E[a] + E[b] 1 roll + E[next]
Expected-value DP DP whose states store expectations, usually filled backwards E[i]
Probability DP DP whose states store probabilities, usually pushed forwards p[i]
Self-loop A state whose formula contains itself E[7] uses E[7]
Monte Carlo simulation Estimating by playing many random games 7.587807
Absolute error |your answer − true answer| ≤ 10^−6
Modular inverse x with a · x ≡ 1 (mod p), used to divide mod p inv(6)
setprecision / %.6f Print a fixed number of decimals 7.166667

Summary

  • Simulation is approximate (~3 digits) and slow; compute the expectation exactly.
  • E[i] = 1 + average of E over the next states; fill backwards from E[end] = 0.
  • A wasted roll is a self-loop: recursion never ends, a loop with E[i] = 0 is wrong. Move the self term to the left: E[i] = (6 + sum) / (6 − stay).
  • Probabilities flow forwards from p[start] = 1.
  • Print enough digits (%.6f). O(6n) for n = 10^6.
  • Real bugs: SIGSEGV from the self-loop, 2.775231 from E[i] = 0, 7.587807 from simulation.

Solutions in C++, Java and Python

Problem Q · Exact Finish

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    vector<double> E(n + 1, 0);           // E[n] = 0: already finished
    for (int i = n - 1; i >= 0; i--) {     // from the finish backwards
        double sum = 0;
        int stay = 0;                        // rolls that overshoot
        for (int d = 1; d <= 6; d++) {
            if (i + d <= n) sum += E[i + d];
            else stay++;
        }
        // E[i] = 1 + (sum + stay * E[i]) / 6   →   solve for E[i]
        E[i] = (6 + sum) / (6 - stay);
    }
    printf("%.6f\n", E[0]);
    return 0;
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int n = new Scanner(System.in).nextInt();
        double[] E = new double[n + 1];              // E[n] = 0
        for (int i = n - 1; i >= 0; i--) {           // from the finish backwards
            double sum = 0;
            int stay = 0;                            // rolls that overshoot
            for (int d = 1; d <= 6; d++) {
                if (i + d <= n) sum += E[i + d];
                else stay++;
            }
            E[i] = (6 + sum) / (6 - stay);           // solved for E[i]
        }
        System.out.printf("%.6f%n", E[0]);
    }
}

Python (6 · 10^6 steps take a few seconds in Python; fine for the samples)

def main():
    n = int(input())
    E = [0.0] * (n + 1)                  # E[n] = 0
    for i in range(n - 1, -1, -1):       # from the finish backwards
        s, stay = 0.0, 0
        for d in range(1, 7):
            if i + d <= n:
                s += E[i + d]
            else:
                stay += 1
        E[i] = (6 + s) / (6 - stay)      # solved for E[i]
    print(f"{E[0]:.6f}")

main()

All three print 6.000000, 7.166667, 7.587963 and 285719.047619 for n = 1, 8, 10 and 10^6.

Next episode: DP optimisation 1: monotonic queue and prefix-min tricks (a sliding-window minimum inside a DP).