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.
249
questions
1
vote
1answer
50 views
Expected numbers of turns to generate k distinct elements
There is a random number generator. It generates numbers between $1$ and $n$ with equal probability. What is the expected number of turns for it to generate k distinct numbers?
EDIT: My approach is to ...
8
votes
1answer
115 views
Infection in a village
Consider the following problem:
Suppose a lonely wanderer infected with a virus came into an isolated village with $M$ villagers and stayed there. Every week each of the infected villagers coughs ...
1
vote
2answers
34 views
Number of tries to get all characters
If I have the following table
10 Common characters 70% chance
5 Uncommon characters 20% chance
2 Epic characters 10% chance
How many tries to get all the characters (I can draw duplicates)
How many ...
-1
votes
1answer
16 views
Average time taken to collect at least 1 category of cards from 10 cards with replacement
let say there's 10 card in a box, which categorize to:
Spade - A, 2, 3, 4, 5
Heart - A, 2, 3, 4, 5
One card is draw at a time with replacement,
What is the average time taken to collect at least one ...
0
votes
0answers
18 views
Solving Coupon's Collector Problem with Unequal Probabilities in Google Sheets
I am creating a game where I want the player to collect 26 letters (A-Z). Each letter has a different weight/probability.
How do I calculate how many draws will a player need to collect all 26 letters,...
5
votes
1answer
86 views
Expected number of games so that every player has been an Imposter in Among Us
Imagine you have $n$ players. In each game, $k$ $(k\leq n)$ players are chosen randomly to do whatever.
By game $G$, what is the probability that every player has been chosen at least once?
What is ...
1
vote
0answers
23 views
Distribution for first time to have drawn all colors
Consider an urn with $n=\sum_{i=1}^rn_i$ balls, where $n_i$ represents the number of balls of color $i$ (out of $r$ possible colors).
What’s the distribution describing the first time it takes to have ...
2
votes
1answer
74 views
what is the probability of drawing each element at least once from set $\{1,2,3,\dots, n\}$ , drawing with replacements at most $k$ times ($k>n$)
what is the probability of drawing each element at least once from set $\{1,2,3,\dots, n\}$, drawing with replacements at most $k_0$ times ($k_0>n$)
my take:
$$\left(\prod_{i=1}^{n} \frac{i}{n}\...
0
votes
2answers
67 views
Five pills problem from exercises based on Feynman's lectures
I have some questions about the solution to the five pills problem which is part of the list of exercises based on Feynman's lectures.
In the solution above m is the number of types of pills and ...
0
votes
1answer
19 views
Are the geometric random variables in coupon collector problem independent?
Based on the "Calculating Variance" section in https://en.wikipedia.org/wiki/Coupon_collector%27s_problem, it appears that the geometric RVs in the coupon collector problem are independent.
...
0
votes
1answer
21 views
P.m.f., expected value, and variance of number of rolls of a fair die needed for every face to appear at least once.
I think I have found that $\operatorname E(X) = 14.7.$
However, I'm not sure about the pmf or $\operatorname{Var}(X).$
I have the hint that $X = 1 + X_1 +X_2+\cdots+X_5$
and that for some reason $P(...
2
votes
1answer
25 views
Chance of rolling each permutation of a die after passing an initial dice roll
Let's say we have a 20-sided die and a 6-sided die. In order to roll the 6-sided die one time, we must first roll a 20 on the 20-sided die. Our objective is to get to the 6-sided die and roll each ...
1
vote
0answers
21 views
variant of coupon collector's problem - how many draws to cover p fraction of coupons
I have a urn with balls of "M" distinct colors. I draw "N" times (with replacement) from the urn. Probability of encountering each ball in a draw = $\frac{1}{M}$. How many expected ...
1
vote
1answer
74 views
Expectation rounds of group drawings of urn balls
An urn has $N$ red balls. We constantly sample $k$ random balls from it (group drawing with fixed size $k$), repaint the balls to white balls, and return $k$ white balls to the urn. I wonder the ...
0
votes
0answers
18 views
Needed subset draws to get all elements with a given probability [duplicate]
I have a set of N elements. I draw (without replacement) a subset of M elements, then replace it.
What value M do I need, to have a probability greater than p to draw all N elements within X subset ...
4
votes
1answer
91 views
However, how long will it take to randomly generate an $n$-universal word?
Suppose $A$ is a finite alphabet, $|A| = m$. Let's call a word $w \in A^*$ $n$-universal iff it contains every word from $A^n$ as a subword. Now, suppose we generate a random $n$-universal word in a ...
0
votes
1answer
42 views
The probability of getting $y$ new coupons from a batch of $k$
In the coupon collector process, the goal is to assemble a collection of $n$ distinct coupons, while we get a random coupon at each time.
I am looking at a generalization of this problem, where at ...
1
vote
1answer
30 views
Expected time for multiple independent coupon collectors to finish
I have a problem where there are $C$ independent coupon collectors and there are 5 coupons in total. All $C$ collectors have already collected the first three coupons and have to finish collecting the ...
2
votes
2answers
145 views
Packs of gum probability
On each gum pack there's a prize. There's $6$ different prizes and each gum pack has the same probability to have each prize. Johnny buys a gum pack each day to collect all the different prizes and ...
2
votes
2answers
79 views
Coupon collector's problem revisited (brute force calculation)
I was trying to solve coupon collector problem for $5$ coupons using brute force calculation, but gave up and say the simple expected value based solution. The question goes like this:
Coupon in ...
1
vote
0answers
25 views
What is the expected value of this question? [duplicate]
There is a lottery system with 12 kinds of cards. Everyday I'm allowed to take one card from the system and the odds of taking each kind of cards is equal(1/12).The number of each kind of cards is ...
0
votes
1answer
28 views
Pile of cards - Probability question [duplicate]
There is a standard pile of cards with 52 cards that is mixed randomly. Every time I pick a card randomly. Afterwards, I put the card back. I continue to do so until I see all the different ace cards (...
0
votes
0answers
22 views
Generic Solutions to the Coupon Collector Problem
Suppose I wanted to find out how many rolls it would take to get 75% of the values on a N sided dice, how would I do this?
0
votes
1answer
47 views
Expected number of rolls needed to get four distinct results
Suppose I have a fair, six-sided die. What is the expected number of rolls it would take me to get four distinct outcomes?
3
votes
1answer
45 views
Coupon collector with arbitrary duplicates
What is the expected number of tickets in the coupon collector's problem where duplicates are allowed, but some tickets have a different, arbitrary number of duplicates required until the collector's ...
1
vote
0answers
27 views
Coupon problem from Ross' Probability Models [duplicate]
This is a question from Sheldon M Ross' Intro to Probability Models.
Suppose that each coupon obtained is, independent of what has been previously
obtained, equally likely to be any of $m$ ...
0
votes
0answers
44 views
What is the probability of getting one of each 10 different figures if we bought 25 pack? [duplicate]
There are 10 differente figures (A,B,C,D,E,F,G,H,I,J), all equally probable to get.
We bought 25 pack which each contains only 1 figure
What is the porbability if we bought 25 packs we got all the ...
0
votes
0answers
90 views
A Coupon's collector look a like problem
The pub Gosset’s Paradise serves $N ≥ 1$ different brands of beer. Each time a drink is ordered, one of the brands is served uniformly at random. John wants to sample each brand at least once. Let $...
1
vote
0answers
24 views
Variant of coupon collector's problem [duplicate]
If each box of cereal contains 2 different prizes at random and there are 7 prizes total, how many boxes would you expect to open in order to collect all 7 prizes?
The standard version of this ...
0
votes
2answers
55 views
How many dice to get one of each of the 6 faces?
There's this riddle: In a pub the owner is throwing a number of dice simultaneously. "I am trying to get one of each of the six faces", he says, "But it hasn't happened yet". "No", I said "You need at ...
0
votes
1answer
43 views
Find the expected value of tickets that the player should buy, in order to get a super prize.
In a lottery, there are $K$ distinct prizes. The probability of winning any one of the prizes is the same for every ticket and is equal to $1/K$. In case the player wins all $K$ prizes, he will get a ...
0
votes
0answers
19 views
Probability of Sampling All Members of a Subset At Least Once with Repeated, Without-Replacement Sampling [duplicate]
Given a set containing n unique members, what are the odds that all members of a subset m are sampled at least once when non-replacement samplings of size k are repeated i times? Members are replaced ...
2
votes
0answers
28 views
Permutation: how many random permutations needed to have every possible values in every possible places
I'm doing random permutations of a set (shuffling) and I want to generate the minimum number of permutations to have every values at every places, at least once.
Say I have a set of $n$ distinct ...
1
vote
1answer
50 views
Expected Value of the number of letters we need to draw from the alphabet
We draw letters (a-z) independently and uniformly at random from the alphabet with replacement. If we draw a collection of letters, then we say that we can write a word when the collections contains ...
0
votes
0answers
33 views
Expected number of turns to win a card-collecting game
I am designing a card-collecting game where one would draw one random card (lets call it "A" tier) at a time with the goal of finishing a set (of at least 3), where each card is distinct in the set (...
2
votes
2answers
133 views
What is the expected number of rolls until outcomes 1 and 2 are both observed on a dice? [closed]
What is the expected number of rolls until outcomes 1 and 2 are both observed. They can be in any order. I assume this is something related to a geometric distribution.
2
votes
1answer
51 views
With $50$ options, what is the average random chooses until are a used
In the scenario where there are $50$ options and $1$ option is chosen randomly at a time, on how many times would it take until all options are chosen on an average attempt?
Then, if there are again $...
2
votes
3answers
42 views
Why is $\sum_{i=1}^n\frac n{n-i+1}=n\sum_{i=1}^n\frac1i$?
While reading through my (algorithms and) probability script, I have seen this equality for calculating the first moment of the coupon-collector problem. However, I don't quite see how the sum of the ...
0
votes
0answers
32 views
How long on average will it take to get every option in a set of 73 at 4 random options per day
My question seems simple but I can't figure out how to get to a mathematical answer. It has something to do with the binomial coefficient as it is 73 choose 4 but I'm not sure how to represent ...
0
votes
1answer
43 views
Inclusion-Exclusion Principle with Summations and combinations
I am trying to understand this solution. I understand how they derived P(Aj), P(Aj1,Aj2), etc. After using the inclusion exclusion principle I get lost. How did they go from the inclusion-exclusion ...
0
votes
0answers
16 views
Probability of collecting all prizes from cereal boxes [duplicate]
Each cereal box contains 1 of 5 uniformly distributed prizes. If you open 10 randomly selected boxes, what is the probability that you will get all 5 prizes?
More generally, is there a formula you ...
0
votes
2answers
27 views
What is the expected number of rolls to get 5 different numbers from a 10-face die?
Suppose we have a 10-face fair die such that the expected number of rolls to get a particular number from $\{1, 2, \ldots, 10\}$ is $10.$ Then, I am wondering how would I go about finding the expected ...
4
votes
2answers
90 views
Multinomial Distribution — How to calculate percentiles?
I've read the rules and searched but I do not even know what I'm looking for.
Here is my problem:
Suppose I have a bag containing three different marbles: red, green, and blue. I am drawing a single ...
1
vote
2answers
127 views
Expectation on drawing card from a deck. [duplicate]
Suppose I keep drawing cards from a deck of cards(with replacement, meaning after I draw a card, I switch a new deck of cards but keep the card I draw) until I have drawn both a 1 and a 2. Then What ...
7
votes
4answers
185 views
Probability of a number to appear once after every number appear once in rolling die
A die is rolled until every number appears at least once. What is the probability that the number 1 only appears once?
I think the problem is related to the Coupon collector's problem, but I cannot ...
0
votes
0answers
23 views
Expect number of samples, without replacement, from a set such that the sum of sampled elements exceeds a threshold.
I apologize in advance if this question was already asked; I just could not find it!
Say I have the set, C, such that:
$$C=\{p | p_i\geq0;\sum_{i=0}^n p_i=1\}$$
A simple example, I let C={0, 0, 0, ...
0
votes
1answer
52 views
Find number of red balls after K turns if you paint Q balls from a bag of N distinct ones
This was a question from Infinix Hiring challenge, which ended few days ago.
You have N distinct white balls, and want to paint balls in a red color, instead of ...
0
votes
1answer
28 views
Use Chebyshev inequality to find a least bound for number of purchases in collector's problem
From the classic version of this problem, we know $T_N$, the number of purchases required to collect N distinct coupons has $E(T_N) \approx NlogN$; $V(T_N) \approx N^2\pi^2 /6$.
Here I have got a ...
1
vote
2answers
90 views
What is the probability of collecting all 50 state quarters from a bucket of 1000 of them based on known probabilities of each zone of origin?
I live in the Eastern time zone of USA. Assume that there are 5 "zones" the USA is divided into for this problem (Eastern, Central, Mountain, Pacific, and Alaska + Hawaii). Also assume that if the ...
0
votes
0answers
32 views
what is the probability to know every card at the end of the game? [duplicate]
I'm not really into math so i'm sorry if this problem already has an answer in another form, but i didn't find any.
Here it is : i pick a given number of cards and put them on hidden face in front ...
