.PEIN.'s blog

Where can I find expected value tutorial?
By .PEIN., 14 years ago, In English
Suppose I've to find what is the expected time to get out of a maze or expected number of item I can collect. Where can I find tutorial to solve these kind of problems.
  • Vote: I like it
  • 0
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hi,
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.
→ Reply