Find the expected value of the largest number in the sample.

Question

An urn contains N cards numbered from 1 to N. A random experiment It consists of selecting n cards at random and with replacement. Find the expected value of the largest number in the sample.

The answer is $N - \frac{1}{N^{n}} \Sigma_{k=1}^{N-1}k^{n}$ but I don´t how justify it.

Answer 1

Let $X$ enumerate the highest card selected in the sample; so $$\mathsf P(X>k)=\left(1-\left(1-\frac{k}{N}\right)^n\right)\mathbf 1_{k\in\{1..N\}}$$

Then the expected value is $$\begin{split}\mathsf E(X) &= \sum_{j=1}^{N} j~\mathsf P(X=j)\\ &= \sum_{j=1}^{N} \sum_{k=0}^{j-1} \mathsf P(X=j) \\ & = \sum_{k=0}^{N-1} \sum_{j=k+1}^{N}\mathsf P(X=j)\\ &= \sum_{k=0}^{N-1}\mathsf P(X>k) \end{split}$$

and so...

Answer 2

HINT

Let M be the largest number drawn. Then $\Pr(M=1)=N^{-n}.$ Suppose $k>1.$ Then for $M$ to be equal to $k$ it must be the case that every number drawn is $\le k$ and it must not be the case that every number drawn is $\le k-1$. That is, $$Pr(M=k)=\begin{cases} N^{-n},&k=1\\ N^{-n}(k^n-(k-1)^n),&2\le k\le N \end{cases} $$ Therefore, $$ E(M)= N^{-n}(1+\sum_{k=2}^N{[k^{n+1}-k(k-1)^n]},$$ and the only problem is evaluating the sum. In evaluating the sum, there is substantial telescoping. If you don't see it offhand, I suggest working it out for say $N=4$. You will spot the pattern, I'm sure.