If I roll an M-sided dice N times per second, what is the expected time elapsed until I roll a specific fixed value V at least once? And how long do I need to wait to be certain to a certain degree, say two standard deviations (95%), that I have gotten said specific value at least once?
My attempt so far:
As far as I have understood, this is a case of independent trial. and $p=1/M$ . The expected value should be $E(X) = 1/p = M$. This would take me $t=M/N$ s.
So if I have a 6-sided dice and I roll it 2 times per second, I would expect to roll a specific value, like 4, after M = 6 rolls, or in 6/2 = 3s
But how about the variance? According to wikipedia, the variance of the geometric distribution is $(1-p)/p^2$, which in the example would mean that $\sigma^2 = (1-1/M)/(1/M)^2=M^2(1-1/M)=M^2-M$, and the stddev would be $\sigma=\sqrt(M^2-M)$. In the 6-sided example that's $\sigma=\sqrt(6^2-6)=\sqrt(30)\approx5.47$ rolls. To be certain to two standard deviations, that would then mean I'd have to wait $E(X)+2\sigma$ = $6+2\sqrt(30)\approx16.95$ rolls, or $16.95/2\approx8.47$ seconds. Is that correct?
One thing that threw me off is that I get a different result if I calculate per second instead. So in the 6-sided example, I roll twice per second. Then the actual chance of success per second, rolling at least one 4, is $1-(5/6)*(5/6)=11/36$. If you now consider each second a single experiment and then calculate the expected value, you get $E=36/11\approx3.27$s, which is different than 3s, which I get if I calculate per roll. Why is that?
There is a simple reason the two methods give different answers. When you roll two times per second, the time it takes is either an integer number of seconds, or an integer number plus one half. However, in the second formulation where you count the number of seconds instead of the number of rolls, the answer is always an integer number of seconds, so you are effectively rounding up to the nearest integer. This is why the second method gives a larger answer. The correct answer is that it takes $M$ rolls on average, so $M/N$ seconds.
For the variance calculation, when you say that two standard deviations above gives $95\%$ certainty, you are implicitly approximating the geometric distribution with a normal distribution. However, there is no need for approximations, because this problem can be exactly answered easily. After $R$ rolls, the probability you have seen the value at least once is $1-(1-\frac1M)^R$. For this to be greater than $0.95$, you need $$ R>\frac{\ln(0.05)}{\ln(1-\frac1{M})} $$ Therefore, the number of rolls you need to get $95\%$ certainty of seeing the desired value is given by the above formula.