Skip to main content

Questions tagged [coupon-collector-problem]

In probability, the coupon collector's problem models "collect all the coupons and win" contests. In its simplest form, suppose n distinct types of coupon are equally likely to occur: what is the expected number of coupons we must draw to collect at least one of each type?

Filter by
Sorted by
Tagged with
43 votes
7 answers
21k views

How often do you have to roll a 6-sided die to obtain every number at least once?

I've just played a game with my kids that basically boils down to: whoever rolls every number at least once on a 6-sided die wins. I won, eventually, and the others finished 1-2 turns later. Now I'm ...
Jonas's user avatar
  • 1,678
34 votes
2 answers
7k views

How many stickers do I need to complete my FIFA Panini album?

I'm playing the FIFA Panini Online Sticker Album, which is an Internet adaption of the classic Panini albums that are usually published for the soccer world cup, European championship, and possibly ...
Vidar S. Ramdal's user avatar
8 votes
1 answer
581 views

Mars attack (probability to destroy $n$ spaceships with $k \cdot n$ missiles)

Suppose Earth has been attacked by $n$ Martian spaceships and suppose that we have $m=k \cdot n$ missiles to release against the $n$ spaceships. The probability to hit and destroy each spaceship by ...
will198's user avatar
  • 669
5 votes
1 answer
378 views

Probability associated with experiencing all outcomes

Assume last year I commuted to work in a taxi, and suppose if there are $n$ taxis in the fleet I used. If I took one of these taxis every trip at random and with replacement, then what is the number ...
Vinay's user avatar
  • 81
20 votes
3 answers
4k views

Estimating population size from the frequency of sampled duplicates and uniques

There is a web service where I can request information about a random item. For every request each item has an equal chance of being returned. I can keep requesting items and record the number of ...
hoju's user avatar
  • 300
15 votes
3 answers
2k views

Estimating n in coupon collector's problem

In a variation on the coupon collector's problem, you don't know the number of coupons and must determine this based on data. I will refer to this as the fortune cookie problem: Given an unknown ...
goweon's user avatar
  • 253
10 votes
2 answers
5k views

Is there a formula for a general form of the coupon collector problem?

I stumbled across the coupon collectors problem and was trying to work out a formula for a generalization. If there are $N$ distinct objects and you want to collect at least $k$ copies of each of ...
nickponline's user avatar
9 votes
1 answer
394 views

Intuition about the coupon collector problem approaching a Gumbel distribution

The coupon collector's problem Let there be $n$ different types of coupons and we try to collect all of the types. We do this by independent random draws of coupons in which each type of coupon has an ...
Sextus Empiricus's user avatar
5 votes
1 answer
437 views

How many times, in expectation, am I fetching a random sample from a predefined discrete probability distribution of elements?

As part of a simulation that I'm working on, I have a probability distribution over $n$ elements, from which I have to sample a set $S$ of size $m$. That is, each element $e \in S$ must be unique [1]...
PhD's user avatar
  • 14.7k
23 votes
4 answers
5k views

What is a tight lower bound on the coupon collector time?

In the classic Coupon Collector's problem, it is well known that the time $T$ necessary to complete a set of $n$ randomly-picked coupons satisfies $E[T] \sim n \ln n $,$Var(T) \sim n^2$, and $\Pr(T &...
David's user avatar
  • 343
5 votes
1 answer
4k views

Probability of selecting each item at least once when sampling with replacement [duplicate]

Sampling with replacement $N$ items from $K$, where $N \geq K$, what is the probability that each item in $K$ is selected at least once? For example, from $10,000$ individuals, what is the ...
not_my_birthday's user avatar
5 votes
1 answer
621 views

Distribution based on rate of distinct values

I am investigating the following problem: I have a large set of values, many of which are repeated. Measuring the number of distinct (or unique) values shows that their number grows much slower than ...
alexfernandez's user avatar
16 votes
1 answer
2k views

Expected numbers of distinct colors when drawing without replacement

Consider an urn containing $N$ balls of $P$ different colors, with $p_i$ being the proportion of balls of color $i$ among the $N$ balls ($\sum_i p_i = 1$). I draw $n \leq N$ balls from the urn without ...
a3nm's user avatar
  • 707
9 votes
1 answer
431 views

Multinomial distribution conditional on number of distinct items

I want to sample from the integers $\{1, \dots, k\}$ with probabilities $\{ p_i \}_{i=1}^k$, with replacement, until I see $m$ distinct elements (call that $n$ times). You can view the distribution I ...
Danica's user avatar
  • 25k
7 votes
1 answer
1k views

In the coupon collector's problem with group drawings, why does the probability decrease with increasing samples?

My son is collecting Panini stickers from one of their football albums, where there are 472 stickers in total, and you can buy them in packs of 5 (no duplicates within those 5). You can also buy any ...
Timothy Jones's user avatar
6 votes
1 answer
560 views

How many random permutations to cover all possible permutations?

I have code that generates a random permutation. In my case, a permutation consists of N binary features, and each of the N features is set or unset randomly. How many times must I generate a random ...
Tyro's user avatar
  • 151
5 votes
1 answer
594 views

Continuous Version of Coupon-Collector Problem

Suppose I get in an elevator every morning and am in it for exactly one minute. A continuous loop of music plays in the elevator and is 10 minutes long. If my daily arrival time is uniform in the ...
soakley's user avatar
  • 4,596
5 votes
2 answers
1k views

Expectation of collecting stickers in groups

I saw this article about the expected number of stickers required to complete the Panini Euro 2016 album, where stickers are sold in packets of 5 distinct stickers. The author presents the case where ...
Timothy Jones's user avatar
5 votes
1 answer
2k views

Number of expected turns to get $k$ distinct numbers

We have a random number generator, which generates random numbers from $1$ to $N$. Each number has an equal probability of occurring (equiprobable). Find the expected number of turns to get $k$ ...
Sak1sham's user avatar
4 votes
1 answer
182 views

An interesting problem - fishing distribution

I found an interesting problem (not homework) that I can't solve. Lake has 4 types of fishes (A, B, C, D) each with given probability to be caught (0.1, 0.2, 0.3, 0.4). We fish until we catch at least ...
Milica's user avatar
  • 43
4 votes
1 answer
109 views

Finding a discrete distribution for the minimum number of times needed for all events to occur

Is there a distribution that describes the number of trials before all the events of a random variable with a discrete uniform distribution occurs? Examples: The number of rolls before getting all ...
Manuel Sapage's user avatar
3 votes
1 answer
104 views

How many samples do I need to take to expect I have seen (x%, say 99%) of the finite population?

Let's say I have balls numbered 1 to 100 in an urn. Every time I pick one at a random, record it as seen and put it back in the urn. How many such picking do I have to perform if I expect to see at ...
Vijay's user avatar
  • 133
1 vote
1 answer
104 views

Need help with expected value calculation in coupon collectors in coupon collectors variant

I am revisiting a question I asked previously with a slight caveat. In my new situation, I am considering the marbles to always be attached to the same neighbors. Hopefully this will be clearer with a ...
jordanlgraves's user avatar
1 vote
1 answer
313 views

How many times I need to draw k items from a list of n items to get a probability P that each item is selected at least once? [duplicate]

I have seen a few related questions but not exactly what I am looking for (in particular this and this) I think. I may be missing something since I am only a beginner at these counting problems. I am ...
LasEspuelas's user avatar