Q. 4.30 - A First Course in Probability

Question

Balls numbered $1$ through $N$ are in an urn. Suppose that $n,n\le N$, of them are randomly selected without replacement. Let $Y$ denote the largest number selected.

(a) Find the probability mass function of $Y$.

(b) Derive an expression for $E\left[Y\right]$ and then use Fermat's combinatorial identity (see Theoretical Exercise $11$ of Chapter $1$) to simplify the expression.

Step-by-Step Solution

Answer

(a) The probability mass function of $Y$ is$P(Y=k)=\frac{\left(\begin{array}{l}k-1\\ n-1\end{array}\right)}{\left(\begin{array}{l}N\\ n\end{array}\right)}$

(b) $E\left(Y\right)=\frac{N+1}{n(n+1)}$

Step 1: Definition Part (a)

A probability mass function is a cycle over the example space of a discrete arbitrary variable $X$ which gives the probability that $X$ is indistinguishable from a particular worth.

Step 2: Explanation Part (a)

Let's define the  random variable $Y$. It marks the largest number taken out of the urn. We find that $Y\in \{n,\dots ,N\}$.

Let's take any $k\in \{1,\dots ,N\}$.  

From the information we observe that there are $\left(\begin{array}{l}N\\ n\end{array}\right)$ of all possible combinations.

If the largest number taken out is $k$, we are capable to choose $n-1$ out of $k-1$ numbers freely.

Hence

$P(Y=k)=\frac{\left(\begin{array}{c}k-1\\ n-1\end{array}\right)}{\left(\begin{array}{c}N\\ n\end{array}\right)}$

Step 3: Given information Part (b)

Balls numbered $1$ through $N$are in an urn. Suppose that $n,n\le N$, of them are randomly selected without replacement. Let $Y$denote the largest number select

Step 4: Explanation Part (b)

We have that, $E\left(Y\right)=\sum _{k=n}^N k\cdot \frac{\left(\begin{array}{l}k-1\\ n-1\end{array}\right)}{\left(\begin{array}{l}N\\ n\end{array}\right)}=\frac{1}{\left(\begin{array}{l}N\\ n\end{array}\right)}\sum _{k=n}^N k\left(\begin{array}{l}k-1\\ n-1\end{array}\right)$ by using the definition of expectation.

Now, find that $k\left(\begin{array}{l}k-1\\ n-1\end{array}\right)=k\cdot \frac{(k-1)!}{(n-1)!(k-n)!}=\frac{k!}{(n-1)!(k-n)!}=\frac{1}{n}\left(\begin{array}{l}k\\ n\end{array}\right)$

So we have the expression above is equal to $\frac{1}{\left(\begin{array}{l}N\\ n\end{array}\right)}\sum _{k=n}^N\frac{1}{n}\left(\begin{array}{l}k\\ n\end{array}\right)=\frac{1}{n\left(\begin{array}{l}N\\ n\end{array}\right)}\sum _{k=n}^N\left(\begin{array}{l}k\\ n\end{array}\right)$

Using Fermat's combinatoric identity, we have that 

$\sum _{k=n}^N\left(\begin{array}{l}k\\ n\end{array}\right)=\left(\begin{array}{l}N+1\\ n+1\end{array}\right)$

Step 5: Final answer Part (b)

So finally, we have that 

$E\left(Y\right)=\frac{1}{\left(\begin{array}{l}N\\ n\end{array}\right)}·\left(\begin{array}{c}N+1\\ n+1\end{array}\right)=\frac{N+1}{n(n+1)}$