[idbfs]

A simple, principled way of solving October's problem is to model it as a Markov chain with absorbing states (the "Finish" square, and the two invisible squares past it -- the two invisible squares are unnecessary as mentioned by jtsummers below), and compute the expected absorption time starting from the first square.

See e.g. http://en.wikipedia.org/wiki/Absorbing_Markov_chain

[Jtsummers]

Since this seems to only care about the probability of any transition would you need the 2 invisible squares, or wouldn't the "Finish" square suffice? That is, in any square that can advance to 12 (10, 11) 10 has a 1/3 probability of advancing to 11, and 2/3 of hitting 12/13. While 11 has a probability of reaching 12 (or beyond) of 1.

Also, thanks for that link. Markov chains are something I know about, but never really set to the task of learning. It's also a much quicker solution than my initial concept, and neatly handles the chute/ladder squares (that is, on square 5 you'd have a 1/3 chance of ending on 11, 1/3 on 2 and 1/3 on 8; 6 and 7 are never actually reached - which also means they can be eliminated from the set of states).

[idbfs]

Yes, you're right. Good point.

[CurtMonash]

Quite so.

I'd say there simple are 8 possible states -- nominally 12, but 2 each are collapsed via chutes and ladders.

If I had to solve it by hand, however, I wouldn't try to invert an 8x8 matrix. Rather, I'd write it down as a simple system of linear equations. Let f1, ..., f12 be the expected number of steps to completion if you start in position 1, ..., 12.

f12 = 0. f11 = 1. f10 = (f11 + f12 + f12)/3 + 1. f9 = f8, because of the chute. f8 = (f9 + f10 + f11)/3 + 1.

and so on.

[Pitarou]

That's exactly how I did it. It's straightforward.