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
1
vote
0
answers
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 (...
5
votes
2
answers
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
8
votes
2
answers
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
11
votes
1
answer
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
0
votes
1
answer
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
1
answer
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
5
votes
1
answer
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
0
votes
1
answer
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 ...
0
votes
0
answers
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
4
votes
1
answer
66
views
Probability that N i.i.d. draws from a multinomial distribution have made all events appear
Consider a multinomial distribution $\mathbb{P}$ on $S$ states $\{s_1,\dots,s_S\}$ where $S\in \mathbb{N}$ and $S\geq 2$, with probabilities $\mathbb{P}(s_i)=:p_i$. Now consider $N$ i.i.d. draws $X_1,...
- 6,315
1
vote
1
answer
32
views
Minimum Samples to Identify Box (Coupon Collector Extension)
I am thinking on the follow probabilistic problem setting:
Say we have $n$ boxes, each of which has an affiliated set of $k$ balls. We aim to distribute these balls across the boxes in the most fair ...
- 57
0
votes
2
answers
44
views
Average number of collected coupons problem
I have the following problem.
There are two kinds of coupons, $A$ and $B$. Each type has the same probability to be present in a box of cookies. You want to collect a complete set of coupons where ...
- 532
1
vote
1
answer
49
views
Why is the expected number of draws given $k$ coupons so similar to the expected number of draws required to obtain $k$ coupons?
Regarding the coupon collector’s problem, the question Expected size of collection based on number of uniques asks for the expected value of the number $N$ of draws made, given that $k$ out of $m$ ...
- 216k
0
votes
1
answer
65
views
Number of rolls of a single die until both a 6 and an odd number appear
I have a probability question. The problem goes: John (J) and Max (M) are rolling a die (one die together). John wants to see an odd number on the die and Max wants to see a 6.
X ... number of rolls ...
- 11
1
vote
2
answers
56
views
How do I approach the coupon collector's problem if multiple items belong to different "families"?
Say we roll a fair six-sided dice, and our goal is to roll every number at least once. The expected number of rolls is fairly simple: we find $E(x)=\int_0^\infty(1-(1-e^{-\frac{t}{6}})^6)dt=6(1+\frac{...
- 1,137
1
vote
0
answers
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
2
votes
1
answer
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
1
answer
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
2
votes
1
answer
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 ...
12
votes
2
answers
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
8
votes
3
answers
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 (...
- 237
2
votes
1
answer
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
2
answers
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 ...
- 57
0
votes
0
answers
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
0
votes
0
answers
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 ...
- 1
6
votes
3
answers
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
0
votes
0
answers
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
0
answers
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
4
votes
3
answers
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
0
votes
0
answers
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
6
votes
1
answer
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
1
answer
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
9
votes
1
answer
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
6
votes
1
answer
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
0
votes
1
answer
111
views
Coupon Collector's Problem with Subset
I have a variation of the Coupon Collector's Problem which can be state as follows.
"Given a set $N$ of $n$ different kinds of coupons and a subset $K\subset N$ of $k$ kinds of coupons, with $k&...
user952500
-1
votes
1
answer
75
views
Probability problems associated with collecting all types of cards [closed]
When a person buys 15 boxes, there are 5 cards in the box, and the types of the 5 cards are different from each other (however, the relationship between the cards in the box and other cards in other ...
0
votes
1
answer
49
views
Number of times of an experiment needed to all balls numbers to be written down
Please help me with the following probability problem and give some reference how to deal with such problems. Thank you.
In a pool, we have $200$ balls with numbers from $1$ to $200$. Each time, we ...
- 5,080
1
vote
1
answer
57
views
Finding the CDF of the Coupon Collectors Problem with non uniform probabilities
Given a set of $n$ coupons with draw probabilities $p_1, p_2, ..., p_n$ such that $$\sum_{i=1}^{n} p_i = 1$$ What is the probability $P(X \le x)$ of having completed a full set of coupons in fewer ...
- 31
2
votes
1
answer
163
views
Finding the CDF for a Modified Coupon Collector Problem with Bernoulli Trials
I'm working with a problem that combines the coupon collector problem with Bernoulli trials and I'm not sure how to work out the probability function.
In the classic coupon collector problem we get a ...
- 31
0
votes
1
answer
85
views
Coupon collector problem with unequal draw probabilities
This is an instance of the "coupon collector's problem" in which not all the "coupons" have the same probability of appearance. Here the "coupons" are boxes of cereal, ...
0
votes
1
answer
42
views
Expected probability that $i$-th coupon is not chosen after picking $M$ coupons
There are $N$ distinct types of coupons in a cereal boxe and each type, independent of prior selections, is equally likely to be in a box. You draw $M$ coupons from the cereal box. What is the ...
- 275
0
votes
2
answers
35
views
Intersection of events in Coupon Collector Problem $ P(A_i \cap. A_j) $
I am studying a variation of the coupon collector problem where there are N coupons, and each coupon has a probability $p_i$ of appearing with $i = 1,2,3 ... N$. I have to find $P(T=n)$ where T is a ...
- 89
3
votes
0
answers
87
views
How many happy meals do you need to buy to collect all 25 different holos from the Pokemon 25th anniversary promotion? [duplicate]
So Pokemon and McDonald's recently had a promotion where with each Happy Meal, there would be a pack of Pokemon cards included. Each pack contains a holo card. There are 25 holo cards in all. How many ...
- 31
0
votes
1
answer
57
views
Find the probability distribution of minimum number of draws to get balls of each color in an urn
An urn contains 10 black 10 white and 10 blue balls . Balls are drawn randomly with replacement Let T be the minimum number of draws required to get balls of all different colors .Find distribution of ...
2
votes
1
answer
44
views
Expected size of collection based on number of uniques
I have been thinking about this for some time. Imagine there are fortune cookies. Each of them can carry a random quote (1 out of total 100 possible quotes). After buying N cookies, we stopped and ...
- 148
1
vote
1
answer
33
views
Finding the distribution of the number of tosses it takes to observe all 6 sides of a fair die
I found this question on http://www.cis.jhu.edu/~xye/papers_and_ppts/ppts/SolutionsToFourProblemsOfRollingADie.pdf. It is Q(d):
Roll x times until getting all the faces from “1” to “6”, what’s the ...
- 275
2
votes
1
answer
185
views
double dixie cup problem - upper bound
There is a set of $n$ cards to collect, in each pack there is exactly one card. The sets are distributed uniformly among the packs (i.e. the probability for obtaining a particular card is $\frac{1}{n}$...
- 95
0
votes
0
answers
53
views
Coupons collectors problem extended
Given $n$ distinct coupons, each package contains exactly one of the $n$ coupons with the probability $\dfrac{1}{n}$. I'm interested in the expected number of packages one has to buy so that one has ...
- 313
2
votes
1
answer
95
views
Probability of exactly 1 given everything appears
I'm trying to figure out the following question, and I'm stuck! It comes from an old PUMaC problem with a partial solution (there's a typo in the one provided on Stack Exchange as well):
Stack Post:
...
- 361
2
votes
2
answers
121
views
Probability of drawing at least J cards out of I cards of interest from a deck of N cards within D draws with replacement
Given a regular deck of 52 playing cards, if you draw from the deck 10 times with replacement, what is the probability that you have drawn at least 3 different aces (any of the 4 aces) at least once ...
