Solution: 2017 Fall Final - 20

Author: Michiel Smid

Question

You choose a uniformly random element, say $a$, from the set $\{1,2,\dots,100\}$, and you choose a uniformly random element, say $b$, from the same set $\{1,2,\dots,100\}$. ($a$ and $b$ are chosen independently of each other.) Define the random variable $X$ to be

X = $\max(a,b)$.

What is the expected value $\mathbb{E}(X)$ of the random variable $X$?

(a)

${\sum_{k=1}^{100}} k \cdot \left( \frac{1+2(k-1)}{100^{2}} \right)$

(b)

${\sum_{k=1}^{100}} k \cdot \frac{k(k-1)}{100^{2}}$

(c)

${\sum_{k=1}^{100}} k \cdot \frac{k^{2}}{100^{2}}$

(d)

${\sum_{k=1}^{100}} k \cdot \frac{2k}{100^{2}}$

Solution

Goal of Problem

We want to calculate the expected value of the random variable: $X = \max(a, b)$ where:

$ a $ and $ b $ are chosen independently and uniformly from the set $ {1, 2, \ldots, 100} $.

Key Observation

The maximum of two independent uniformly random variables, $ a $ and $ b $, takes the value $ k $ if:

At least one of the two numbers is equal to $ k $.
The other number is less than or equal to $ k $.

Probability that $ X = k $

For a maximum of $ k $ to occur:

At least one of $ a $ or $ b $ must be equal to $ k $.
The other value must be $ \leq k $.

The total number of outcomes for $ (a, b) $ is: $100^2$ since $ a $ and $ b $ are chosen from $ {1, 2, \ldots, 100}$.

The favorable outcomes for $ X = k $ are:

$ a = k $ and $ b \leq k $: $ k $ outcomes.
$ b = k $ and $ a \leq k $: $ k $ outcomes.
$ a = b = k $ is counted twice, so subtract 1.

Total favorable outcomes: $2k - 1$

This means the probability that $ X = k $ is: $P(X = k) = \frac{|X = k|}{|S|} = \frac{2k - 1}{100^2}$.

Substituting Expected Value Formula

By the definition of expected value: $E(X) = \sum_{k=1}^{100} k \cdot P(X = k)$

Substituting the probability: $E(X) = \sum_{k=1}^{100} k \cdot \frac{2k - 1}{100^2}$

We can rewrite $2k-1$ as $1 + 2(k-1)$. They result in the same sum, so we get: $E(X) = \sum_{k=1}^{100} k \cdot \left(\frac{1 + 2(k-1)}{100^2}\right)$