Introduction
In the previous post, we discussed the expected number of steps to collect all verification codes. In this post, we will calculate the variance of the number of log-in tries to collect all verification codes.
Problem Statement
(See the previous post.) Let be a finite set of size . At the beginning, a set is initialized to be an empty set. For each step, a random element is chosen at uniformly random from and put to , i.e., . Let be the random variable that represents the number of steps to reach . Then, what is the variance of ?
Solution
Fix and let be the random variable for the number of steps to choose which has not been chosen when there are out of elements are not in . Then, we have where each are independent. Hence, we have where represents the variance.
Now, note that is the geometric distribution with parameter . The probability mass function of the geometric distribution with parameter is given by
Variance of Geometric Distribution
Well, one may calculate the variance by calculating
but I don’t want to do that. Instead, I will use the following formula:
where is the moment generating function. Calculating the moment generating function of , we get
where . Then, we have
(Yes, I calculated for you.) Now, we finally have
Finally Calculating the Variance
Now, we have
Hence, the variance we want to calculate is
In particular, the growth rate is where is the Riemann zeta function.
Conclusion
We have, and . Hence, in a high probability, I shall try times to collect all verification codes!