Skip to main content
28 votes
Accepted

Expected number of times to roll a die until each side has appeared 3 times

Suppose all $d=6$ sides have equal chances. Let's generalize and find the expected number of rolls needed until side $1$ has appeared $n_1$ times, side $2$ has appeared $n_2$ times, ..., and side $d$ ...
whuber's user avatar
  • 327k
12 votes

Expected number of times to roll a die until each side has appeared 3 times

The original version of this question started life by asking: how many rolls are needed until each side has appeared 3 times Of course, that is a question that does not have an answer as @...
wolfies's user avatar
  • 7,823
8 votes

Continuous Version of Coupon-Collector Problem

This question reminds me of Wilfrid Kendall's dead leaves simulation, which he uses to explain the difference between forward and backward sampling. Given that the problem can be formalised ...
Xi'an's user avatar
  • 106k
5 votes
Accepted

Intuition about the coupon collector problem approaching a Gumbel distribution

Below is a bastardized short version of the connection made in the paper by Holst: The connection with the Gumbel distribution is made with the following steps... Viewing the waiting time to collect ...
Sextus Empiricus's user avatar
5 votes
Accepted

Expectation of collecting stickers in groups

Probability problems can be tricky. Whenever possible, reduce them to steps that are justified by basic principles and axioms. Expectation problems get a little easier because you don't have to keep ...
whuber's user avatar
  • 327k
5 votes

Is there a formula for a general form of the coupon collector problem?

This is not easy to compute, but it can be done, provided $\binom{m+k}{k}$ is not too large. (This number counts the possible states you need to track while collecting coupons.) Let's begin with a ...
whuber's user avatar
  • 327k
4 votes

Estimating n in coupon collector's problem

Likelihood function and probability In an answer to a question about the reverse birthday problem a solution for a likelihood function has been given by Cody Maughan. The likelihood function for the ...
Sextus Empiricus's user avatar
4 votes
Accepted

Number of expected turns to get $k$ distinct numbers

Consider a stage in this process where exactly $i$ distinct numbers have already been seen $(0 \le i \lt N).$ "Equiprobable" means that on average, out of every $N$ times this stage is ...
whuber's user avatar
  • 327k
3 votes
Accepted

How many unique values can you expect after throwing a die with k sides?

How many unique values can you expect after throwing a dice with k sides? If you only need the expectation value then the answer is relatively simple. We can compute the probability that a specific ...
Sextus Empiricus's user avatar
3 votes

Probability of all points has been sampled after M trials

In these complex situations it's often much easier to simulate the situation and find an approximate probability than to find an exact analytic expression. Here's a simulation in R showing there is ...
David L Thiessen's user avatar
3 votes

Expected numbers of distinct colors when drawing without replacement

Suppose you have $k$ colors where $k \leq N$. Let $b_i$ denote the number of balls color $i$ so $\sum b_i = N$. Let $B = \{b_1, \ldots, b_k\}$ and let $E_i(B)$ notate the set which consists of the $i$ ...
jakab922's user avatar
  • 211
3 votes
Accepted

Modified coupon collector: killing traitors problem

As pointed out in the comment, this is a special case of the Negative Hypergeometric distribution. So the answer is, on average, $$\frac{m}{m+1}(n-m)$$ innocents will be killed before all $m$ traitors ...
chausies's user avatar
  • 421
2 votes

What proportion of the space is taken up by independent discrete uniform variables

