Solving formulas for Coupon Collector's problem variant

76 Views Asked by At

I considered a modified version of the Coupon Collector's problem where there are $m$ transparent balls, $k$ different colors and $c$ balls of each color for a total of $n=ck+m$ balls in the urn.

I stop when I draw (without reimmision) a ball of each color and want to know the expected numbers of draws. I don't care about transparent balls that can be any number from $0$ to $m$.

The resolving formula is well known and states that:

$\displaystyle E = \sum_{i=1}^k (-1)^{i-1} \binom{k}{i} \frac{n+1}{ci+1}$

a friend however found another solving formula.

In python code it's straight forward (function returns a vector of elements whose sum is the expected value):

def Qkf(n, k, c):
    N = n+1
    D = c*k+1

    E = []
    for i in range(k):
       p = Fraction(N, D)
       E.append(p)

       N -= p
       D -= c

   return E

That can be translated into this succession:

$\displaystyle N_{i} = N_{i-1} \frac{c(k-i+1)}{c(k-i+1)+1} + \frac{n+1}{c(k-i+1)+1}$

with $N_0 = 0$ and $N_k$ the expected value I'm looking for.

Now, although these formulas seems quite different, their result matches exactly for every possible valid triplet I tried.

In other words it appears that:

$\displaystyle N_k(n, k, c) = E(n, k, c)$

So I suspect the succession can be simplified into the summation. I cannot however prove it.

Any ideas how to?