3
$\begingroup$

I'm struggling with the following discrete probability problem. I've managed to solve it halfway through for its general case in quite an ugly way, but not for the specific case in the problem statement.


A card collector wants to complete a collection that comprises $n$ distinct cards. Cards are sold in packs of $k$ distinct cards ($k \le n$). Let $X$ be the random variable representing the (minimum) number of packs he has to buy to complete the collection.

What's $\Pr (X = x)$ for arbitrary $n$ and $k$?

Prove that, for arbitrary $n​$ and for $k=1​$, $$\mathbb{E}(X) = n\sum_{i=1}^n \frac{1}{i}\ .$$

$\newcommand{\deq}{\stackrel{\scriptstyle def}{=}}$

My attempt

First we'll count the number of possible combinations of cards when buying exactly $x\in\mathbb{N}$ packs such that their union forms the complete col·lection.

We'll represent the set of $n​$ cards with the set $[n] = \{1,\ldots,n\}​$. For each $c\in [n]​$, define the set $$ A^x_c = \{(P_1,\ldots,P_x) \mid \forall i \in [x]\quad P_i \subseteq [n]\ \land \ |P_i| = k \ \land \ c \notin P_i \}\ , $$ that is, the set of $x$-tuples of packs such that $c$ isn't in any of them.

