# Questions tagged [coupon-collector]

A famous problem of probability, where a person samples a set with replacement until every element of the set (i.e. each coupon) has been obtained at least once. Questions deal with the associated probability distribution, proof techniques, etc.

311 questions
Filter by
Sorted by
Tagged with
1 vote
27 views

### Finding an upper bound on the coupon collectors problem

Suppose I have $n^2\cdot \log^2 n+k$ pairs of boxes (each blue box has a corresponding red box), all independent and each having a coupon from the set $\{ 1,2,...,n\}$ with an equal probability (...
104 views

### Number of draws before you see all candies?

Recently, I thought of the following question: Suppose there are 5 candies in a bag - you choose two candies, and then put these two candies back in the bag (assume each candy has an equal probability ...
• 161
212 views

### Two artists want to paint all sand grains in 2 colors. They stop if one artist picks a grain already painted by the other. In mean how many picks?

Let $N$ be the (big) number of sand grains. Artist $B$ want to paint them blue. Artist $R$ want to paint them red. We start with all sand grains unpainted. They decide $B$ can start. $B$ picks a ...
• 225
287 views

### The coupon collector's most collected coupon

Suppose a coupon collector is collecting a set of $n$ coupons that he receives one-by-one uniformly at random. If the collector stops exactly when the collection is complete, we know the expected ...
• 217
38 views

### What is the general expression for the number of possible way to generate $k$ distinct number from $n$ sequentially?

What is the general expression for the number of possible way to generate $k$ distinct number from $n$ sequentially? For example, let's say I have $n$ numbers ranging from $1$ to $9$ and I want to ...
• 1
1 vote
63 views

### A “two-dimensional” generalization of coupon collectors problem

Suppose we have colored balls with numbers. There are $m$ colors and $n$ numbers (so there are $mn$ different kind of balls, appearing with equal probability). What’s the expectation of balls we need ...
• 219
184 views

### Coupon collectors problem, but kicking a ball around

The coupon collectors problem asks about the distribution of the number of coupons you'd need to collect in order to complete a collection. The coupons can have equal probabilities or unequal ...
• 5,565
59 views

### How many times must a pair of 6-sided dice be rolled until all sides appear at least once

This is problem 11 in "A Collection of Dice Problems" by Matthew Conroy. Let state i be the state that i different sides have appeared, then 6 is the state that all sides have appeared, make ...
51 views

### The expected number of meals to collect all four designs of the cushion.

A fast food restaurant chain releases cushions in 4 safari animal hoodie designs in addition to your combination meal. A fan of the cushions is determined to collect them all, and suppose one of the ...
• 47
66 views

• 1,137
1 vote
55 views

### Is there a closed form formula for this function of two positive integers?

Let $n$ and $k$ be positive integers. Suppose there are $n$ cards in a deck, and you want to collect at least $k$ of each card. A store sells these cards, but here is the catch: It is random which ...
• 13.6k
101 views

### Coupon Collector's Problem and Stirling numbers of the second kind: rationale

I have basic notions of probability and combinatorics, but I hadn't heard of Stirling numbers (or I forgot them 😐) until I recently fell into the Coupon Collector's Problem, and into the formula for ...
• 145
1 vote
66 views

### Permutations: play a song 3 times before all songs have played at least once.

A playlist has $10$ songs. Two musics players ($A$ and $B$) implement the "shuffle and repeat" feature a little differently. In $B$, no song will be played twice in a row, but it is possible ...
• 381
105 views

### Asymptotic Distance Between First Occurrences of Distinct Letters in Multiset Permutations

Consider a multiset consisting of $h$ copies of each of $n$ distinct letters. To each permutation, we assign a label, $\vec{T}$, whose components, $t_i$ are the positions (1-indexed) in the ...
267 views

### Average number of days to see all possible cards

My father and I go to the restaurant everyday, and each one of us needs to grab a card, which has a number from 1 to 600. I thought about registering every new card we see in a list, and a question ...
• 551
514 views

### I've clicked XKCD's "random" button k times and I've already seen all of them. What's the expected number of XKCD's I've seen?

This seems like a modification of the coupon collector's problem which can be stated as follows: There are $n$ coupons total to collect. Given that the past $k$ coupons seen I've already collected (...
160 views

### Coupon Collector Score

Suppose you have a non-uniform coupon collector problem. But, rather than quotas, each coupon gives you points. There are $n$ different groups of coupons, and the probability of receiving a coupon of ...
• 10.2k
1 vote
115 views

### Sampling without replacement expectation proof

Here is my problem and subsequent attempted proof: Assume we have $n$ different colored balls and $k$ of each color for a total of $nk$ balls. We want to draw from this set without replacement until ...
22 views

### Batched Urn/coupon problem

The problem setting is as follows. We have an initial collection (urn?) of $N$ different coloured balls - say $C$ distinct colours. The distribution of different colors is non-uniform and unknown. In ...
• 354
25 views

### Coupon Collector's Problem with loot boxes (more than one outcome each try, different drop rates)

Disclaimer: I am not a mathematician by any means and am just interested in the coupon collector's problem in terms of video games and drop rates. I want to know how many lootboxes must be opened in ...
194 views

### Upper bound of probability of not getting all values in independent draws

We draw $m$ uniform independent random values among $n$, with $m\ge n$. We consider the probability $p(m,n)$ that not all $n$ values have been drawn. We want an upper bound within a constant factor. ...
• 1,500
41 views

### Generalized coupon problem for intervals of size $L$

Assume that we are decoding a letter of length $G$ with pieces of size $L$. Each time we take a piece of size $L$ of the letter from some box with replacement (The probability of appearance of each of ...
• 3,507
1 vote
32 views

### Deducing expected value using asymptotic probability distribution (Coupon Collector's problem)

I am reading Erdős and Rényi's On a Classical Problem of Probability Theory, where they derive the asymptotic distribution for the Coupon Collector's problem of collecting at least one of every type ...
• 992
232 views

### Expected number of throws required so every face of die shows up

Here's a question from my probability textbook: A die is thrown until every face has turned up at least once. Show that on average $14{7\over{10}}$ throws will be required. The easy way to do this ...
• 1,345
21 views

### If I have a 1/171 chance of getting a certain item, and I need to collect all 171 items, what is the average number of attempts it will take? [duplicate]

I am playing a game in which I need to earn 171 unique items to earn a trophy. There is a guaranteed drop of one item after every match, and I can get duplicates. Each item has an equal chance of ...
• 1
84 views

### Modified coupon collector's problem, where you can trade off excess coupons

I am struggling with a variation of the coupon collector's problem. Suppose that we need to collect $n$ distinct coupons by buying boxes of toys, where each box contains one coupon with uniform ...
• 63
1 vote
94 views

### Variance of urn problem with replacement and color switching

Objective: I am trying to calculate the variance for each number of draws $k$ for an urn problem (analogous to coupon collector's). Problem description: Imagine a urn, initially completely filled with ...
• 125
203 views

### Suppose we have $N$ people. A random selection of $k$ of these people meet each day. What is the expected number of days until everyone has met?

I thought of this problem today and I'm not quite sure how it's solved. My idea is simply to use the definition of expectation: $$E[\text{# of days until everyone has met}] = \sum_{x=1} x \cdot p(x)$$ ...
• 91
210 views

### Coupon collectors derivation

Yesterday, a user posted the following derivation of the coupon collectors problem but unfortunately deleted his question: There are $n$ distinct characters one could obtain from a card package, ...
• 425
111 views

• 313