The Ticket-Collector's Problem

[Agent Smith]

The ticket-collector's problem: Assume there are n different tickets you can collect, these tickets are found in boxes of a product (some boxes maybe empty i.e. have no tickets in them). There are therefore n + 1 different possibilities. Each box has the same probability for these n + 1 possibilities i.e. each box contains either no ticket or 1 ticket (one of the n). What is the average number of boxes that have to be purchased to ensure you collect all tickets. If collect them all you win a prize, that's how it usually works.

How do we solve this problem?

The easiest and dumbest way to find the answer is to use a random number generator. Assign each ticket + no ticket a number from 1 to n + 1 and carry out a simulation. Conduct a (large) number of simulations and find the average of the number of attempts (purchases) that have to be made to acquire all n tickets.

Wikipedia has an article on this but I couldn't understand it.

Here's how I attacked the problem:

Let the number of tickets = n = 4
We have n + 1 possibilities (counting empty boxes) = 4 + 1 = 5

For 4 boxes, we see total number of permutations possible = $5^4 = 625$
The number of ways we can collect all 4 tickets = $^4 C_4 \times^4 P _4 = 24$
Probability of getting all tickets in just 4 tries = P(four) = $\frac{24}{625}$

For 5 boxes, we see that there are $5^5 = 3125$ possibilities (repetitions are possible)
In how many ways can we "win" (get all 4 tickets)? $^5 C_4 \times ^4 P_4 \times ^4 P_1 = 480$
Probability of getting all tickets in just 5 tries = P(five) = $\frac{120}{3125}$

For 6 boxes, total possibilities = $5^6$
Win possibilities = $^6 C_4 \times ^4 P_4 \times ^4 P_2$
Probability of getting all tickets in just 6 tries = P(six) = $\frac{^6 C_4 \times ^4 P_4 \times ^4 P_2}{5^6}$

In general, $P(x) = \frac{^x C_4 \times ^4 P_4 \times ^x P_{x - 4}}{5^x}$

Looks like I'm calculating the probability of getting all n tickets in exactly $x$ attempts/purchases.

What do I do with these probabilities?
If random variable = $X$ = the expected number of purchases to "win" then, ...
$E(X) = P(four) \times 4 + P(five) \times 5 + P(six) \times 6 + ... + P(x) \times x$?

Help!

 

[Steven G]

Think of the problem as follows. You have a container with n balls in it (or if you prefer, n+1 balls) numbered from 1 to n. All balls are the same size. You pick a ball, record its number and then replace it. Repeat. Eventually, you will have picked all n balls. Can you now find the average number of trials for picking all n balls?

 

[Agent Smith]

Think of the problem as follows. You have a container with n balls in it (or if you prefer, n+1 balls) numbered from 1 to n. All balls are the same size. You pick a ball, record its number and then replace it. Repeat. Eventually, you will have picked all n balls. Can you now find the average number of trials for picking all n balls?

It looks like I have a series on my hands; it looks like a converging series too. Is there some way of finding the sum?

 

[mmm4444bot]

It looks like I have a series on my hands; it looks like a converging series too.

Please show us the series that you have in mind. If you can't, then explain why you think it's a series.

Please explain why you believe the series converges.

In other words, please be complete.
$\;$

 

[Agent Smith]

Here's how I attacked the problem:

Let the number of tickets = n = 4
We have n + 1 possibilities (counting empty boxes) = 4 + 1 = 5

For 4 boxes, we see total number of permutations possible = $5^4 = 625$
The number of ways we can collect all 4 tickets = $^4 C_4 \times^4 P _4 = 24$
Probability of getting all tickets in just 4 tries = P(four) = $\frac{24}{625}$

For 5 boxes, we see that there are $5^5 = 3125$ possibilities (repetitions are possible)
In how many ways can we "win" (get all 4 tickets)? $^5 C_4 \times ^4 P_4 \times ^4 P_1 = 480$
Probability of getting all tickets in just 5 tries = P(five) = $\frac{120}{3125}$

For 6 boxes, total possibilities = $5^6$
Win possibilities = $^6 C_4 \times ^4 P_4 \times ^4 P_2$
Probability of getting all tickets in just 6 tries = P(six) = $\frac{^6 C_4 \times ^4 P_4 \times ^4 P_2}{5^6}$

In general, $P(x) = \frac{^x C_4 \times ^4 P_4 \times ^x P_{x - 4}}{5^x}$

Looks like I'm calculating the probability of getting all n tickets in exactly $x$ attempts/purchases.

What do I do with these probabilities?
If random variable = $X$ = the expected number of purchases to "win" then, ...
$E(X) = P(four) \times 4 + P(five) \times 5 + P(six) \times 6 + ... + P(x) \times x$?

Help!

Please show us the series that you have in mind. If you can't, then explain why you think it's a series.

Please explain why you believe the series converges.

In other words, please be complete.
$\;$

 

[Agent Smith]

Please show us the series that you have in mind. If you can't, then explain why you think it's a series.

Please explain why you believe the series converges.

In other words, please be complete.
$\;$

$P_n$ = probability of getting all tickets in exactly $n$ trials. $n \geq \text{number of tickets, N}$

Average number of trials to get all tickets = A = E(X), where X is the random variable for the number of trials

$E(X) = P_N \times N + P_{N + 1} \times (N + 1) + P_{N + 2} \times (N + 2) + \dots$ ?

As $n \to \infty, P_n \to 1$. Is this not convergence? Non liquet.

 

[Agent Smith]

To those who want to know the answer:

With n tickets, the number of tries = $\displaystyle n(\ln n + \gamma)$

 

[mario99]

To those who want to know the answer:

With n tickets, the number of tries = $\displaystyle n(\ln n + \gamma)$

What is $\gamma$?

 

[Agent Smith]

What is $\gamma$?

Euler-Mascheroni constant.

 

[mario99]

Euler-Mascheroni constant.

Beautiful. And how did you figure out the answer?

 

[Agent Smith]

Beautiful. And how did you figure out the answer?

Someone posted in on another forum. I wish I had figured it out myself, but I lack the basic ingredients to cook that dish, if you catch my drift. I hope it's not wrong. I ran some simulations, 1000 for every n from 1 to 28 or 30 I forget and the formula checks out.