Understanding Linearity of Expectation

In probability theory, the Linearity of Expectation is a powerful property that simplifies the calculation of the expected value of a sum of random variables, regardless of whether the variables are ‘independent’ or ‘dependent’. This concept is particularly useful in various fields such as computer science, statistics, and operations research.

Introduction

A discrete random variable X is a function from a finite or countably infinite sample space S to the real numbers. It associates a real number with each possible outcome of the experiment. Each possible outcome in the sample space has a corresponding ‘probability’ associated with it, and the random variable assigns a real number value to each outcome.

For a discrete random variable X and a real number x, the probability density function of event, X = x can be defined as:

P[X = x] =  \sum_{X(s) = x} {P\{s\}} 

Expected value of a random variable

The distribution of a random variable is the ‘average’ of the value it takes on. And, the expected value E[X] of a discrete random variable X is:

E[X] =  \sum_{x} x * {P\{X = x\}} 

Let’s understand expected value through a simple example:

Consider a game in which you flip 2 coins. You’ll earn $3 for each head and lose $2 for each tail you get on the two coins. Now, the expected value of your earnings can be calculated as:

E[X] = (6 * P[H,H]) + (1 * P[H,T]) + (1 * P[T,H]) - (4 * P[T,T])
     = (6 * (1/4)) + (1 * (1/4)) + (1 * (1/4)) - (4 * (1/4))
     = 3/2 + 1/4 + 1/4 - 1
     = 1

Linearity of Expectation

Linearity of expectation is a property that states that the expected value of the sum of random variables is equal to the sum of their individual expected values. Mathematically, if X and Y are random variables,

E[X + Y] = E[X] + E[Y]

This property holds true regardless of whether X and Y are dependent or independent. It allows us to simplify the calculation of expected values in complex probability problems by breaking them down into simpler components.

The elegance of this theorem is its simplicity and the ease with which it can be extended to any number of random variables whether dependent or independent:

Now, let’s apply it to a programming problem.

Expected Number of Unique Cards

We need to calculate the expected number of unique cards drawn from a shuffled deck.
Suppose we draw k cards from a standard deck of 52 cards. Now, we want to find out the expected number of unique cards we could draw from the deck.

Pseudocode

1. For each card in the deck, we could use an indicator variable Xi which is '1' if the ith card is drawn at least once and '0' otherwise.

2. The total number of unique cards – U, can now be expressed as sum of all Xi:

U = X1 + X2 + X3 + ... + X52

3. Calculating E(Xi): The probability that any specific card i is not drawn in a single draw is 51/52. Now, the probability that card i is not drawn in k independent draws is:

 (\frac{51}{52})^k 

Using probability theory to calculate the probability that it is drawn at least once is:

E(Xi) =  1 - (\frac{51}{52})^k 

4. Using Linearity of Expectation:

E(U) =  \sum_{i=1}^{52} E(X_{i}) = 52 (1 - (\frac{51}{52})^{k}) 

Code Implementation

//
//  main.cpp
//  Linearity of Expectation
//
//  Created on 11/05/24.
//

#include <iostream>
#include <cmath>
using namespace std;

double expected_unique_cards(int k) {
    double prob_not_drawn = pow(51.0 / 52.0, k);
    double expected_unique = 52 * (1 - prob_not_drawn);
    return expected_unique;
}

int main() {
    int k = 10;
    
    cout << "Expected number of unique cards: " << expected_unique_cards(k) << endl;
    
    return 0;
}

Output

Expected number of unique cards: 9.17753

Linearity of expectation is a powerful concept in probability theory that simplifies the calculation of expected values in probabilistic experiments. By breaking down complex problems into simpler components and leveraging this property, we can efficiently analyze various probabilistic scenarios. This concept forms the foundation for more advanced probabilistic analysis in various fields.

Reference: Introduction to Algorithms – (CLRS book)