Largest Number Drawn - RV 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.
 A: 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)$
A: Pick your $n$ numbers.  There are ${N^n}$ ways to do that.
The number of ways the maximum is $k$ is ${k^n-(k-1)^n}$.
The sum you want is $\sum_{k=1}^N k \Pr(\max=k)\\=
\sum_{k=1}^N [k^{n+1}-k(k-1)^n]/N^n\\=N-\sum_{k=1}^{N-1}(k/N)^n$
