7.1. 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,...,m$, denote the number of times that the name in position iappears 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,...,m$. Let U be a uniform (0, 1) random variable, and let $X=\left[mU\right]+1$.

(b) What is the probability mass function of X?

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

$n\left(i\right),i=1,\dots ,m$ is the number of times that the name in position iappears on the list

$d=$the number of distinct names on the list

Express $d$in terms of $m$.

Here, $d$is the number of distinct names on the list and $n\left(i\right)$is the number of times that the name in $i^{th}$position appears on the list.

The total number of name in the list is determined as,

$\text{Total number of names}=m$

$=\sum _{i=1}^m \left(n\right(i\left)\right)\times d$

From the overhead expression of the total number of names, $d$can be expressed in terms of $n\left(i\right)$and $m$. Hence, $d$is expressed as:

$m=\sum _{i=1}^m \left(n\right(i\left)\right)\times d$

$\sum _{i=1}^m 1=d\sum _{i=1}^m \left(n\right(i\left)\right)$

$d=\frac{\sum _{i=1}^m 1}{\sum _{i=1}^m \left(n\right(i\left)\right)}$

$d=\sum _{i=1}^m \frac{1}{n\left(i\right)}$

Thus, the required expression of $d$ will be $d=\sum _{i=1}^m\frac{1}{n\left(i\right)}$.

$n\left(i\right),i=1,\dots ,m$is the number of times that the name in position $i$appears on the list

$d=$the number of distinct names on the list

We need to calculate the probability mass function of X.

If a random variable, U that follows uniform distribution between 0 and 1 .

So that, the probability density function of U is,

$f_U\left(u\right)=\left\{\begin{array}{l}1\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}0\le u\le 1\\ 0\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{Otherwise}\end{array}\right.$

If a random variable X and it is defined as $X=[mU]+1$.

The probability mass function of Xis determined as:

$P(X=i)=P\left(\right[mU]+1=i)$

$=P\left(\right[mU]=i-1)$

$=P(i-1\le mU<i)$

$=P\left(\frac{i-1}{m}\le U<\frac{i}{m}\right)$

Using the probability density function of U, the probability mass function of X is simplified as:

$P(X=i)=P\left(\frac{i-1}{m}\le U<\frac{i}{m}\right)$

$={\int }_{\frac{i-1}{m}}^{\frac{i}{m}} 1du$

$=[u{]}_{\frac{i-1}{m}}^{\frac{i}{m}}$

$=\frac{i}{m}-\frac{i-1}{m}$

$=\frac{1}{m}$

Thus, the probability mass function of X will be $P(X=i)=\frac{1}{m}$.

$n\left(i\right),i=1,\dots ,m$is the number of times that the name in position $i$appears on the list

$d=$the number of distinct names on the list

If $E\left(\frac{m}{n\left(X\right)}\right)=d$

The expected value of a random variable Y will be $E\left(Y\right)=\sum _{y}yP(Y=y)$

Now,$P(Y=y)$ is the probability mass function of the random variable Y.

Now we need to calculate the value of $E\left(\frac{m}{n\left(X\right)}\right)$

$E\left(\frac{m}{n\left(X\right)}\right)=\sum _{i=1}^m \frac{m}{n\left(i\right)}P(X=x)$

$=\sum _{i=1}^m \frac{m}{n\left(i\right)}\times \frac{1}{m}$

$=\sum _{i=1}^m \frac{1}{n\left(i\right)}$

$=d$

Thus, the value can be said that$E\left(\frac{m}{n\left(X\right)}\right)=d$