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
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 ...

1
2 3 4 5