2
$\begingroup$

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 that I have performed this action on all the items.

For illustrative purposes -- Let's say I take 5 ping-pong balls blindly out from a sack where there are originally 100 white balls. I paint/repaint those I have taken red and put them back in the sack. After how many tries can I be 95% sure that all the balls in sack are now red. What would the general form for the calculation be for other sample sizes and probabilities. (10% of balls and 75% chance etc.)

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ If you selected the balls 1 at a time, this would be equivalent to the coupon-collector problem; the selection of 5 at a time is a modest wrinkle on that (since you only ever get 5 different coupons in each set of 5 this way). $\endgroup$
    – Glen_b
    Commented Oct 13, 2021 at 7:00
  • $\begingroup$ It might be good to edit the question and make some suggestions in the direction of at least a partial solution. $\endgroup$
    – TMBailey
    Commented Oct 13, 2021 at 7:01
  • $\begingroup$ In addition to the duplicate, stats.stackexchange.com/questions/198915 is also relevant. $\endgroup$
    – whuber ♦
    Commented Oct 13, 2021 at 17:16

2 Answers 2

Reset to default
0
$\begingroup$

If you are interested in a numerical result, using simulations in R

n=100
k=5
p=0.95

res=replicate(1e5,{
  x=rep(0,n)
  i=0
  while (TRUE) {
    x[sample(1:n,k,replace=F)]=1
    i=i+1
    if (all(x==1)) {
      break
    }
  }
  i
})

quantile(res,p)

95% 
148
Improve this answer
$\endgroup$
0
$\begingroup$

This problem is a generalisation of the classical coupon-collector problem. A reasonable way to find the solution would be to frame the process as a Markov chain. The random variable of interest here is the hitting time for the final state in the chain. I will suggest some basics to get you started on the problem, but you will need to have a look at material on hitting times for Markov chains to get a full solution.

To generalise your problem slightly, suppose you originally have $m$ objects in your set and you are selecting $k > 0$ random objects on each draw, via simple random sampling. If we let $K_n$ be the number of objects that have been selected (at least once) after $n$ draws then the process $\{ K_n | n \in \mathbb{N} \}$ is a discrete Markov chain with transition probabilities taken from the hypergeometric distribution:

$$p_{i,j} \equiv \mathbb{P}(K_{n+1} = j | K_n = i) = \frac{{i \choose k+i-j} {m-i \choose j-i}}{{m \choose k}} \quad \quad \quad \text{for all } i \leqslant j \leqslant i+k.$$

Now, if you form the Markov chain with states $0,...,m$, starting state $0$ and transition probabilities given by this equation then the random variable you are looking for is the hitting time for the state $m$. Getting the exact distribution for the hitting time is a somewhat involved exercise (it can be done by finding the eigen-decomposition of the transition probability matrix and using this to derive the CDF for the hitting time). Alternatively you can simulate the Markov chain a large number of times to estimate the distribution of interest. (The other answer here gives you a direct simulation of the process, but you can probably make this more efficient by simulating the Markov chain.)

I won't go further and give a full solution, but this ought to give you an idea of the general direction we could go to try to derive the distribution of the quantity of interest.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.