Usually I solve most problems of this type like this :

Basically lets say that you go from state X to state Yi with time ti and probability pi
The part of the expected cost would be

f(X) = sum pi*( ti + f(Y) )

Lets just think of this like a graph, now, if this is like a DAG kind of a graph, then you can easily use a recursive solution with memoization. If not, then it gets interesting,

basically you'd get a set of equations you've to solve now.

For example

f(A) = 1 + 0.5 * f(B) + 0.5*f(C)

f(B) = 1 + 0.5 * f(A) + 0.5*f(C)

f(C) = 0 

You need to solve these equations, maybe a problem has a pattern (most recent Topcoder Div1 900), if it doesn't you can use Gaussian Elimination to compute your required answers.

This is rather terse but I hope this helps.