Expected Value and Linearity of Expectation

Expected value is the probability-weighted average of a numeric random variable, not necessarily an attainable outcome. Linearity lets us add expectations of components even when those components are dependent. This often avoids enumerating an enormous joint sample space. The main program computes a weighted discrete expectation; a separate example uses indicator variables for sampling without replacement.

Prerequisites: Probability Fundamentals; sums; floating-point arithmetic.

Build the idea

1. 1. Define a discrete expectation

   If X takes value xᵢ with probability pᵢ, then E[X]=Σxᵢpᵢ. Probabilities are nonnegative and sum to one. The program receives positive integer weights wᵢ and interprets pᵢ=wᵢ/Σw, so normalization is explicit. Multiple listed outcomes may have the same numeric value; their probability contributions still add.

   $$E\left[X\right]=\sum _i{x}_i{p}_i$$

2. 2. Derive linearity without independence

   For random variables X,Y on the same outcome space, sum (X(ω)+Y(ω))P(ω) and distribute addition to obtain E[X]+E[Y]. Dependence does not appear in this derivation. By contrast, E[XY]=E[X]E[Y] generally requires independence or another justification. Do not transfer the unrestricted sum rule to products.

   $$E(X+Y)=E\left(X\right)+E\left(Y\right)$$

3. 3. Use indicator random variables

   Let I be one when an event occurs and zero otherwise. Then E[I]=P(event). If a total count X is a sum of indicators, its expectation is the sum of their individual probabilities. The indicators may be dependent. This is often the simplest way to count expected successes, equal pairs or occupied categories.

4. 4. Compare the two examples

   Weighted values 0,10,20 with weights 1,2,1 have expectation (0+20+20)/4=10. For two draws without replacement from three red and two blue objects, let each draw’s red indicator be Iⱼ. Each position is marginally red with probability 3/5 by symmetry, so expected red count is 2·3/5=1.2, even though the draws are dependent.

5. 5. Interpret the result correctly

   An expectation can be fractional or absent from the outcome set; it is a weighted average over repeated conceptual trials. It is not a guarantee for one run and not a median or most likely value. The programs compute formulas, not simulations, and print floating approximations. Long-double accumulation avoids integer overflow in weighted products under the stated bounds, but still has finite precision.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: 5. Interpret the result correctly An expectation can be fractional or absent from the
// outcome set; it is a weighted average over repeated conceptual trials.
#include<iostream>
#include<iomanip>
int main(){
    int n;
    std::cin>>n;
    long double weighted=0,totalWeight=0;
    for(int i=0;i<n;++i){
        long long value,weight;
        std::cin>>value>>weight;
        weighted+=(long double)value*weight;
        totalWeight+=weight;
    }
    std::cout<<std::fixed<<std::setprecision(6)<<weighted/totalWeight<<'\n';
}

Complexity analysis

O(n) time and O(1) auxiliary space for n weighted outcomes, streamed without storing them. Indicator supplement O(1) time/space. Numeric outputs are approximate. n≥1 and positive weights guarantee a nonzero normalizer; input magnitudes are bounded before conversion to long double.

Example input and output

Read n (1..100000), then n pairs value weight with |value|≤10^9 and 1≤weight≤10^6. Print the weighted expectation to six decimal places.

Input

3
0 1
10 2
20 1

Output

10.000000

Probabilities are 1/4,1/2,1/4 and weighted contributions are 0,5,5.

Read red blue draws, 0≤red,blue≤10^6, 1≤red+blue and 0≤draws≤red+blue. Draw uniformly without replacement; print expected red count.

// Key idea: 5. Interpret the result correctly An expectation can be fractional or absent from the
// outcome set; it is a weighted average over repeated conceptual trials.
#include<iostream>
#include<iomanip>
int main(){
    long long red,blue,draws;
    std::cin>>red>>blue>>draws;
    long double expected=(long double)draws*red/(red+blue);
    std::cout<<std::fixed<<std::setprecision(6)<<expected<<'\n';
}

Input

3 2 2

Output

1.200000

Each draw position has red probability 3/5, so linearity gives 2×3/5 despite dependence.

Complexity: O(1) arithmetic time and space.

Practical applications

Use indicator sums for expected counts and contributions, especially when full distributions are difficult. Use probability DP when the distribution or nonlinear outcome is required. A modular expected value is a separate field-arithmetic representation needing invertible denominators; it is not an ordinary real probability.

Check your understanding

Does E[X+Y]=E[X]+E[Y] require independent X and Y?

Put it into practice

Compute expected equal-value pairs in random draws using one indicator per pair.