Suppose we roll a die repeatedly and let Tk be the number of rolls until some number appears k times in a row.

Question

Suppose we roll a die repeatedly and let Tk be the number of rolls until some number appears k times in a row. (a) Find P(T2 = k) for each integer k ≥ 2. (b) Find E[T2].

I am thinking that P(T2=2) = (1/6)(1/6) ; P(T2=3) = (5/6)(1/6)^3 . So I was trying to develop the pattern : P(T2=k) = (5/6)^(k-2) * (1/6)^k . However, I run into the issue that I have with P(T2=4) : The first role has 5 options, the second has 4 (because it cannot be the previous OR the next number). So I cannot figure out the general formula.

** I also originally thought that for all k>3, P(T2+k) would be zero. Is that correct or is the above reasoning better?

Thanks!

Answer 1

Clearly we can't finish on the first roll. However, on every subsequent roll, we finish iff we roll the same as the roll before. That means at any point after the first throw, we have a $\frac16$ probability of finishing there, and a $\frac56$ probability of continuing the game one step further.

So the probabilities would be exactly the same if the game had been "Throw the die once first. Then after that, throw until you get a $6$." And throwing until you get a $6$ has an expected value of $6$ throws. Add in the first dummy throw at the start, and we see that the answer becomes $7$.

Answer 2

We can answer the question for a die with $n$ faces, rolling until some number appears $k$ times in row. We have for the probability that we need $m$ rolls where $m\ge k$ from first principles

$$\mathrm{P}[T=m] = \frac{1}{n^m} \frac{n}{n-1} [z^m] (n-1) z^k \sum_{q\ge 0} (z+\cdots+z^{k-1})^q (n-1)^q \\ = \frac{1}{n^m} \frac{n}{n-1} [z^m] (n-1) z^k \sum_{q\ge 0} z^q (1+\cdots+z^{k-2})^q (n-1)^q \\ = n \frac{1}{n^m} [z^m] z^k \sum_{q\ge 0} z^q (1-z^{k-1})^q (n-1)^q / (1-z)^q \\ = n \frac{1}{n^m} [z^m] z^k \frac{1}{1-(n-1)z(1-z^{k-1})/(1-z)} \\ = n \frac{1}{n^m} [z^m] z^k \frac{1-z}{1-z-(n-1)z+(n-1)z^{k}} \\ = n \frac{1}{n^m} [z^m] z^k \frac{1-z}{1-nz+(n-1)z^{k}}.$$

Let us verify that this is a probability distribution. We sum the probabilities to obtain

$$n\sum_{m\ge k} \frac{1}{n^m} [z^m] z^k \frac{1-z}{1-nz+(n-1)z^{k}} = n \frac{1}{n^k} \frac{1-1/n}{(n-1)/n^{k}} = \frac{n-1}{n-1} = 1$$

and the sanity check goes through. We continue with the expectation.

$$\mathrm{E}[T] = n\sum_{m\ge k} \frac{1}{n^m} m [z^m] z^k \frac{1-z}{1-nz+(n-1)z^{k}} \\ = n\sum_{m\ge k} \frac{1}{n^m} [z^{m-1}] \left(z^k \frac{1-z}{1-nz+(n-1)z^{k}}\right)' \\ = \sum_{m\ge k} \frac{1}{n^{m-1}} [z^{m-1}] \left(\frac{kz^{k-1}-(k+1)z^k}{1-nz+(n-1)z^{k}} - \frac{(z^k-z^{k+1})((n-1)kz^{k-1}-n)}{(1-nz+(n-1)z^k)^2} \right) \\ = \frac{k/n^{k-1}-(k+1)/n^k}{(n-1)/n^{k}} - \frac{(1/n^k-1/n^{k+1})((n-1)k/n^{k-1}-n)}{(n-1)^2/(n^k)^2} \\ = \frac{nk-(k+1)}{n-1} - \frac{(1-1/n)((n-1)k/n^{k-1}-n)}{(n-1)^2/n^k} \\ = \frac{(n-1)k-1}{n-1} - \frac{1}{n} \frac{((n-1)k/n^{k-1}-n)}{(n-1)/n^k} \\ = k-\frac{1}{n-1} - \frac{1}{n} \frac{n(n-1)k-n^{k+1}}{n-1} = k-\frac{1}{n-1} - \frac{(n-1)k-n^{k}}{n-1}.$$

This yields the desired answer

$$\bbox[5px,border:2px solid #00A000]{ \mathrm{E}[T] = \frac{n^k-1}{n-1}.}$$