Note that $|A^x_c| = {n - 1 \choose k}^x$, since for each pack, there are ${n-1 \choose k}$ possible combinations (we can't choose card $c$. By the same reasoning, $$ \left|\bigcap_{i\in I \subseteq[n]} A^x_i\right| = {n - |I| \choose k}^x $$

Then the number of ways to get $x$ packs such that one completes the collection is, by the inclusion-exclusion principle (where the complement is considered in the set of all $x$-tuples of packs), $$ \left|\left(\bigcup_{c = 1}^n A^x_c\right)^\complement\right| = \sum_{I \subseteq [n]} (-1)^{|I|} \left|\bigcap_{c \in I} A_c^x \right| = \sum_{I \subseteq [n]} (-1)^{|I|} {n - |I| \choose k}^x = \sum_{i = 0}^n (-1)^{i} {n \choose i} {n - i \choose k}^x \,. $$ Since the total number of $x$-tuples of packs is ${n \choose k}^x$, the probability to complete the collection having bought exactly $x$ packs is $$ F(x) \deq \frac{\sum_{i = 0}^n (-1)^{i} {n \choose i}{n - i \choose k}^x}{{n \choose k}^x }\,. $$ Now, consider the process of buying packs until we complete the collection, and no more. Then the previous expression is actually the cumulative probability — the probability of having stopped at $x$ or less packs.

So the actual probability is $$ \Pr(X = x) = F(x) - F(x - 1) = \frac{\sum_{i = 0}^n (-1)^{i} {n \choose i}{n - i \choose k}^x}{{n \choose k}^x } - \frac{\sum_{i = 0}^n (-1)^{i} {n \choose i}{n - i \choose k}^{x-1}}{{n \choose k}^{x-1} } = \\ = \frac{\sum_{i = 0}^n (-1)^{i} {n \choose i}{n - i \choose k}^{x-1} \left[ {n - i \choose k} - {n \choose k} \right]}{{n \choose k}^x } \,. $$ Applying this for $k = 1$, we get $$ \Pr(X = x) = \frac{\sum_{i = 0}^n (-1)^{i} {n \choose i}(n-i)^{x-1} \left[ (n - i) - n \right]}{n^x } = \\ = \frac{\sum_{i = 0}^n (-1)^{i+1} {n \choose i}(n-i)^{x-1} i}{n^x } = \frac{1}{n} \sum_{i = 1}^n (-1)^{i+1} {n \choose i}\left(\frac{n-i}{n}\right)^{x-1}i\,. $$ Now, I tried to calculate $\mathbb{E}(X)$ as follows. Even having supposed that the expected value converges, there are a couple of steps involving infinite sums which I'm not sure are totally valid. $$ \begin{multline*} \mathbb{E}(X) = \sum_{x = 1}^\infty x \cdot \Pr(X = x) = \sum_{x = 1}^\infty x \cdot\frac{1}{n} \sum_{i = 1}^n (-1)^{i+1} {n \choose i}\left(\frac{n-i}{n}\right)^{x-1}i = \\ = \frac{1}{n} \sum_{i = 1}^n \sum_{x = 1}^\infty x \cdot (-1)^{i+1} {n \choose i}\left(\frac{n-i}{n}\right)^{x-1}i = \frac{1}{n} \sum_{i = 1}^n (-1)^{i+1} {n \choose i} i \cdot \sum_{x = 1}^\infty x \cdot \left(\frac{n-i}{n}\right)^{x-1} = \\ = \frac{1}{n} \sum_{i = 1}^n (-1)^{i+1} {n \choose i} i \cdot \frac{1}{(1 - \frac{n - i}{n})^2} = n \sum_{i = 1}^n \frac{(-1)^{i+1}}{i}{n \choose i} \,. \end{multline*} $$


Now, I got stuck here since I don't know how to prove $$ \sum_{i = 1}^n \frac{(-1)^{i+1}}{i}{n \choose i} = \sum_{i=1}^n \frac{1}{i}\,, $$ which apparently is an identity.



Edit

For $k=1$, this can be solved, as is well known, by defining, for each $m \in \mathbb{N}$, $X_m$ as the random variable that gives the amount of cards you have to buy until you encounter a new one, having already got $m-1$ distinct cards.

Since $X_m \sim \mathrm{Geom}(\frac{n- m + 1}{n})$, we have $$ \mathbb{E}(X) = \mathbb{E}\left(\sum_{i = 1}^n X_i\right) = \sum_{i = 1}^n \mathbb{E}(X_i) = \sum_{i = 1}^n \frac{n}{n-i+1} = n \sum_{i=1}^n \frac{1}{i}\,. $$

In any case, I still would like to know if the more general approach above is correct, and how to prove the identity.

$\endgroup$
  • $\begingroup$ For $k=1$ this is the classic coupon collector's problem. Please do a in-site or Google search. At this point I don't have much to say for general $k$. $\endgroup$ – Lee David Chung Lin Mar 10 at 17:15
  • $\begingroup$ The term $\sum^n_{i=1} {1 \over i}$ is known as the $n$th Harmonic number, and a lot is known about them. In particular, the identity you want actually appears (with a proof via integration) in the wikipedia article: en.wikipedia.org/wiki/Harmonic_number#Calculation $\endgroup$ – antkam Mar 19 at 19:25
3
$\begingroup$

I haven't checked it very closely, but I don't see anything glaringly wrong. As to the identity, we can prove it by induction. The basis is clear. Suppose the identity holds for $n.$

$$\sum_{i=1}^{n+1}{(-1)^{i+1}\over i}{n+1\choose i}= \sum_{i=1}^{n+1}{(-1)^{i+1}\over i}{n\choose i}+ \sum_{i=1}^{n+1}{(-1)^{i+1}\over i}{n\choose i-1}\tag{1} $$ The first sum on the right of $(1)$ is $\sum_{i=1}^n{1\over i}$ by the induction hypothesis, since ${n\choose n+1}=0,$ so if we can show that the second sum on the right is ${1\over n+1},$ we will be done.

The binomial theorem gives $$\sum_{i=0}^n(-1)^i{n\choose i}x^i=(1-x)^n$$ Integrate both sides from $0$ to $1$:$$ \begin{align} \sum_{i=0}^n(-1)^i{n\choose i}\int_0^1x^i\mathrm{dx}&=\int_0^1(1-x)^n\mathrm{dx}\\ \end{align}$$ and evaluate the integrals to complete the proof.

I feel like there ought to be a way to prove the identity directly from the binomial theorem, without resorting to induction, but my attempts didn't work. I'm probably just holding my head at the wrong angle.

$\endgroup$
1
$\begingroup$

Here is another way to prove the identity in question. Consider the integral $$\int_0^{\infty} [1-(1-e^{-x})^n] \; dx$$ We can evaluate the integral in two different ways. First, using the Binomial Theorem, $$\begin{align} \int_0^{\infty} [1-(1-e^{-x})^n] \; dx &= \int_0^{\infty} \left[ 1-\sum_{i=0}^n (-1)^i \binom{n}{i} e^{-ix} \right] \;dx \\ &= \sum_{i=1}^n (-1)^{i+1} \binom{n}{i} \int_0^{\infty} e^{-ix} \; dx \\ &= \sum_{i=1}^n \frac{(-1)^{i+1}}{i} \binom{n}{i} \tag{1} \end{align}$$ Second, using the substitution $u = 1 - e^{-x}$ and the formula for the sum of a geometric series, $$\begin{align} \int_0^{\infty} [1-(1-e^{-x})^n] \; dx &= \int_0^1 \frac{1-u^n}{1-u} \; du \\ &= \int_0^1 \sum_{i=0}^{n-1} u^i \; du \\ &= \sum_{i=0}^{n-1} \frac{1}{i+1} \\ &= \sum_{i=1}^{n} \frac{1}{i} \tag{2} \\ \end{align}$$ Equating $(1)$ and $(2)$, we have $$ \sum_{i=1}^n \frac{(-1)^{i+1}}{i} \binom{n}{i} = \sum_{i=1}^{n} \frac{1}{i}$$

$\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.