In consecutive throws of an ordinary die, which of the following two possibilities is more likely to happen first:

a) Two successive occurrences of 5 or

b) Three successive appearances of numbers divisible by 3?

I thought that "time to event" random variable follows a geometric distribution. In the first case the probability of the event would be $p_1=1/36$ so the waiting time would be $E(X_1)=\frac{1-p_1}{p_1}=35$, plus 2 (for the successive occurrences of 5) = 37.

Accordingly the probability of the second event would be $p_2=\frac{2^3}{6^3}$ and the waiting time for the second event would be $E(X_2)=\frac{1-p_2}{p_2}=26$, plus 3 = 29.

As I was not sure about the validity of the above considerations, I decided to try some monte carlo simulations (the code can be found here: http://ideone.com/TbLdDe). According to the results, the second event will happen first, indeed. But the expected values are larger than the ones calculated before (About 42 and 39, accordingly)

What is the right way to calculate the waiting time?

  • 2
    $\begingroup$ "I thought that "time to event" random variable follows a geometric distribution." -- you have overgeneralized. Some 'number of trials to event A' variables have a geometric distribution, but many other distributions occur (e.g. 'number of trials to the second success in Bernoulli trials' is not geometric, but negative binomial). When you seek several of the same event in a row you generally don't have a geometric. $\endgroup$ – Glen_b -Reinstate Monica Mar 27 '14 at 9:26
  • 1
    $\begingroup$ my simulations match yours: general function here for 1 in n probability, r repeats, N trials: repeated<- function(n,r,N) { s<-rle(sample(1:n,N,replace=T)); mean(sapply(1:n, function (x) sum(s$lengths)/sum(s$lengths[s$values==x]%/%r))) } $\endgroup$ – TooTone Mar 27 '14 at 13:18

Generalizing the problem, let $X$ be the random variable for the number of trials it takes to achieve $r$ successes in a row, with $p=$ the probability of success.

The probability of having no successes in a row at time $t$, for $t\ge 1$, is the probability of a failure at time $t$ preceeded by a sequence to time $t-1$ that has not yet had $r$ successes, which is: $$(1-p)(1-P(X\le t-1))$$

The probability of having $r$ successes at time $t+r$ following no successes at time $t$ is: \begin{align} P(X=t+r) &= p^r(1-p)(1-P(X\le t-1)) \\ P(X=t+r+1) &= p^r(1-p)(1-P(X\le t)) \end{align} Then taking sums from $t=0$ to $\infty$: \begin{align} \sum_{t=0}^\infty P(X=t+r+1) &= \sum_{t=0}^\infty p^r(1-p)(1-P(X\le t))\\ \sum_{t=0}^\infty P(X=t) - \sum_{t=0}^r P(X=t) &= p^r(1-p)\sum_{t=0}^\infty (1-P(X\le t))\\ \end{align}

Finally using the facts that:

  • the sum of a probability distribution is 1: $\sum_{t=0}^\infty P(X=t) = 1$
  • the probabilities of seeing $r$ successes in the first $r$ trials are trivially $P(X=t)=0$ for $t<r$ and $P(X=r)=p^r$
  • the expectation of a random variable taking non-negative values can be written in terms of its cumulative distribution function: $E[X] = \sum_{x=0}^\infty (1-F(x))$

we have

$$E(X) = \frac1{p^r(1-p)}(1-p^r)$$

For $r=1$, as expected this simplifies to the same formula as for the geometric distribution: $E(X) = 1/p$.

The cases

  • $p=1/6, r=2 \implies E(X)=6^3/5\times(1-1/6^2)=42$, and
  • $p=1/3,r=3 \implies E(X)= 3^4/2\times(1-1/3^3)=39$

confirm your simulations.

  • $\begingroup$ Very nice proof! Have you seen it in a book? If yes, which one? $\endgroup$ – Brani Mar 28 '14 at 7:21
  • 1
    $\begingroup$ thankyou, no the proof is not from a book (although there is nothing new under the sun so no doubt it's in a book or a solution to an exercise somewhere). It's a simpler version of a technique I used to find the mean in this answer. $\endgroup$ – TooTone Mar 28 '14 at 10:57

I don't have a full solution but perhaps it's relevant that the pattern 55 is embedded in itself (I think the term for this is "not prefix free"?). That is, the first time to get a 55 is greater than the time to get the second 55 because the second 55 can occur immediately, as in the sequence "32555". So if we let X1 be waiting time for first 55 and X2 be waiting time for second 55 and E[5] be average waiting time for just a 5 then I think E[X1] = E[X2] + E[5]. My guess for E[X2] was 36 and E[5] is 6, which gives 42 for the first 55 as you calculated.

  • $\begingroup$ My simulation stops when the first 55 appears, so there is no chance for a 555 $\endgroup$ – Brani Mar 27 '14 at 8:43
  • 1
    $\begingroup$ I think that's the point, though. That is, the theories (Blackwell's theorem?) generally apply to asymptotic limits (i.e. in your case, the time to wait for the 2nd set of 55), whereas your simulation is just for the first one, so the theory won't apply directly. Maybe you can simulate to see if the second set of 55's comes after 35 or 36 trials. But as I wrote, I'm not an expert on these issues, so it will be interesting to see what others have to say! $\endgroup$ – user42628 Mar 27 '14 at 9:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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