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.

Filter by
Sorted by
Tagged with
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 (...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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,...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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$ ...
user avatar
  • 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 ...
user avatar
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{...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 (...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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)$$ ...
user avatar
  • 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, ...
user avatar
  • 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&...
user avatar
-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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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, ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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}$...
user avatar
  • 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 ...
user avatar
  • 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: ...
user avatar
  • 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 ...
user avatar

1
2 3 4 5
7