Chapter 7, Problem 7.1STPE

Consider a list of m names, where the same name may appear more than once on the list. Let $n\left(i\right),i=1,\mathrm{...},m,$ denote the number of times that the name in position i appears on the list, and let d denote the number of distinct names on the list.

a. Express d in terms of the variables $m,n\left(i\right),i=1,\mathrm{...},m$. Let U be a uniform $\left(0,1\right)$ random variable, and let $X=\left[mU\right]+1$.

b. What is the probability mass function of X?

c. Argue that $E\left[\frac{m}{n}\left(X\right)\right]=d$.