Traversing an array and counting the number of distanct number from the given elements in an array.

Question

You are given an array $A[0 \ldots n-1]$ of $n$ numbers. Let $d$ be the number of \emph{distinct} numbers that occur in this array. For each $i$ with $0 \leq i \leq n-1$, let $N_i$ be the number of elements in the array that are equal to $A[i]$.

Show that $d = \sum_{i=0}^{n-1} 1/N_i$.
Consider the following algorithm:

Step 1: Choose an integer $k$ in $\{0,1,2,\ldots,n-1\}$ uniformly at random, and let $a = A[k]$.

Step 2: Traverse the array and compute the number $N_k$ of times that $a$ occurs.

Step 3: Return the value $X = n/N_k$.

Determine the expected value $E(X)$ of the random variable $X$.

Answer 1

Suppose that the number $a$ occurs $N_a$ times. Each of the $N_a$ occurrences of $a$ makes a contribution of $\frac{1}{N_a}$ to the sum $\sum_0^{n-1}\frac{1}{N_i}$, for a total contribution of $N_a\cdot \frac{1}{N_a}=1$. Thus the sum $\sum_0^{n-1}\frac{1}{N_i}$ counts the number of distinct $a$ in the array.

The expectation question is essentially a rewording of the above observation. The $i$ are chosen with equal probabilities $\frac{1}{n}$. If $i$ is chosen, then $X=\frac{n}{N_i}$. The expected value of $X$ is therefore $\sum_{i=0}^{n-1} \frac{1}{n} \cdot\frac{n}{N_i}$. Thus if there are $d$ distinct values in the array, then $E(X)=d$.

Answer 2

For the second part: E[X] = E[n/Nk] = n/E[Nk] <-Property of expected value operator E[Nk] = n * Pr(Ai = k) = n * 1/n = 1 recall: E[X] = n/E[Nk] = n/1 = n

Maybe I made some logical mistake though because andre has a really high reputation and our answers are different.