0
$\begingroup$

A company brings out a new set of $n$ collectible cards. The cards are made in equal number, so there is the same probability of any given card being in a random set. They are purchased one-by-one.

Question 1: If I buy $x$ cards, on average how many unique cards $(k)$ will I have? $k$ does not need to be a whole number.

Question 2: How large does x need to be that k/n is over y%?

Question 3: If I buy $x$ cards, what is the probability that I have $j$ unique cards. $j$ is a whole number.

EDIT: Thank you to all who have replied! As a first time poster, it is amazing to get so many helpful responses so quickly. I have learnt that this known as the coupon collector's problem. There is a very straightforward answer to the question, "What is the expected value of x needed to complete the set on n cards"

\begin{align} E[x]={}&x\sum_{i=1}^n\frac1i\;. \end{align}

I am struggling to find equations as simple as this to questions 1 and 2, so will post a second edit once I have them. On question 3 "user 4" kindly gave what I think is the right answer: \begin{align} \frac{n!}{(n-j)! n^x}{x \brace j} \end{align}

$\endgroup$
5
  • 4
    $\begingroup$ That's Coupon collector's problem. $\endgroup$ Feb 10 at 11:07
  • 1
    $\begingroup$ Does this answer your question? Expected time to roll all 1 through 6 on a die $\endgroup$
    – Peter O.
    Feb 10 at 12:15
  • $\begingroup$ Question 2 is unclear. There is no $x$ such that $\frac kn> y$ with certainty unless $y\le\frac1n$. May it be that you ask about the expected value of $x$ instead? $\endgroup$
    – user
    Feb 10 at 13:27
  • $\begingroup$ As the title and the multiple problems in the body of the Question are not consistent, it is perhaps unavoidable that the proposed duplicate target is not exact. The third part of the present Question is about a family of probability distributions, the chance of having exactly $j$ distinct cards after buying $x$ cards. I recommend looking at Probability Distribution in the Coupon Collectors Problem and the many linked Questions to be found there. $\endgroup$
    – hardmath
    Feb 10 at 23:52
  • $\begingroup$ Since no of the given references address the questions of OP, here is the answer to the 3rd question: $$\frac{n!}{(n-j)! n^x}{x \brace j}.$$ More interesting is the answer to the 1st question but the comment format is not suitable for it. $\endgroup$
    – user
    Feb 11 at 8:50
0
$\begingroup$

Q1:

Let us ask first what is the expected value of the binary event $X_i$ which value is $1$ if a certain card was bought at least once and 0 if it was not bought. Clearly the expected value is just the probability to buy the card in at least one of $x$ trials: $$ \mathsf E(X_i)=1-\left(\frac{n-1}n\right)^x.\tag1 $$ Now due to linearity of the expectation the expected number $k$ of unique cards bought at least once is: $$ k=\sum_{i=1}^n\mathsf E(X_i)=n\left[1-\left(\frac{n-1}n\right)^x\right].\tag2 $$

Q2:

As I already mentioned in a comment the question is ambiguous. If you mean the ratio $\frac kn$ it is given by (1).

Q3:

The probability can be computed as follows: $$ p_j(n,x)=\frac1{n^x}\binom nj j!{x \brace j}=\frac{n!}{(n-j)! n^x}{x \brace j},\tag3 $$ where ${x \brace j}$ is the Stirling number of the second kind

In the expression (3) $n^x$ counts the number of ways to dictribute $x$ labeled cards into $n $ labeled boxes with empty boxes being allowed, $\binom nj$ counts the number of ways to choose $j$ out of $n $ labeled boxes, and $j!{x \brace j}$ counts the number of ways to dictribute $x$ labeled cards into $j $ labeled boxes with empty boxes being not allowed. The cards are labeled by the order of their arrival. The boxes are labeled by the types of unique cards.

Observe that we factually proved the relation: $$ \sum_{j=1}^n jp_j(n,x)=n\left[1-\left(\frac{n-1}n\right)^x\right]. $$

$\endgroup$
2
  • $\begingroup$ How on earth did you manage to get a username called "user"?? $\endgroup$ Feb 21 at 12:34
  • 1
    $\begingroup$ Believe me. This is a much more frequent username than @BenjaminWang. :) $\endgroup$
    – user
    Feb 21 at 13:24

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.