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?
59
questions
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 ...
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 ...
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 &...
19
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 ...
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 ...
15
votes
2
answers
1k
views
Expected number of times to roll a die until each side has appeared 3 times
What is the expected number of times you must roll a die until each side has appeared 3 times?
This question was asked in primary school in New Zealand and it was solved using simulations. What is ...
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 ...
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 ...
9
votes
1
answer
366
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 ...
9
votes
1
answer
430
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 ...
8
votes
1
answer
571
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 ...
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 ...
6
votes
1
answer
557
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 ...
6
votes
2
answers
186
views
Probability that all cards have been drawn [duplicate]
Let's say, I have a deck of $m$ cards from which I will draw $n$ cards at random, watch them and put them back in the deck.
I want to know; what is the change after $k$ draws, that I have seen all ...
5
votes
1
answer
590
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 ...
5
votes
1
answer
374
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 ...
5
votes
1
answer
431
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]...
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 ...
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$ ...
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 ...
5
votes
1
answer
607
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 ...
4
votes
1
answer
142
views
Modified coupon collector: killing traitors problem
You have $n$ people, $m$ of whom are traitors. You keep killing them randomly until all the traitors are gone (which you presumably have some way to verify). On average, how many people $X$ will you ...
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 ...
4
votes
1
answer
217
views
Coupon Collection Random Sum [closed]
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 ...
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 ...
3
votes
1
answer
34
views
Hypothetical roulette problem [duplicate]
If you have a roulette table that has 7,000,000 places and you have 10 balls (and only one ball can fit onto each number at every roll), how many rolls would it likely take for a ball to land on every ...
3
votes
1
answer
85
views
Quiz with questions sampled from a pool. How many new questions at each iteration? [duplicate]
I am taking a quiz which is a sample of $g$ questions from a pool of $n$ total questions. At every iteration $i$ I get a new sample of $g$ questions. I want to know the expected number of new ...
3
votes
2
answers
228
views
Combinatorics - calculating probability of choosing n people from m groups of k people
I am trying to calculate and understand the following question:
I have 10 groups of 10 people each and am choosing 10 people at random. What is the probability that all 10 people I have chosen are ...
3
votes
2
answers
94
views
What proportion of the space is taken up by independent discrete uniform variables
If you take $N$ independent uniform random selections from a discrete space with $M$ possibilities (with replacements), then what proportion of the possibilities will have been selected?
Formally, ...
3
votes
1
answer
103
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 ...
3
votes
0
answers
112
views
Probability of bad milk
Assume there are (always) $N$ bottles of milk on the grocery shelf. Each day, a deliveryman randomly selects a fixed $M \lt N$ bottles of milk from the shelf and replaces them with new bottles of milk....
3
votes
0
answers
250
views
What is the waiting time in a coupon collector problem with coupons in packs? [closed]
I am looking for an equation that will let me calculate the waiting time expectation and variance for a coupon collector problem (equal probabilities of coupons) in which coupons come in packs, with ...
2
votes
2
answers
205
views
How many unique values can you expect after throwing a die with k sides?
I ended up asking here.
My problem might be familiar with the coupon collector's problem and related to this post Probability of throwing n different numbers in m throws of a die but it does not solve ...
2
votes
1
answer
76
views
A Pairwise Coupon Collector Problem
This is a modified version of the coupon collector problem, where we are interested in making comparisons between the "coupons". There are a number of constraints which have been placed in ...
2
votes
1
answer
634
views
Expected time to get all four unique coupons [duplicate]
Envelopes are on sale for Rs. 30 each. Each envelope contains exactly one coupon, which can be one of four types with equal probability. Suppose you keep on buying envelopes and stop when you collect ...
2
votes
1
answer
629
views
What's the expected number of distinct values within a binomial distribution sample?
Given $X$ has a binomial distribution $B(n,p)$. Now I take $k$ samples from $X$. What's the expected value of how many distinct values I sampled?
My rather futile approach was: Given after $k$ draws, ...
2
votes
0
answers
25
views
How can I find the expectation value to this problem?
At a wedding reception on an evening the representative of the host is taking it as an occasion to exercise and explain a classical analytic problem. specifically, he insists that he would start ...
2
votes
2
answers
107
views
Calculate probability that I have fully sampled a set [duplicate]
Let's say I have a set of items out of which I randomly take 5% . Then perform some action on these items and put them back in the set.
After how many repetitions of this process can I be 95% sure ...
2
votes
0
answers
195
views
Intuition about a coupon problem were we ask for the distribution of the unique coupons when the number of draws is fixed
Alternative viewpoint of the coupon collectors problem
In the coupon collectors problem we draw from a collection of $n$ coupons, with replacement and ask the question how many draws $K$ it takes to ...
2
votes
0
answers
253
views
Extending the Coupon Collector Problem
The Coupon Collector Problem is a well-known one in mathematics and statistics.
The problem assumes that all unique coupons are equally likely a priori and gives the expected (mean) number of coupons ...
2
votes
0
answers
82
views
Variation of coupon collector's problem: types of coupon are divided into sets, find expected number of coupons for first complete set
Suppose you are collecting coupons from a pool of 50 distinct types. These types can be divided into 10 sets of 5 types each. What is the expected number of coupons you need to collect in order to ...
1
vote
1
answer
298
views
Coupon collecting problem
Suppose there are 8 different types of coupons, each coupon has probability 1/8 of being selected. Suppose a total of 6 coupons are collected.
Let:
$$
X_i=\begin{cases} 1, \textrm{if a type-i coupon ...
1
vote
1
answer
73
views
Probability of all points has been sampled after M trials
If I have a sequential dataset of size 10,000 (e.g. timeseries) and sampling randomly a batch size of 100 random values, each point of the 100 is sampled with the next 5 points after it. so basically ...
1
vote
1
answer
137
views
How many samples are needed to observe every subject?
I have this problem. I have to analyze 13 chemical substances (n=13) in more than one analysis cycle. In each cycle of analysis, 8 substances are randomly chosen (m=8) to be analyzed. I would like to ...
1
vote
1
answer
299
views
Probability of Jar containing Balls type question with replacement
A jar has 50 balls 1 to 50 each one having distinct number written on it. Bob, owner of the jar,each day he takes out one ball out of the jar randomly ( with equal probability) and put it back.
Q1. ...
1
vote
1
answer
82
views
Calculate probability
Assume that a remailer reorders messages. It has a pool of n-1 messages at all times. When the nth message arrives, one of the n messages is selected at random and forwarded. An attacker fools the ...
1
vote
1
answer
285
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 ...
1
vote
1
answer
103
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 ...
1
vote
0
answers
47
views
How many random draws needed to sample a uniform space?
I am looking for a way to estimate how many random draws took place to produce a produce a known number of unique results. I'm sampling a uniform distribution.
For example, if there were a lottery ...
1
vote
0
answers
250
views
Understanding the equation for the coupon collector problem
I am collecting the new world cup panini album. The album has 680 stickers (approx) and there are 5 different stickers in each packet. I would like to know the probability I have of missing 50 sticker ...