What is the probability that all faces have appeared in some order in some six consecutive rolls?

We roll a 6-sided die n times. What is the probability that all faces have appeared in some order in some six consecutive rolls?

Is there a way to do this without resorting to markov chains?

Solution 1:

You can compute the result numerically by a recursion or (equivalently) by a Markov chain formulation. The advantage of the former is that you can do some asympotics (as Thomas Andrews showed in the comments).

For completeness, here's the recursion.

Let define the state, $X_t$ as the length of the longest trailing subsequence with different values, after $t=1,2 \cdots$ tries, if the target subsequence (six different values) has not yeat appear, $X_t=6$ otherwise. Let $p(x,t)=P(X_t =x)$.

Hence $X_1=1$ , and we want $p(6,t)$

The recursion is

$$ p(x,t+1)=\begin{cases} \displaystyle{ \frac{6-(x-1)}{6} p(x-1,t) + \frac16 \sum_{k=x}^5 p(k,t)} & {\rm if } \; x=1,2\cdots 5 \\ \displaystyle{ p(6,t) + \frac{1}{6} p(5,t)} & {\rm if }\; x=6 \end{cases} $$

This can be computed numerically, for example with a spreadsheet:

https://docs.google.com/spreadsheets/d/1SJRlXaaS2K1YYNfa7QFcJ29Ks6M2nVf9mlbIteNWwrY

The last column shows the approximation from Thomas Andrews.