Probability with replacement, question on balls in urn.

Question

An urn contains $n$ balls numbered 1 through $n$. If you withdraw $m$ balls randomly in sequence, each time replacing the ball selected previously, find $P\{X=k\}$, $k = 1,.....m$, where $X$ is the maximum of the $m$ chosen numbers.

This was my approach

If $k$ is the maximum then all the $m$ numbers have to be chosen from $1,...k$. Now we can have $i$ balls that are less than $k$ which gives $k-1$ options and $m-i$ balls that are numbered exactly $k$ where $i$ goes from $0$ to $m-1$.

So $$P\{X=k\} = \sum\limits_{i=0}^{m-1}{m\choose k}\frac{(k-1)^i}{n^i}\frac{1}{n^{m-i}}$$

However the answer given is

$$P\{X=k\} = \frac{k^m}{n^m} - \frac{(k-1)^m}{n^m}$$

I wanted to know if my approach and answer are correct, if yes how can I come to the second solution from the first one? If no, can please give the correct approach?

Answer 1

Noting that $n^i\times n^{m-i}=n^m$ we can rewrite your sum as $$\frac 1{n^m}\times \binom mk\times \sum_{i=0}^{m-1}(k-1)^i$$ For $k=1$ this is $\frac m{n^m}$ which is not correct.

A quick approach:

It is somewhat easier to compute $P(X≤k)$. There are $k^m$ ways to choose $m$ values $≤k$ and $n^m$ unconstrained selections, so $$P(X≤k)=\frac {k^m}{n^m}$$

But, of course, $$P(X=k)=P(X≤k)-P(X≤k-1)$$

Answer 2

Your mistake is that you did not correctly count the number of ways in which we could choose $i$ of the $m$ drawn balls to be the ones whose values are less than $k$. That number is $\binom mi,$ but you wrote $\binom mk.$ If you write your formula with this correction, you will have $$P\{X=k\} = \sum_{i=0}^{m-1}\binom mi\frac{(k-1)^i}{n^i}\frac{1}{n^{m-i}}.$$ This gives the correct result, although it still takes more effort than the problem needs.

Answer 3

The following is the answer given by Sheldon Ross in A First Course in Probability.

Let $X_i$, $i = 1, ... , m$, denote the number on the $i$th ball drawn. Then

\begin{align*} \mathbb{P}(X\leqslant k)&=\mathbb{P}(X_{1}\leqslant k, X_{2}\leqslant k,...,X_{m}\leqslant k)\\ &=\mathbb{P}(X_{1}\leqslant k)\mathbb{P}(X_{2}\leqslant k)\cdots\mathbb{P}(X_{m}\leqslant k)\\ &=\left(\frac{k}{n}\right)^{m}. \end{align*}

Therefore,

$$\mathbb{P}(X=k)=\mathbb{P}(X\leqslant k)-\mathbb{P}(X\leqslant k-1)=\left(\frac{k}{n}\right)^{m}-\left(\frac{k-1}{n}\right)^{m}.$$