Contrary to the answer by kjetil, this is actually the "classical occupancy problem" (which is related to the coupon collector's problem, but is not quite the same problem). The random variable $|S|$ ...
Ben's user avatar
  • 127k
2 votes
Accepted

How many samples do I need to take to expect I have seen (x%, say 99%) of the finite population?

This is a variant of the coupon collector's problem, which can be solved using the classical occupancy distribution (see e.g., Johnson and Kotz 1977). Suppose you draw $n$ times from your urn of $m=...
Ben's user avatar
  • 127k
2 votes

Probability that all cards have been drawn

I think the solution would go something like this: Let $P(m, n, k, x, y)$ be the probability of seeing exactly $x$ cards at least once over $k$ draws, once $y$ cards have already been seen. Then $P(...
rinspy's user avatar
  • 3,370
2 votes
Accepted

Quiz with questions sampled from a pool. How many new questions at each iteration?

Each question has a probability $1-g/n$ of not being picked in each iteration. Hence after the $i$'th iteration (letting $i=0$ denote the first iteration), each question has not been picked with ...
Jarle Tufto's user avatar
  • 11.2k
2 votes

Combinatorics - calculating probability of choosing n people from m groups of k people

Consider $m=10$ groups of size $n=10$ each. Obtain a sample of size $N$ by withdrawing one element at a time. For the possible counts $0, 1, 2, \ldots, m,$ let $p_N(i)$ be the chance that exactly $i$...
whuber's user avatar
  • 327k
2 votes

Hypothetical roulette problem

If you want the expected number, then you can use a recursion for an exact calculation (up to precision errors). For example in R ($7$ million loops takes some time): ...
Henry's user avatar
  • 40.4k
2 votes

How many samples are needed to observe every subject?

This is a variation of the Coupon Collector problem, extensively discussed on this site. However, the algorithm proposed for this variation is based on the Principle of Inclusion-Exclusion, which is ...
whuber's user avatar
  • 327k
1 vote
Accepted

Calculate probability

Let, Y be the number of fake messages sent by trickster for all the original messages to be forwarded. E[Y] be the expected number of fake messages sent. We can write \begin{equation} Y = X_1+X_2+\...
Stats Noob's user avatar
1 vote

A Pairwise Coupon Collector Problem

A Solution for Question 1 \begin{align*} E(X) &= \binom{M}{2}\left(1 - (1-p)^T\right) \\ V(X) &= \binom{M}{2}(1-p)^T\left(1 -\binom{M}{2}(1-p)^T\right) + 6\binom{M}{3}(1-q)^T + 6\binom{M}{4}(...
knrumsey's user avatar
  • 8,317
1 vote
Accepted

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?

We could find the probability of not having some items selected at all after the experiment, for a given $m$. For a chosen set of $x$ items, the probability of not having selected them at all after $m$...
gunes's user avatar
  • 57.7k
1 vote

Probability that all cards have been drawn

This is a simple variant of the coupon collector's problem, which uses the classical occupancy distribution. Let $K$ be the number of distinct cards that have been drawn, distributed according to the ...
Ben's user avatar
  • 127k
1 vote
Accepted

Need help with expected value calculation in coupon collectors in coupon collectors variant

This answer was what I was looking for. With a single cap, I can get the probability that any point chosen randomly from the surface will not be part of the cap as: $ Pr=(1 - \frac{m}{n}) $ and for $k$...
jordanlgraves's user avatar
1 vote

Coupon Collection Random Sum

Note: I am writing a partial answer which is to be updated later You can use $$P(T=t|R=r) = \frac{N_{T=t,R=r}}{N_{R=r}}$$ the ratio of $N_{R=r}$ the number of ways the number of ways to finish in $...
Sextus Empiricus's user avatar
1 vote
Accepted

Expected time to get all four unique coupons

One way to approach this would be to break down $X$, the number of trials required, into the sum $X = X_1 + X_2 + X_3 + X_4$, where $X_i$ is the number of trials needed to get the $i^{th}$ unique ...
josliber's user avatar
  • 4,377
1 vote

In the coupon collector's problem with group drawings, why does the probability decrease with increasing samples?

While late to the game I believe I understand the issue you are having. The case is not, as the comments suggest, because the equation is for exactly the number of stickers, but rather due to the ...
Zack Ashman's user avatar
1 vote

Multinomial distribution conditional on number of distinct items

TLDR just generalize the coupon collector techniques. Suppose you have a discrete state space Markov chain that evolves on the space of all subsets of $\{1,\ldots,k\}$ that have size between $0$ and $...
Taylor's user avatar
  • 20.9k
1 vote

What's the expected number of distinct values within a binomial distribution sample?

Let us reformulate and generalize a bit. Say we have a collection of $n$ objects ($n \ge 1$). We sample with replacement from this collection $k$ times. Each time the probability of selecting object $...
kjetil b halvorsen's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible