[Math] Largest Number Drawn – RV

probabilityrandom variables

From a box containing N identical tickets numbered 1 to N, n tickets are drawn with replacement. Let X be the largest number drawn. Find E[X]. Rohatgi 3.2 (2nd problem)

My solution 2:

I thought about using the Indicator RV.

Xi = 1, if the ith draw is the largest

Xi = 0, o/w

Now, E[Xi] = Pr {Xi = 1}
= 1/i {Since each of other i-1 numbers could be the largest}

=> E[X] = $\displaystyle\sum\limits_{i=1}^N 1/i$

Does it make sense?

Thanks.

Best Answer

Let $X_i$ be the value of the $i^{th}$ ticket drawn. Let $X$ denote the largest value drawn, and notice that $X = \max{ \{ X_1, ..., X_n \}}$. Let's try to find the pmf of $X$. This is actually easiest if we use CDFs.

$F_X(k)=P(X \leq k)=P(\max{ \{ X_1, ..., X_n \}} \leq k) = P((X_1 \leq k) \cap ... \cap (X_n \leq k))$.

The second equality holds because we need each of the $X_i$ to be less or equal to $k$ if we want the maximum to be less or equal to $k$.

Now notice that we are sampling the tickets with replacement, so each draw is independent. This allows us to say

$P((X_1 \leq k) \cap ... \cap (X_n \leq k)) = P(X_1 \leq k)\cdot \cdot \cdot P(X_n \leq k) = P(X_i \leq k)^n$.

Again, since we are sampling with replacement, he last equality holds because each draw has the same distribution. Now we know that each $X_i$ is a discrete uniform distribution on the set $ \{ 1, 2, ... N \}$, so, putting it all together, what we end up with is

$F_X(k) = P(X_i = k)^n = (k/N)^n$.

From this we can easily find $p_X(k)$, and then $E(X) = \sum_{k=1}^{N} kp_X(k)$

Related Question