Analysing Failure probability of random sampling with replacement

36 Views Asked by At

I am trying to understand the failure probability of random sampling with replacement. Here is one problem instance.

Given a bag with M = 5 numbered balls (1, 2, 3, 4, and 5), from which the balls are sampled uniformly randomly and with replacement. Say the sampling step happens for r = 100 times. Now, what is the probability that

  1. One particular ball is never selected?

  2. One particular ball is selected less than $\delta$ times the expected number. For instance, in the above setting, each ball should be selected around 20 times. But say $\delta = 0.9$, then what is the probability that some ball is selected < 0.9 *20 = 18 times?

Here is my thinking that for Case 1: at each iteration, the sampler is only selecting from among 4 out of 5 balls hence the probability that one ball is never selected is $\left( \frac{4}{5} \right) ^r$

For Case 2: Sampler is selecting from among 4 out of 5 balls in the extra $\frac{(1-\delta) * r }{M}$ iterations. Hence the failure probability is $ \left( \frac{4}{5} \right) ^{\frac{(1-\delta) * r }{M}}$

Is my reasoning correct? Any suggestions.

Also any reference material where the failure probabilities have been analyzed would be very helpful. Thank You