
Advanced Statistics Advanced Probability and Statistics Math Forum 
 LinkBack  Thread Tools  Display Modes 
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,059 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 m1 x m1. Then the fundamental matrix N is given by: where I is the identity matrix. Now each element in N, 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,059 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 [IQ] matrix can be inverted in a reasonable amount of time using various numerical techniques. 

Tags 
expected, number, state, steps 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
State the domain  Shamieh  Calculus  1  October 30th, 2013 07:39 PM 
Prove and state transformation  Lucida  Algebra  3  March 31st, 2012 08:10 PM 
steady state of the equation  uterfor86  Applied Math  1  January 25th, 2012 02:49 PM 
finite state machine help!  lamhmh  Applied Math  1  July 28th, 2011 02:18 AM 
State a single vector  Calc12  Calculus  2  January 19th, 2011 05:59 PM 