Expected value in dice game Consider the following game:

Successive rolls six six-sided dice are made.

In each roll some (o none) numbers are marked.

The goal is to mark the 6 numbers.

A number can be marked only if you have marked the previous number (in the current roll or earlier).

If $X$ is the number of rolls needed to win the game, what is the exact value of $\mathbf{E}[X]$?
In the two examples below they were obtained $X = 6$ and $X = 2$ (each row corresponds to a roll and green the marked numbers).

Win in six rolls:



Win in two rolls:
Start by computing the chance to get the next $n$ numbers you need.  The chance to get $0$ is $(\frac 56)^6$.  To get $1$, you need to get that one and not get the next one, so the chance is $6(\frac 16)(\frac 56)^5$.  To get $2$, the chance is ${6 \choose 2}(\frac 16)^2(\frac 56)^4$ and so on.  If you don't need that many, add in the chances of getting more.  

Let $x_i$ be the expected number of rolls given that you already have $i$ numbers.  If you already have $5$, the expected number of rolls is $x_5=1+(\frac 56)^6x_5$ because if you don't get a $6$ you are back where you started.  $x_5\approx 1.5035$  If you already have $4$, we have $x_4=1+6(\frac 16)(\frac 56)^5x_5+(1-(\frac 56)^6-6(\frac 16)(\frac 56)^5)x_4$ because on the next roll you might get them both, you might get $1$ and need $x_5$ more tries, or you might get none and need $x_4$ more tries.  They get messier each step, but the approach is the same.  If you are happy with numerics, you can put it into a spreadsheet.
Of the $46,656$ possible dice rolls:


each individual number appears $31,031$ times.
A 2-run starting at any particular number appears $19,502$ times.
3-runs appear $11,340$ times
4-runs appear $5,880$ times
5-runs appear $2,520$ times
$720$ rolls contain 6-runs.


These numbers do not exclude longer runs: for instance, only $19,502 - 11,340 = 8,162$ rolls have a run that goes 2-3 but not 2-3-4.  So transitioning from state 1 to state 3 only has $8,162$ possible ways it can happen.

With this information we can determine the state transition matrix:  

$$A = \frac{1}{46656}\left(\begin{matrix}
15,625 &amp; 11,529 &amp; 8,162 &amp; 5,460 &amp; 3,360 &amp; 1,800 &amp; 720 \\
0 &amp; 15,625 &amp; 11,529 &amp; 8,162 &amp; 5,460 &amp; 3,360 &amp; 2,520 \\
0 &amp; 0 &amp; 15,625 &amp; 11,529 &amp; 8,162 &amp; 5,460 &amp; 5,880 \\
0 &amp; 0 &amp; 0 &amp; 15,625 &amp; 11,529 &amp; 8,162 &amp; 11,340 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 15,625 &amp; 11,529 &amp; 19,502 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 15,625 &amp; 31,031 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 46,656
\end{matrix}\right)
$$

Finding the number of tries a typical game will take is then a matter of applying this matrix repeatedly to the start state, $(1, 0, 0, 0, 0, 0, 0)$; after $n$ applications, the value in the last slot will tell you the probability of the game having finished in $n$ or fewer rolls.

Unfortunately, the game is potentially infinite: there is no ironclad guarantee you'll ever see a particular number when you need it, so this appears (at first blush) to require an infinite number of additions.



But that's only at first blush.

The part that is potentially infinite here is simply this: that we will fail, potentially infinitely many times, to progress.  These are the $15,625$s along the diagonal: $(5/6)^6$ of the time we will not progress at all.  This is a geometric distribution!  On average it will take $\frac{46,656}{31,031}$ rolls to get a success.

With this we can make progress!

So the expected number of rolls to get from having the value $n$ to completing the task is $x_n$:

$x_6 = 0$

$x_5 = \frac{46,656 + 31,031x_6}{31,031}$

$x_4 = \frac{46,656 + 19,052x_6 + 11,529x_5}{31,031}$

$x_3 = \frac{46,656 + 11,340x_6 + 8,160x_5 + 11,529x_4}{31,031}$

etc.

This gets to some big fractions pretty quickly.  I've plugged it into Excel; it gave me $2.386$.  Honestly that feels low though!