2
$\begingroup$

The question is as follows: Consider an urn of n distinct objects. At each time, m (m < n) objects are drawn randomly at once. The objects obtained are noted and then placed back in the urn. What is the expected number of draws I have to make until all of the objects have drawn at least once?

$\endgroup$
  • $\begingroup$ Can we find the expected number of draws before a particular object is drawn, and then use linearity of expectation somehow? $\endgroup$ – G Tony Jacobs Aug 19 '17 at 20:12
  • $\begingroup$ @GTonyJacobs I am not sure about it. What do you have in mind? $\endgroup$ – lebesgue Aug 19 '17 at 20:27
  • $\begingroup$ Well, any particular object has probability $m/n$ of being chosen on one draw. The expectation for how many draws it will take to be chosen is thus $n/m$. That's the same for each object..... does that get us closer to the answer? $\endgroup$ – G Tony Jacobs Aug 19 '17 at 20:38
  • $\begingroup$ @GTonyJacobs the number of draws could be as large as possible. How can you express it as sum of random variables? $\endgroup$ – lebesgue Aug 19 '17 at 20:40
  • $\begingroup$ The support of the distribution in question would be from $\lceil n/m\rceil$ to infinity... $\endgroup$ – G Tony Jacobs Aug 19 '17 at 20:42
2
$\begingroup$

Let's take a look at a random draw log. In each line, we have all $n$ objects, where $1$ means it has been drawn and $0$ means it hasn't been. Here, $n=5$ and $m=3$:

1 1 1 0 0
0 1 1 0 1
1 0 1 0 1
0 1 1 1 0

Now we will try to find the probability, that all objects have been drawn after $k$ draws. This is achieved when each object has been drawn at least once. We can denote this as $1-\text{[probability that it has never been drawn]}$. In each draw, there is probability $\frac{n-m}{n}$ that the object isn't drawn, so after $k$ draws, there is probability $\left(\frac{n-m}{n}\right)^k$ that the object hasn't been drawn.

Okay, so we know that each object is after $k$ draws drawn at least once with probability $1-\left(\frac{n-m}{n}\right)^k$. If we have $n$ objects, then probability, that all of them have been drawn at least once after $k$ draws is obviously $\left(1-\left(\frac{n-m}{n}\right)^k\right)^n$.

If we want to know, what is the probability, that we got the state "each object has been drawn at least once" exactly after $k$ draws, we need to subtract probability, that it was achieved after $k-1$ draws or sooner: $$P_{\text{exactly after $k$}}=\left(1-\left(\frac{n-m}{n}\right)^k\right)^n-\left(1-\left(\frac{n-m}{n}\right)^{k-1}\right)^n$$

Now if you lok at definition of expected value, our expected number of draws is sum of expressions $k\times\text{[probability of ending exactly after $k$]}$. Namely, $$\sum_{k=0}^\infty k\cdot\left(\left(1-\left(\frac{n-m}{n}\right)^k\right)^n-\left(1-\left(\frac{n-m}{n}\right)^{k-1}\right)^n\right)$$

And this can be simplified to: $$\sum_{k=0}^\infty 1-\left(1-\left(\frac{n-m}{n}\right)^k\right)^n$$

I'm convinced it can't be simplified any more (and WolframAlpha agrees). If you're interested in any specific step of this solution, just write in comments.

Edit: My answer is not totally correct, see comments.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This doesn't work for $n=2$, $m=1$. That case is easy to calculate by hand, and the expected value is $3$, but this formula gives $\frac83$. $\endgroup$ – G Tony Jacobs Aug 20 '17 at 0:21
  • $\begingroup$ Argh, you're right. The problem is that for $k=1$ the real probability is $0$, but my approach gives $\left(\frac{n-m}{n}\right)^n$, because it assumes average $m$ drawn objects, but the problem states exactly $m$ objects. So my solution is right for this variation of the problem. Maybe for large number the two results converge. (?) $\endgroup$ – Puding Aug 20 '17 at 9:29
2
$\begingroup$

This answer is a work in progress.

Case 1: $m=n-1$

In this case, all but one are drawn on the first draw, and we're just looking for the expected number of attempts to get the last one. Since the probability of getting it on any particular draw is $\frac{n-1}{n}$, the expected number of draws after the first to get it is $\frac{n}{n-1}=1+\frac{1}{m}$. Adding to this the original draw, we have $E=2+\frac{1}{m}$.


Case 2: $m=1$

The probability that the number of draws required is $k$ is given by $n\times\frac1n\times K$, where $K$ is the probability that the other $n-1$ objects were all drawn in the first $k-1$ draws. (The first $n$ picks the final object drawn, and the $\frac1n$ gives us that it shows up in draw number $k$.) We can write a formula for $K$ using inclusion-exclusion:

$$K=\frac{(n-1)^{k-1} - \binom{n-1}{n-2}(n-2)^{k-1}+\binom{n-1}{n-3}(n-3)^{k-1}+\cdots + (-1)^n\binom{n-1}{1}(1)^{k-1}}{n^{k-1}}$$

Letting $E_n$ denote the resulting expected value for $n$ objects drawn $m=1$ at a time, we have:

$$E_2=3, E_3=\frac{11}{2}, E_4=\frac{25}{3}, E_5=\frac{137}{12}, E_6=\frac{147}{10}$$

I don't yet have a general formula for $E_n$ in the $m=1$ case, but it seems possibly tractable.

Edit: The case $m=1$ is the Coupon collector's problem, which is a wheel I'm going to now stop re-inventing. We have $E_n=n(1+\frac12+\cdots+\frac1n)$, which confirms the answers I'd found so far.


Another approach: The number of objects not yet chosen after $k$ steps is approximately $U_k=n\cdot\left(\frac{n-m}{n}\right)^k$. (That value is actually precise for $k=0$ and $k=1$, and approximate after that.) We might expect all objects to have been chosen at some point where $U_k<1$. How far below $1$ is not entirely clear, but maybe we can get an idea by looking at cases where we know the answer. Thus, for $m=n-1$, we have $U_{E_n}=n\cdot\left(\frac1{n}\right)^{2+\frac1{n-1}}$. This quantity is $\frac14$ for $n=2$, and goes to $0$ as $n\to\infty$. On the other hand, for $m=1$, the quantity $U_{E_n}$ goes up from $\frac14$ and approaches $\frac12$ as $n\to\infty$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.