10
$\begingroup$

Given the set of numbers from 1 to n: { 1, 2, 3 .. n } We draw n numbers randomly (with uniform distribution) from this set (with replacement). What is the expected number of distinct values that we would draw?

My Approach:

Let $X(k)$ denote the expected number of distinct values in a sample of size $k$. Then,

$X(k) = \frac{n - X(k-1)}{n}*(1 + X(k-1)) + \frac{X(k-1)}{n}*X(k-1)$

$X(k) = 1 + \frac{n-1}{n}*X(k-1)$

Since $X(1) = 1$, solving the recursive relation, we get

$X(k) = 1 + (\frac{n-1}{n}) + (\frac{n-1}{n})^2 + (\frac{n-1}{n})^3 + ... + (\frac{n-1}{n})^{k-1}$

$X(k) = \frac{1-(\frac{n-1}{n})^k}{\frac{1}{n}} = n*(1-(1-\frac{1}{n})^k)$

Hence,

$X(n) = n*(1-(1-\frac{1}{n})^n)$

The answer is correct, but I doubt if my approach is correct or not. The idea behind the first equation is: after $k-1$th sample, the probability of getting a new value in $k$th sample is $ \frac{n - X(k-1)}{n} $. Since $X(k-1)$ is not necessarily an integer, I doubt if the probability is correct or not. So my question is: is my approach correct or not? please provide some convincing explanation as to why or why not is it correct.

$\endgroup$
10
  • 1
    $\begingroup$ You approach is correct due to the linearity of the recurrence. Essentially, the $\frac{n - X(k-1)}{n}$ you wrote is $\frac{n - \mathbb{E}(X(k-1))}{n}$, which can be expanded to $\sum_{x} P(X(k-1)=x) \frac{n - x}{n}$ without any problem since the form is linear. $\endgroup$
    – Vezen BU
    Commented Jul 13, 2022 at 5:39
  • $\begingroup$ To make the proof more rigorous, you may want to define $X(k)$ as the NUMBER of distinct values in a sample of size $k$ and explicitly use $\mathbb{E}(X(k))$ as the EXPECTED number. $\endgroup$
    – Vezen BU
    Commented Jul 13, 2022 at 5:42
  • $\begingroup$ There is a more elegant route: linearity of expectation combined with symmetry. Write $Y=Y_1+\cdots +Y_1$ where $Y_i=1$ if number $i$ is drawn and $Y_i=0$ otherwise. Take expectation on both sides. $\endgroup$
    – drhab
    Commented Jul 13, 2022 at 6:03
  • $\begingroup$ @drhab I know but I was wondering if what I tried is correct or not $\endgroup$ Commented Jul 13, 2022 at 6:11
  • $\begingroup$ @VezenBU Thanks! I understand your idea. If you can write an answer using the same idea, I'll accept it $\endgroup$ Commented Jul 13, 2022 at 6:27

5 Answers 5

6
$\begingroup$

The easier route is through using linearity of expectation.

Let $Y_i$ be an indicator variable that is equal to $1$ if number $i$ is not collected in $n$ draws, and $0$ otherwise.

Then $P(Y_i) = {(1- \frac{1}{n})}^n$

Now the expectation of an indicator variable is just the probability of the event it indicates, and by linearity of expectation, which operates even when the variables are not independent,

$\Bbb E[Y] = \Sigma \Bbb E[Y_i] = n(1-\frac{1}{n})^n$

and $\Bbb E[X]=$ number of distinct coupons collected in $n$ draws
= n - $\Bbb E[Y] = n[1- (1-\frac{1}{n})^n]$

$\endgroup$
9
  • $\begingroup$ please read my question again. $\endgroup$ Commented Jul 13, 2022 at 6:13
  • $\begingroup$ Oh... I see that Vezen BU has already addressed your concern. I am just leaving my answer as a simpler approach. $\endgroup$ Commented Jul 13, 2022 at 6:31
  • 1
    $\begingroup$ Dear tba (I so much respect you, and not only for your age). It appeared that the question was posted by a smartguywithmathsmajor. See his comment on my comment. $\endgroup$
    – drhab
    Commented Jul 13, 2022 at 6:34
  • $\begingroup$ @drhab "So my question is: is my approach correct or not? please provide some convincing explanation as to why or why not is it correct." $\endgroup$ Commented Jul 13, 2022 at 6:38
  • 1
    $\begingroup$ @drhab: Thanks, I respect you equally, one among half a dozen or so. What to do ? I am the guy without math major getting dumber by the day ! $\endgroup$ Commented Jul 13, 2022 at 6:47
5
$\begingroup$

In your answer $X(k)$ is defined to be the expectation of the number of distinct results if $k$ are drawn. That is wrong.

Let $X_k$ denote the number of distinct results if $k$ are drawn.

Then:$$\mathbb E[X_k|X_{k-1}=r]=\frac{r}{n}\cdot r+\left(1-\frac{r}{n}\right)\cdot(r+1)=\left(1-\frac1n\right)r+1$$ From this we conclude that:$$\mathbb E[X_k|X_{k-1}]=\left(1-\frac1n\right)X_{k-1}+1$$and consequently:$$\mathbb EX_k=\mathbb E[\mathbb E[X_k|X_{k-1}]]=\left(1-\frac1n\right)\mathbb EX_{k-1}+1\tag1$$

This can be further exploited as you do in your question, resulting in:$$\mathbb EX_k=n\left(1-\left(1-\frac1n\right)^k\right)$$ Substitution $k=n$ gives your final result.


Of course it is much more elegant to make use of linearity of expectation and symmetry (provided in the answer of @true blue anil). I am aware of it (now) that you already know that but IMV the method simply deserves to be mentioned in this context. Also for the benefit of persons who read this and are not familiar with it yet.

