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. the coupons) has been obtained at least once. Questions deal with the associated probability distribution, proof techniques, etc.
1
vote
0answers
71 views
How many boxes of cereal do you expect to have to buy to get all N toys?
Suppose 𝑵 different toys are offered in boxes of a favorite brand of cereal. You want to collect all the different toys. How many boxes of cereal do you expect to have to buy to get all 𝑵 toys? Let ...
4
votes
2answers
49 views
Counting coupons in a box
I have a question with regards to counting. I come from a background in quantum computing, so I'm not familiar with the relevant literature here. For the interested reader, I provide below more ...
0
votes
0answers
23 views
The coupon collectors bounding proof
Here's a variation of the coupon collector problem that I'm stuck on. I don't have any idea for solving. Is there any solution to solve?
The sharp threshold results in the coupon collector's problem ...
0
votes
1answer
30 views
Coupon Collector Problem: How to derive a recurrence for expected time.
Let $T_{i,j}$ denote the expected time taken to get $j$ distinct coupons given that one already has $i$ distinct coupons. Say that we have $n$ distinct coupons, then I want to find a recurrence ...
2
votes
0answers
41 views
Coupon Collector's Problem and Balls in Bins Variant
Consider a variant of the traditional coupon collector's problem. There're $n$ kinds of coupons and there's a $1 \times n$ grid. Each grid corresponds to one kind of coupon. Once picking a coupon, we ...
-2
votes
1answer
34 views
Variation of coupon collector's problem? [closed]
If I have n coupons to collect and I buy only 2n boxes, how many distinct types of coupons can I expect to have?
0
votes
0answers
28 views
Tail bounds for partial coupon collector process
In the coupon collector problem, a collector gets a random coupon from $\{1,\ldots,n\}$ at every time instance.
The original formulation usually deals with bounds on the time it takes the collector ...
0
votes
0answers
22 views
The expected number of n types of coupons have appeared at least once? [duplicate]
There are n different types of coupons and each item must contain one coupon. So what is the expected number of items needed to buy for all n types of coupons have appeared at least once?
1
vote
1answer
16 views
Help in Disproving another approach to the Coupon Collector Problem
In the coupon collector's problem, instead of setting E(X) as the amount of time required to select a new distinct Coupon, if we set it as the expectant amount of required to select a given coupon ...
2
votes
1answer
89 views
Coupon Collector problem - 2nd moment method
Recall the coupon collector problem, namely, drawing numbers (coupons) iid from $[n]$.
I want to prove that the probability that we drawed all numbers after $k=\frac{n\ln n}{4}$ tries tends to $0$ as $...
0
votes
0answers
35 views
Coupon Collecting with Quotas
Trying to visualize how to find the probability of winning this game in $X$ number of trials. There is a mathematical paper (see below) that refers to a game of "under the cap" where you have to meet ...
1
vote
0answers
75 views
Inclusion-Exclusion principle / Coupon Collector
Here's the setup to the problem. Assume there are $5$ types of coupons, and you keep collecting coupons until you meet your condition. What is the probability that the number of trials needed to ...
2
votes
1answer
62 views
Mixture of negative binomial distributions (technically some of them are geometric)
I have something that I am trying to compute.
Let's say that a number is uniformly generated 1-4.
What would be the expected number of generations required to get at least 3 1s and every other ...
2
votes
1answer
82 views
Coupon Collecting Problem: Condition on the order of coupons you see
There are four types of coupons (call them types $1,2,3,4$) with $p_1 = p_2 = 1/8$ and $p_3 = p_4 = 3/8$. You collect coupons until you have a full set.
Q1: What is the probability that after ...
1
vote
2answers
96 views
Coupon Collecting Problem: $4$ coupons with $p_1 = p_2 = \frac{1}{8}$ and $p_3 = p_4 = \frac{3}{8}$
This is from Ross.
I know how to solve everything but (d).
The book answer is $\frac{123}{35}$.
There are $4$ different types of coupons, the first $2$ of which compose one group and the second $2$...
0
votes
1answer
81 views
Coupon collector problem with partial collection of a specific set of coupons
I am very new in probability and combinatorics and have a naive question around a variation on the coupon collector problem with partial collection.
Lets assume we have a box with 45 coupons labeled ...
1
vote
2answers
150 views
Expected number of coupons occurring at most once
As a variation on the coupon collector problem, I would like to find on average how many coupons ($n$ types of coupons) occur in $k$ trials are picked at most once.
I have approached this by summing ...
2
votes
1answer
141 views
Variation of coupon collector problem with distinct coupons in each type
I am interested in yet another variation of the coupon collector problem. Specifically, we have an urn with $n_i$ "distinct" coupons of type $i$, where $i = 1,\ldots, K$ (for example, a type can be ...
0
votes
2answers
83 views
Coupon collecting with unequal probabilities (S.Ross Min-Max approach)
While going through a method to solve the coupon collecting problem , the author posed the problem as follows :
Suppose there are $n$ types of coupons and that each time one collects a coupon, it ...
0
votes
0answers
46 views
Probability of visiting all states at least once in N trials [duplicate]
Assuming my world is made up of 100 distinct states such that:
$$S = (s1, s2, s3, ... s100)$$
Let's call the number of states 'K'.
And assuming that I perform N trials, wherein each trial I visit ...
4
votes
3answers
198 views
Does the uniform distribution minimize the expected value in the coupon collector's problem?
Given a discrete probability distribution with $n$ possible outcomes and the task of repeatedly sampling until getting each outcome at least once, does the uniform distribution give the smallest ...
0
votes
1answer
87 views
Inclusion Exclusion Principle Combinatorics
My problem is: Assume that every time you buy a box of cereal, you receive one of the pictures of the New York Yankees players and there are $n$ on the team. Over some time you buy $m\ge$$n$ boxes of ...
0
votes
1answer
68 views
the probability for a file to be completed under random distribution
Suppose there are $n$ files, for ease lets assume all are of the same size $S$.
Further suppose that each second, you obtain some fraction of size $k<<S$ (packet size) that is a part of one of ...
0
votes
1answer
26 views
Random Variable Distribution (Successive Removal from List)
Let $A$ be an arbitrary list with $n$ distinct elements. Suppose I have a separate list, $B$, which is initially identical to $A$. Denote individual elements in $B$ as $b_k$ where $k\in\{1,2,...,n\}$...
1
vote
2answers
168 views
Drawing at least that many “distinct” balls of each color
We have an urn with $n_1$ red balls and $n_2$ black balls (total number of balls is $n = n_1+n_2$). We will draw a total of $k$ balls with replacement.
1) What's the probability that in the $k$ ...
3
votes
2answers
64 views
Formula to determine how many quarters needed to buy remaining baseball cards in collection?
I apologize in advance if I'm not explaining this well. I'm trying to solve a problem I'm having at work but I can't think of the mathematical formula needed in order to solve it. Rather than bore ...
3
votes
0answers
68 views
In a network like Facebook, how many distinct user profiles can one manufacturer access if it can access each device owner's friends of friends? [closed]
After reporting on the NYT article Facebook Gave Device Makers Deep Access to Data on Users and Friends, a journalist asked me if this data leak affected more or less Facebook users than the Cambridge ...
14
votes
0answers
321 views
Random sum in coupon collection
I have a problem which involves the standard coupon collector's problem to find a probability density from the generating convolution. I start by defining the problem and a few basic statistics. Let ...
0
votes
0answers
37 views
Coupon collector expectation using definition [duplicate]
I want to do coupon collector's for a dice roll, or the expected number of rolls to get all 6 numbers from definition of expected value as opposed to using linearity of expectation.
$\tau = min\{ t \...
0
votes
1answer
88 views
How many sticker packets do I need to complete an album?
This question solves the problem of "how many packets do I need to achieve a certain probability of completing the album?", but this made me think of another (quite related) question.
Given an album ...
4
votes
1answer
162 views
Show that $n\sum_{k=1}^n\frac{1}{k}\sim n\log{n},$ Collector's problem.
Consider coupons numbered $1, 2, ..., n,$ which you collect until you
have all numbers. Each time you get a coupon, its number is
independent of previous numbers and all numbers are equally likely....
0
votes
1answer
87 views
Coupon Collector Problem: Expectation for a Fraction of Unique Samples
Say that I have a urn with, $m$, unique samples. There is a probability, $p_{i}$ for sampling a given unique sample, $m_{i}$, when sampling with replacement. Also note that the probability, $p_{i}$, ...
3
votes
1answer
143 views
Coupon Collector Problem with multiple copies and X amount of coupons already collected
I have a variant of the coupon collector problem where there are $n$ different coupons being collected, which are being drawn with equal probability and with replacement, but 2 copies of each coupon ...
0
votes
1answer
67 views
Convergence in the coupon collector problem
In the well-known coupon collector problem, let $X$ be the expected time for a collector to obtain all different $n$ coupons. It is well known that
$E[X]=n\log n +O(n)$
where $O(n)$ is a term ...
0
votes
0answers
62 views
Expected number of days before you have collected all flags [duplicate]
At the Pseudo-IMO, there are n students other than you, each from a different country.
Every day, you eat lunch with a random student, and they give you a miniature
flag from their
country. Let X ...
1
vote
1answer
116 views
Coupon Collector problem with unequal probabilities
Suppose there are two different coupons and we want to find the average number of coupons drawn until we get the two coupons.
The probabilities of getting the two coupon types are not equal. Denote ...
1
vote
2answers
257 views
Expected number of 5-sticker packs needed to complete a Panini soccer album
To fill a football album of 200 stickers (images of players), how many envelopes do I need to buy if every envelope has 5 stickers and the album company says that all stickers has the same probability ...
0
votes
1answer
159 views
Coupon Collector when $n=3$
Suppose we have $3$ different types of coupons $C_1,C_2,C_3$, and the probability we draw each coupon is $p_1,p_2$ and $p_3$ for $C_1,C_2$ and $C_3$ accordingly. How many times in average will we have ...
1
vote
2answers
60 views
Coupon Collector's Problem with delayed replacement
I have a set of 28 items (coupons) that are picked one at a time with replacement, but the same coupon is never picked twice in a row. In effect, a coupon is not replaced immediately — each coupon is ...
0
votes
1answer
169 views
variation on the coupon collector problem
I'm considering a twist on the classic coupon collector problem.
The user has k urn and needs to collect m different balls from each urn.
I need to calculate the expected time for the user to collect ...
1
vote
1answer
66 views
How to calculate expected cost of a lottery game?
I'm trying to guess the design of a very complex lottery mechanism from a game to estimate its costs. Here the mechanism :
Each pull costs 1$.
Draws are with replacement.
Chances to get an item is ...
1
vote
0answers
28 views
Expected views to discover all advertisements [closed]
A surface randomly selects 3 different advertisements, from a set of 19 advertisements, and displays these advertisements to the user.
How many times on average must the user view the surface to see ...
0
votes
1answer
124 views
How does the Coupon Collector problem change when you're only trying to collect a subset of the coupons?
If there are 100 tickets in an urn, and I'm only trying to see 10 of them while drawing with replacement, how do I find the result for that?
My intuition makes me want to say it's $n\sum_{i=1}^k\frac{...
1
vote
1answer
129 views
How does the Coupon Collector Problem change when you draw two items at the same time?
If there are 100 tickets in an urn, and you draw two at a time, look at them, and replace them both, how does that change the problem? It would obviously take half as many trials, but how does the ...
1
vote
2answers
176 views
Coupon collector - Chance of collecting desired coupons but not a full set.
Disclaimer: I am not in a mathematics field or a mathematics professional.
I'm interested to know how many random draws it would take to have a particular chance (50%, 75% and 90%) of getting 5 ...
2
votes
1answer
176 views
Finite sample bounds for generalized coupon collector problem
Consider the usual generalization of the coupon collector problem where $m$ copies of each coupon need to be collected. Let $T_m$ be the first time m copies of each coupon are collected. Donald J. ...
1
vote
1answer
344 views
Coupon Collector Problem solving for expected completion percentage [closed]
I'm working on a variation of the coupon collector problem and trying to make a formulaic solution in Excel without using a user-defined function.
Basically, the gist of the problem is that at a ...
2
votes
1answer
919 views
Coupon Collector's Problem with X amount of coupons already collected. [duplicate]
I am having an issue with understanding how to calculate a specific case of the Coupon Collector's Problem. Say I have a set of 198 coupons. I learned how to find the estimated amount of draws to see ...
0
votes
0answers
18 views
Combinatorics and statistics question regarding drawing every element [duplicate]
Assuming a set of size X, on average how many attempts would it take to randomly draw every element in the set (returning it back after drawing)?
I have a hard time formulating a title for this ...
1
vote
1answer
116 views
Is coupon collection concentrated?
Say you buy $m$ coupons out of $n$ possible types, and each is given you randomly with replacement. It's standard that the amount of time you need to wait to get $k$ coupons is approximately in ...
