My Math Forum Expected number of steps to go from state i to state j

 October 3rd, 2010, 11:42 PM #1 Newbie   Joined: Sep 2010 Posts: 4 Thanks: 0 Expected number of steps to go from state i to state j Hey guys, I have a problem in probability: Given a probability matrix P with size of NxN. P[i, j] is the probability of changing from state i to state j, (0 <= P[i, j] <= 1). P[i, j] and P[j, i] can be distinct. You can assume that sum of elements on the row ith (for every 1 <= i <= N) is always equal to 1. How to calculate the expected number of step to go from state 1 to state N ? I think it can be solved by dynamic programming, but there're still some problems: Let E(i) the expected number of step to go from state i to state N => E(1) will be the result. We have the following formula: E(i) = 1 + Sum( P[i, j] * E(j) ) for every j = 1..N But if so, E(i) and E(j) will depend on each other. Therefore, if we do dynamic programming, when should we stop it ? If someone have any ideas, plz show me ! Thanks!
 October 7th, 2010, 01:40 AM #2 Senior Member   Joined: Jul 2008 From: Western Canada Posts: 5,165 Thanks: 46 Re: Expected number of steps to go from state i to state j It's been a while since I've done this. So, hopefully I won't lead you astray. Create a transitional matrix Q by deleting the row and column from matrix P that correspond to the absorbing state. In your example, j is the absorbing state, so delete row j and column j. Hence, if P was an m x m matrix, then Q will be m-1 x m-1. Then the fundamental matrix N is given by: $N=[I-Q]^{-1}$ where I is the identity matrix. Now each element in N, $n_{ik}$ is the number of times that the process will be in state k if it began in state i, before being absorbed. So, to get the mean number of steps, starting in state i, before being absorbed in state j, simply sum all the elements in row i of matrix N. For more details and proofs, refer to 'Finite Markov Chains' by Kemeny & Snell, Chapter 3.
 October 7th, 2010, 02:38 AM #3 Newbie   Joined: Sep 2010 Posts: 4 Thanks: 0 Re: Expected number of steps to go from state i to state j Firstly, thank you for your help. It could also be a solution to this problem. But actually, my problem is given in the grid of size MxN (1 <= M, N <= 40). I want to calculate the expected number of steps to go from cell (1, 1) to (M, N). At a time, each cell will only move to one of 4 neighboring cells with some given probabilities. Because of its quite large size, if we use above approach to consider each square cell on the grid as a vertex on the graph then we will have at most 1600 vertices. Therefore, the matrix's size is too large to compute its inverse ! I wonder if this problem can be solve by a simpler approach that can be programmed quite easily such as Dynamic Programming..! Here's the link for my problem, you can try it as you want http://www.codechef.com/LMDPLA10/problems/ADVTRIP/
 October 7th, 2010, 02:35 PM #4 Senior Member   Joined: Jul 2008 From: Western Canada Posts: 5,165 Thanks: 46 Re: Expected number of steps to go from state i to state j Okay, I didn't know that it was required to use DP for the solution. No doubt then, the problem can be solved with DP. For a one time problem, I generally take the lazy approach and program the easiest algorithm that can will execute in a reasonable amount of time. In other words, I'd rather spend 5 minutes writing a program that takes 10 minutes to run, rather than spend 2 hours to write a program that runs in less than a second. Of course, if this is for something that would be used over and over again, then it's worth spending more time on an efficient algorithm. BTW, A 1600 x 1600 [I-Q] matrix can be inverted in a reasonable amount of time using various numerical techniques.

 Tags expected, number, state, steps

expected years to go from state i to state j

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Shamieh Calculus 1 October 30th, 2013 07:39 PM Lucida Algebra 3 March 31st, 2012 08:10 PM uterfor86 Applied Math 1 January 25th, 2012 02:49 PM lamhmh Applied Math 1 July 28th, 2011 02:18 AM Calc12 Calculus 2 January 19th, 2011 05:59 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top