4
$\begingroup$

I am trying to simulate a process as an absorbing Markov chain model, but I haven't been able to find the scenario that I am interested in looking at in the typical discussions of Markov chains online. Hoping someone out there will have some pointers.

In the chain I am building, there are certain transitions between states that have a certain utility or value. Values are always non-negative. The majority of transitions have zero value, but the few that have values are what's important in this analysis. I am interested in the expected sum of values from all transitions until the chain reaches an absorbing state (there could be more than one absorbing state).

In other words, as the chain evolves, it will pass through certain transitions that have value > 0, and I want to know the expected value the chain accumulates before it ends in an absorbing state.

Is there standard terminology for what I'm trying to describe? What would be the best way to go about finding this value?

I'd also be interested in the probability distribution of which absorbing state the chain terminates in, although that's less important that the expected value.

I will need to test numerous Markov chains with the same set of states, but different transition probabilities to see how the expected value changes.

One strategy that occurs to me is that I could change the transitions that have positive values to a transition into/out of a dummy state, so if I could count the number of expected visits to each dummy state, I could weight them by the values of their transitions appropriately and get the expected value that way. So an alternate form of the question might be, how can you count the expected number of visits to a particular state in an absorbing Markov chain?

I would prefer to implement this in R, especially if there's a package that already does some portion of this. OpenBUGS might be an option too if it makes sense (through R via package rbugs, although I haven't used any BUGS software before).

Any guidance on how to approach this problem or recommendations on tools to solve it would be appreciated.

$\endgroup$
3
  • $\begingroup$ To give an idea of how to guide you, maybe you could mention what stochastic-process texts you are familiar and comfortable with. $\endgroup$
    – cardinal
    Nov 3, 2011 at 20:34
  • $\begingroup$ Mostly one of my 20-year-old college textbooks. I don't have it in front of me at the moment, but with some help from Amazon I think it's either Karlin & Taylor "Second Course in Stochastic Processes" or Hoel/Port/Stone's "Intro to Stochastic Processes". I've been trying to supplement that with online searches for more papers or class notes on the topic. $\endgroup$ Nov 4, 2011 at 14:35
  • $\begingroup$ Ok, great. Good to know what you have at your disposal and your level of familiarity. The Karlin & Taylor texts, of course, provide a very rich background. $\endgroup$
    – cardinal
    Nov 4, 2011 at 14:44

1 Answer 1

0
$\begingroup$

The fundamental matrix $N$ gives the expected number of times that a particular state is reached, given an initial state. From this you can get the probability of being absorbed in a particular absorbing state as $NR$, where $R$ describes the transition probabilities from transient to absorbing states.

Then the expectation of your value function, given an initial state $i$ is $$ \sum_{j\in T} n_{ij}v_j + \sum_{j\in A} b_{ij}v_j, $$ where $S$ is the state space, $T$ is the set of transient states, $A$ is the set of absorbing states, and $n_{ij}$ and $b_{ij}$ are, respectively, the elements of the fundamental matrix $N$ and the matrix $B = NR$.

If your value function is random and has mean values $\mu_j$, replace $v_j$ by $\mu_j$ in the displayed equation above.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.