Q.7.1 - A First Course in Probability

Question

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 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, ... , 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$. 

Step-by-Step Solution

Answer

1. The required expression of $d$ will be $d=\sum _{i=1}^m \frac{1}{n\left(i\right)}$.
2. The probability mass function of X will be $P(X=i)=\frac{1}{m}$
   
3. The value can be said that as $E\left(\frac{m}{n\left(X\right)}\right)=d$.

Step 1: Given information (Part a)

$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 

Step 2: Solution (Part a)

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)}$

Step 3: Final answer (Part a)

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

Step 4: Given information (Part b)

$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

Step 5: Solution (Part b)

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=[m U]+1$.

The probability mass function of X is 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)$

Step 6:Solution (Part b)

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}$

Step 7: Final answer (Part b)

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

Step 8: Given information (Part c)

$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

Step 9: Solution (Part c)

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$

Step 10: Final answer (Part c)

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