$\endgroup$
2
  • $\begingroup$ thanks! now I have even more clarity. I had skipped conditional expectation, guess I'll have to have a look at it. Suppose I define X(k) as you have done, then is my recurrence relation still true? $\endgroup$ Commented Jul 13, 2022 at 7:55
  • $\begingroup$ Your recurrence relation holds (for expectations) and agrees with statement $(1)$ in my answer. $\endgroup$
    – drhab
    Commented Jul 13, 2022 at 8:12
3
$\begingroup$

The idea is correct although it would be better if you can state the proof in a more rigorous way. In short, the reason why the current a-bit-not-rigorous proof works essentially is due to the linearity of the recurrence. More specifically, the $\frac{n - X(k-1)}{n}$ you wrote can be better written as $\frac{n - \mathbb{E}(X(k-1))}{n}$, which can be expanded to $\sum_x \mathbb{P}(X(k−1)=x) \frac{n - x}{n}$ without any problem since the form is linear.


Revised Proof

Let $X(k)$ be the random variable indicating the number of distinct values in a sample of size k.

Then we have the following recurrence: $$ X(k) = \frac{n - X(k-1)}{n}*(1 + X(k-1)) + \frac{X(k-1)}{n}*X(k-1) = 1 + \frac{n-1}{n}*X(k-1), $$ which gives \begin{align} \mathbb{E}(X(k)) & = \sum_x \mathbb{P}(X(k) = x) x \\ &= \sum_{x'} \mathbb{P}(X(k-1) = x') (1 + \frac{n-1}{n}*x') \\ &= 1 + \frac{n-1}{n}*\mathbb{E}(X(k-1)). \end{align} The above equations with and without expectation have the same form due to the linearity of the recurrence.

Now, starting from $\mathbb{E}(X(1)) = X(1)=1$, we solve the above recursive relation and get \begin{align} \mathbb{E}(X(k)) &= 1 + (\frac{n-1}{n}) + (\frac{n-1}{n})^2 + (\frac{n-1}{n})^3 + ... + (\frac{n-1}{n})^{k-1} \\ &= \frac{1-(\frac{n-1}{n})^k}{\frac{1}{n}} = n*(1-(1-\frac{1}{n})^k) \end{align}

Hence, $$ \mathbb{E}(X(n)) = n*(1-(1-\frac{1}{n})^n). $$

$\endgroup$
4
  • $\begingroup$ Thanks!! Can't we just take the expectation on both sides of the recursive relation to obtain the relation between expectations? $\endgroup$ Commented Jul 13, 2022 at 7:28
  • $\begingroup$ @dumbguywithmathsmajor You are welcome! Do you mean $\mathbb{E}(X(k)) = \mathbb{E}(1 + \frac{n-1}{n}*X(k-1)) = 1 + \frac{n-1}{n}*\mathbb{E}(X(k-1))$? Sure! I just wanted to add more details. $\endgroup$
    – Vezen BU
    Commented Jul 13, 2022 at 7:35
  • $\begingroup$ Yeah, that's what I meant. Also, in your recurrence relation isn't the RHS just the expectation of X(k) given X(k-1)? $\endgroup$ Commented Jul 13, 2022 at 7:51
  • $\begingroup$ The recurrence works for expectations. Not for random variables. Notice that $X(k)$ is not determined by $X(k-1)$. $\endgroup$
    – drhab
    Commented Jul 13, 2022 at 8:25
0
$\begingroup$

As @VezenBU suggested.

Let X(k) denote the number of distinct values in a sample of size k.

$\mathbb{E}[X(k)] = \sum_x P(X(k-1) = x) \{(\frac{n-x}{n})(1+x) + \frac{x}{n}x\} $

$\mathbb{E}[X(k)] = \sum_x P(X(k-1) = x) \{(1-\frac{x}{n})(1+x) + \frac{x^2}{n}\} $

$\mathbb{E}[X(k)] = \sum_x P(X(k-1) = x) \{1 - \frac{x}{n} + x\} $

$\mathbb{E}[X(k)] = \sum_x \{P(X(k-1) = x) - \frac{x}{n} * P(X(k-1) = x) + x *P(X(k-1) = x) \} $

$\mathbb{E}[X(k)] = 1 - \frac{\mathbb{E}[X(k-1)]}{n} + \mathbb{E}[X(k-1)]$

$\mathbb{E}[X(k)] = 1 + (\frac{n-1}{n})*\mathbb{E}[X(k-1)]$

$\mathbb{E}[X(k)] = n*(1-(1-\frac{1}{n})^n)$

$\endgroup$
0
$\begingroup$

This can also be done using Stirling numbers. We have from first principles for the expectation that it is

$$\frac{1}{n^n} \sum_{k=1}^n k {n\choose k} k! {n\brace k} \\ = \frac{1}{n^n} n! [z^n] \sum_{k=1}^n k {n\choose k} (\exp(z)-1)^k \\ = \frac{n}{n^n} n! [z^n] \sum_{k=1}^n {n-1\choose k-1} (\exp(z)-1)^k \\ = \frac{n}{n^n} n! [z^n] (\exp(z)-1) \sum_{k=0}^{n-1} {n-1\choose k} (\exp(z)-1)^k \\ = \frac{n}{n^n} n! [z^n] (\exp(z)-1) \exp((n-1)z) \\ = \frac{n}{n^n} n! [z^n] (\exp(nz)-\exp((n-1)z)) \\ = \frac{n}{n^n} (n^n - (n-1)^n) \\ = n \left(1-\left(1-\frac{1}{n}\right)^n\right).$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .