My Math Forum  

Go Back   My Math Forum > College Math Forum > Advanced Statistics

Advanced Statistics Advanced Probability and Statistics Math Forum


Reply
 
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!
zeroman89 is offline  
 
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 m-1 x m-1.

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.
Yooklid is offline  
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/
zeroman89 is offline  
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 [I-Q] matrix can be inverted in a reasonable amount of time using various numerical techniques.
Yooklid is offline  
Reply

  My Math Forum > College Math Forum > Advanced Statistics

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





Copyright © 2019 My Math Forum. All rights reserved.