# 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?

39 questions
36 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 ...
36 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 ...
63 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 ...
85 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 ...
270 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 ...
48 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, ...
39 views

### Coupon collectors variant: Probability of selecting exactly k unique marbles from a bag of n marbles given that you grab a random amount each time?

General case I have a bag of n marbles. I select a handful of marbles out of the bag x number of times. Each marble is equally probable to draw. Each time I select a handful, I mark them with a black ...
20 views

### Probability an binomial experiment terminates

I was recently thinking of how to calculate that an experiment terminates after a given amount of turns. An example would be something similar to opening packs of baseball cards. Suppose there are a ...
45 views

### Total distribution of m geometric distributions

Suppose that you made a webpage and you are collecting the statistics from the visitors. There are m types of visitors (students, company recruiters, etc.). Each visit is equally likely to be any of ...
54 views

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....
45 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 ...
24 views

### Probability of not being included [duplicate]

Suppose that there are 100 buckets. Each time two balls are dropped into two buckets (i.e. they will never be dropped in the same bucket). I keep repeating the exercise. Question is how many times do ...
101 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 ...
749 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 ...
340 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 ...
649 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 ...
70 views

### Birthday problem [duplicate]

Recently I read about how many people it takes for the probability that two or more share the same birthday to be sufficiently high. My question: How many people do I have to know that I could be ...
105 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 ...
170 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 ...
418 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 ...
166 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 ...
89 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, ...
77 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 ...
45 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 ...
810 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 ...
163 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 ...
867 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 ...
140 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 ...
71 views

### coupon collector's problem - labelled or not?

I have come across the famous coupon collector's problem. Linking the problem to the Twelvefold way, my first reaction has been to use the case with ...
4k 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 ...
106 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]...
896 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 ...
184 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. ...
16k 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 ...
351 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 ...
1k 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 ...
225 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 ...
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 &...