Expected value is a fundamental concept in probability theory and statistics, used to describe the average or central tendency of data. In computer algorithm competitions, expected value algorithms are considered medium to advanced level, playing a crucial role in programming. In recent years, problems involving expectations and expectation dynamic programming have frequently appeared in international algorithm competitions such as CSP/USACO. This article will detail the application of expected value in algorithm design.
To lower the reading threshold, this article provides numerous examples to help readers understand the definition of expectation and its practical applications. At the end, relevant algorithm practice problems are also provided.
Basic Concepts of Random Variables
Before understanding expectation, it is essential to understand the definition of a random variable.
A random variable is a function that maps each possible outcome of a random experiment to a numerical value. A random variable can be seen as a mathematical representation of a random phenomenon.
E.g. 1 Tossing a Coin
Take tossing a coin as an example:
- There are two experimental outcomes: heads (H), tails (T).
- Random variable X: defined as heads worth 1, tails worth 0.
E.g. 2 Rolling a Die
When rolling a die:
- There are six experimental outcomes: 1, 2, 3, 4, 5, 6.
- Random variable Y: defined as the value of the rolled number.
Basic Concepts of Expected Value
The textbook definition of expectation is as follows:
The expected value is the weighted average of the values of a random variable, with weights being the probabilities of the corresponding values.
A more intuitive explanation is: the expected value represents the average value of a random variable over a large number of repeated experiments, describing the central tendency of a random phenomenon.
E.g. 3 Exam Scoring
Assume an exam has five multiple-choice questions, with the following scoring rules:
- Correct answer gives 4 points.
- Incorrect answer deducts 1 point.
- No answer gives no points.
If a student randomly selects answers, the probability for each question is:
- Probability of answering correctly: 1/4.
- Probability of answering incorrectly: 3/4.
Then the expected score per question is:
$$E(X) = 4\times \dfrac{1}{4} + (-1) \times \dfrac{3}{4} = 1 - 0.75 = 0.25$$
This means that the long-term average score for random answers is 0.25 points per question.
E.g. 4 Probability Game I
There is a dice game where if you roll a 6, you get 10 points, and for any other number, you lose 2 points. Then:
- Probability of rolling a 6 is $\dfrac{1}{6}$.
- Probability of rolling any other number is $\dfrac{5}{6}$.
Expected score is:
$$E(X) = 10\times\dfrac{1}{6} + (-2)\times \dfrac{5}{6} = \dfrac{10}{6} - \dfrac{10}{6} = 0$$
Therefore, from a long-term perspective (if the game is played repeatedly), it is fair with no advantage in score.
Through these two examples, it should be easy to understand the definition and role of expectation in mathematics.
Linearity and Independence of Expectations
Expectations are additive. Suppose there are two events (they can be independent or dependent), with expectations $E(\Alpha)$ and $E(\Beta)$, then the overall expectation $E(\Alpha + \Beta)$ can be directly decomposed into $E(\Alpha) + E(\Beta)$.
This shows that expectation calculations can be broken down and weighted, regardless of whether the random variables are independent.
E.g. 5 Probability Game II
There is a probability game with two rounds:
- First round: the player rolls a six-sided die, and the score is the number rolled.
- Second round: the player rolls two six-sided dice, and the score is the sum of the numbers rolled.
Objective: Calculate the total expected score for the player.
For this problem, we can use the linearity of expectation. Define the following variables:
- First round score: random variable $X_1$, with values $1, 2, 3, 4, 5, 6$.
- Second round score: random variable $X_2$, which is the sum of the two dice, with values $2, 3, ..., 11, 12$.
- Total score random variable $S = X_1 + X_2$.
According to the linearity of expectation:
$$E(S) = E(X_1) + E(X_2)$$
We can calculate the expectations of the two random variables separately and add the results to find the total expected score of the probability game.
After calculation (this article does not provide detailed examples of the same expectation calculation process, which can be manually derived), the expected scores for the two rounds are:
- First round: $E(X_1) = \dfrac{21}{6} = 3.5$.
- Second round: $E(X_2) = \dfrac{252}{36} = 7$.
Thus, the total expected score is:
$$E(S) = E(X_1) + E(X_2) = 3.5 + 7 = 10.5$$
This means that if the player plays the game infinitely, the average score per round is approximately 10.5.
Fundamental Algorithm Problems Involving Expectation
Expectation is widely applied in computer science. Here are several practical algorithm problems to help readers deepen their understanding of expectation.
E.g. 6 Randomly Swapping a Sequence
Problem Description
Given a sequence of length $n$, with elements $a_1, a_2, ..., a_n$. Each step involves selecting two different positions $i$ and $j$, satisfying $1 \le i, j \le n, i \neq j$, and swapping $a_i$ and $a_j$. Assuming infinite random swaps, determine the expected value of the final number at each position.
Solution Approach
After infinite random swaps, the sequence approaches a uniform random permutation. Since all permutations are equally likely, the expected value at each position should be the average of the sequence.
Mathematical Proof
Let the total sum of the sequence be $S = \Sigma_{i=1}^{n}a_i$, and the average be $\mu = \dfrac{S}{n}$. After infinite random swaps, each position could have any $a_i$, so the expected value is $\mu$.
C++ Code Implementation
The C++ code implementation for this problem is as follows:
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int main(){
int n; cin >> n;
vector<long long> a(n);
double sum = 0.0;
for(auto &x: a){
cin >> x;
sum += x;
}
double average = sum / n;
// Output the expected value for each position
for(int i=0;i<n;i++){
printf("%.6lf ", average);
}
return 0;
}
E.g. 7 Lottery Winning Expectation
Problem Description
You are participating in a lottery game where each ticket has two numbers: a red ball and a blue ball. The red ball number is selected from 1 to R, and the blue ball number is selected from 1 to B. Each ticket wins if both the red and blue numbers are correct. You purchased k different tickets. What is the expected number of wins?
Solution Approach
First, calculate the winning probability for each ticket as $\dfrac{1}{R} \times \dfrac{1}{B} = \dfrac{1}{RB}$. Purchasing k independent tickets, the expected number of wins is $k \times \dfrac{1}{RB}$.
C++ Code Implementation
The C++ code implementation for this problem is as follows:
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int main(){
long long R, B, k;
cin >> R >> B >> k;
double E = (double)k / (R * B);
printf("%.6lf\n", E);
return 0;
}
E.g. 8 Expected Steps to Reach the Target
Problem Description
On a 2D grid, starting from the point $(0, 0)$, the goal is to reach the point $(n, m)$. Each step, you can choose to move right or up. The probability of moving right is $p$, and the probability of moving up is $1 - p$. Calculate the expected number of steps to reach the target.
Solution Approach
Compared to previous problems, this one is more challenging. It is a classic problem combining dynamic programming and expectation. We define $dp[i][j]$ as the expected number of steps from point $(i, j)$ to the target.
State transition equation:
- If the current coordintae is the target, i.e., $i = n$ and $j = m$, then $dp[i][j] = 0$, indicating that zero steps are needed to reach the target.
- If on the boundary (i.e., $i = n$ or $j = m$), only single-direction movement is allowed:
- $dp[i][j] = 1 + dp[i][j+1]$ (moving right)
- $dp[i][j] = 1 + dp[i+1][j]$ (moving up)
- Otherwise:
- $dp[i][j] = 1 + p \times dp[i][j+1] + (1 - p) \times dp[i+1][j]$
Calculation order: start from the target and fill the $dp$ table in reverse order.
C++ Code Implementation
The C++ code implementation for this problem is as follows:
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
int main(){
int n, m; double p;
int dp[505][505];
cin >> n >> m >> p;
for(int i=n; i>=0; i--){
for(int j=m; j>=0; j--){
if(i == n && j == m){
dp[i][j] = 0.0;
continue;
}
if(i == n) dp[i][j] = 1.0 + dp[i][j+1];
else if(j == m) dp[i][j] = 1.0 + dp[i+1][j];
else dp[i][j] = 1.0 + p * dp[i][j+1] +
(1.0 - p) * dp[i+1][j];
}
}
printf("%.6lf\n", dp[0][0]);
return 0;
}
E.g. 9 P1365 WJMZBMR打osu! / Easy
Solution Approach
This is a classic example of an expected value dynamic programming problem. We define $dp_i$ as the expected score ending at the $i$-th character, using a variable $\mathtt{len}$ to represent the number of consecutive o characters (including the current character). Based on the classificatino of the three types of characters in the string, we discuss:
-
When the current character is
x:This indicates the current round fails, and the expected score will not increase or decrease (same as $dp_{i-1}$). Meanwhile, $\mathtt{len}$ should be reset to 0, indicating no consecutive
ocharacters up to now. -
When the current character is
o:This indicates the current round succeeds, and the expected score should be the expected score from the previous round $dp_{i-1}$ plus the expected score for this round $((\mathtt{len} + 1)^2 - \mathtt{len}^2)$ (removing the score for a streak of length $\mathtt{len}$, adding the score for a streak of length $\mathtt{len} + 1$). Simplifying gives: $dp_i = dp_{i-1} + 2 \times \mathtt{len} + 1$. After updating the $dp$ array, set $\mathtt{len}$ to $\mathtt{len} + 1$.
-
When the current character is
?:We need to consider both success and failure scenarios (the average of the successful and failed expectations):
$$dp_i = dp_{i-1} + \dfrac{((\mathtt{len} + 1)^2 - \mathtt{len}^2) + 0}{2} = dp_{i-1} + \mathtt{len} + 0.5$$
Meanwhile, update $\mathtt{len}$ to $\dfrac{(\mathtt{len} + 1) + 0}{2} = \dfrac{\mathtt{len} + 1}{2}$.
Next, simply iterate through the string.
C++ Code Implementation
The C++ code implementation for this problem is as follows:
#include <iostream>
#include <algorithm>
using namespace std;
constexpr int N = 3e5 + 5;
int n; char c;
long double len, dp[N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i=1; i<=n; i++){
cin >> c;
switch (c){
case '?':
dp[i] = dp[i-1] + len + 0.5;
len = (len + 1) / 2; break;
case 'o':
dp[i] = dp[i-1] - len * len + (len + 1) * (len + 1);
len++; break;
case 'x': dp[i] = dp[i-1]; len = 0; break;
}
}
printf("%.4Lf\n", dp[n]);
return 0;
}
This algorithm has a time complexity of $O(n)$ and a space complexity of $O(n)$. However, since each $dp_i$ depends only on the previous state ($dp_{i-1}$), the space complexity can be further reduced to $O(1)$.
E.g. 10 P1850 [NOIP2016 Advanced Group] Change Classes
This problem is the original question from the NOIP 2016 competition, showing that expected value dynamic programming is a key topic.
Solution Approach
Similarly, we first define the $dp$ state. Define $dp_{i,j,k}$ as the expected value when reaching the $i$-th point, applying for $j$ class changes, and whether to change (1/0) in the current step. Use $map[a][b]$ to represent the shortest path between $a$ and $b$ in the map (due to the data range and the need for multi-source shortest paths, use Floyd's algorithm to compute the shortest paths).
State transitions:
-
No class change ($dp_{i,j,0}$):
-
Case 1: Previous step also did not change classes:
$$dp_{i,j,0} = dp_{i-1,j,0} + \text{map}[c[i-1]][c[i]]$$
-
Case 2: Previous step changed classes:
$$dp_{i,j,0} = dp_{i-1,j,1} + \text{map}[c[i-1]][c[i]] \cdot (1 - k[i-1]) + \text{map}[d[i-1]][c[i]] \cdot k[i-1]$$
-
-
Class change ($dp_{i,j,1}$):
-
Case 1: Previous step did not change classes:
$$dp_{i,j,1} = dp_{i-1,j-1,0} + \text{map}[c[i-1]][d[i]] \cdot k[i] + \text{map}[c[i-1]][c[i]] \cdot (1 - k[i])$$
-
Case 2: Previous step changed classes:
$$dp_{i,j,1} = dp_{i-1,j-1,1} + \text{map}[d[i-1]][d[i]] \cdot k[i-1] \cdot k[i] + \text{map}[d[i-1]][c[i]] \cdot k[i-1] \cdot (1 - k[i]) + \text{map}[c[i-1]][d[i]] \cdot (1 - k[i-1]) \cdot k[i] + \text{map}[c[i-1]][c[i]] \cdot (1 - k[i-1]) \cdot (1 - k[i])$$
-
C++ Code Implementation
The C++ code implementation for this problem is as follows:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
constexpr int N = 2005;
constexpr int V = 305, E = 90000;
int n, m, v, e;
int c[N], d[N];
double k[N];
long long map[V][V];
// dp[i][j][k] represents the expected value when reaching the i-th point, applying for j times,
// and whether to apply (k) in the current step.
double dp[N][N][2];
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> v >> e;
for (int i=1; i<=n; i++) cin >> c[i];
for (int i=1; i<=n; i++) cin >> d[i];
for (int i=1; i<=n; i++) cin >> k[i];
for (int i=1; i<=v; i++){
for (int j=1; j<=v; j++){
map[i][j] = 0x7f7f7f7f;
}
map[i][i] = map[i][0] = map[0][i] = 0;
}
for (int i=1; i<=e; i++){
int a, b, w;
cin >> a >> b >> w;
map[a][b] = map[b][a] = min(map[a][b], 1LL * w);
}
for (int k=1; k<=v; k++){
for (int i=1; i<=v; i++){
for (int j=1; j<=v; j++){
map[i][j] = min(map[i][k] + map[k][j], map[i][j]);
}
}
}
for (int i=0; i<=n; i++){
for (int j=0; j<=m; j++){
dp[i][j][0] = dp[i][j][1] = 1e9;
}
}
dp[1][0][0] = dp[1][1][1] = 0;
for (int i=2; i<=n; i++){
dp[i][0][0] = dp[i-1][0][0] + map[c[i-1]][c[i]];
for (int j=1; j<=min(i, m); j++){
int C1 = c[i-1], C2 = d[i-1], C3 = c[i], C4 = d[i];
dp[i][j][0] = min(dp[i][j][0], min(dp[i-1][j][0] + map[C1][C3],
dp[i-1][j][1] + map[C1][C3] * (1 - k[i-1]) + map[C2][C3] * k[i-1]));
dp[i][j][1] = min(dp[i][j][1],
min(dp[i-1][j-1][0] + map[C1][C3] * (1 - k[i]) + map[C1][C4] * k[i],
dp[i-1][j-1][1] + map[C2][C4] * k[i] * k[i-1] +
map[C2][C3] * k[i-1] * (1 - k[i]) +
map[C1][C4] * (1 - k[i-1]) * k[i] +
map[C1][C3] * (1 - k[i-1]) * (1 - k[i])));
}
}
double ans = 1e9;
for (int i=0; i<=m; i++){
ans = min(ans, dp[n][i][0]);
ans = min(ans, dp[n][i][1]);
}
printf("%.2lf", ans);
return 0;
}
E.g. 11 P1654 OSU!
Similar to [E.g. 9 [P1365 WJMZBMR打osu! / Easy]], with slight modifications.
Solution Approach
To solve for the expected value of $x^3$, we must maintain the expected values of $x$ and $x^2$.
Specifically:
- $a[i]$ represents the expected value of $x$ ending at the $i$-th position.
- $b[i]$ represents the expected value of $x^2$ ending at the $i$-th position.
- $dp[i]$ represents the expected value of $x^3$ ending at the $i$-th position.
Recurrence formulas:
- $a[i] = (a[i-1] + 1) \times p[i]$
- $a[i-1]$ is the expected value of $x$ from the previous round, and adding the contribution of the current position $1 \cdot p[i]$.
- $b[i] = (b[i-1] + 2 \cdot a[i-1] + 1) \times p[i]$
- The expected value of $x^2$ from the previous round plus the new contribution, including $2 \cdot a[i-1] \cdot 1$ and $1^2$.
- $dp[i] = dp[i-1] + (3 \cdot (a[i-1] + b[i-1]) + 1) \times p[i]$
- Finally, accumulate all the expected values of $x^3$ to the current $dp$ state.
C++ Code Implementation
The C++ code implementation for this problem is as follows:
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
constexpr int N = 3e5 + 5;
int n;
long double p[N], dp[N], a[N], b[N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i=1; i<=n; i++) cin >> p[i];
for (int i=1; i<=n; i++){
a[i] = (a[i-1] + 1) * p[i];
b[i] = (b[i-1] + 2 * a[i-1] + 1) * p[i];
dp[i] = dp[i-1] + (3 * (a[i-1] + b[i-1]) + 1) * p[i];
}
printf("%.1Lf\n", dp[n]);
return 0;
}
Common Misconceptions and Errors
Misconception One: Confusing Expected Value with Actual Value
Expected value represents the average of a random variable, but this does not mean the random variable equals the expected value in every experiment. The expected value is the average result after many experiments, not the deterministic result of a single experiment.
Misconception Two: Ignoring Conditional Expectation
In complex problems, ignoring conditional expectation can lead to incorrect expectation calculations, especially in problems with dependencies or multi-stage decisions. For example, in [E.g. 8 Expected Steps to Reach the Target], failing to consider the current position's conditions (current coordinates) would lead to errors in the state transition equations, resulting in incorrect expected steps.