0
$\begingroup$

Suppose you have a set of $n$ balls, $k$ of them are black and the other are white. At each step, you take one ball at random, without replacement.

How much steps do you need to get all the $k$ black balls, in expectation?

Actually, I am fine with an upper bound on this expectation rather than an exact formula.

Motivation. The question I try to answer is the following: Given a polynomial of degree $d$ over a finite field $\mathbb F_q$, say with exactly $d$ distinct roots in $\mathbb F_q$, how long does it take you to discover all these roots if you tste all the $q$ elements in random order. This is the exact same question with $k=d$ and $n=q$.

$\endgroup$
2
  • $\begingroup$ Well, the polynomial with roots can have repeated roots. Do you mean $d$ distinct roots? $\endgroup$ Feb 6, 2015 at 16:33
  • $\begingroup$ Precisely, I assume that the polynomial is a product of distinct linear polynomials: it has no repeated roots, and it has as many (distinct) roots as its degree. $\endgroup$
    – Bruno
    Feb 6, 2015 at 16:36

1 Answer 1

1
$\begingroup$

The expected value is:

$$\frac{\sum_{j=k}^n j\binom{j-1}{k-1}}{\binom{n}{k}}$$

Now: $$j\binom{j-1}{k-1} = \frac{j!}{(j-k)!(k-1)!} = k\binom{j}{k}$$ and:

$$\sum_{j=k}^n \binom{j}{k} =\binom{n+1}{k+1}$$

So the expected value is:

$$\frac{k\binom{n+1}{k+1}}{\binom{n}{k}} = \frac{k(n+1)}{k+1}$$

I'm guessing there is a more "intuitive" way of showing this result.

$\endgroup$

You must log in to answer this question.

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