No way to extract the transition matrix from a Markov chain?
I'm experimenting with using Lea to analyze Markov chains. As an example, rules for rolling dice in certain games can be modelled as a Markov chain (a simplified example - roll 2 dice, rerolling doubles, is an absorbing chain where (n, m) is an absorbing state if n != m, and transitions to a new rolled pair if n == m).
One thing I'd like to do is extract the transition matrix from a Chain
object. I can do this using the private _next_state_lea_per_state
attribute, and deconstructing the Alea
object for each starting state - but that's a little messy, and uses private information.
Is there a better way that I've missed? And if not, could one be added?
(Actually, Lea in general seems to make it hard to extract the underlying representation of an object - the best way I've found of getting the probability values for an Alea
object is list(zip(obj.support, obj.ps))
which is a little non-obvious (neither "support" nor "ps" are attribute names I would have immediately thought of).
Comments (31)
-
repo owner -
repo owner -
assigned issue to
-
assigned issue to
-
reporter I'm only really playing with Markov chains. There are some specific things I'm interested in, but they may not be particularly appropriate for Lea (and once I have the transition matrix, they aren't that hard to produce manually).
Specifically:
- Is a Markov chain absorbing? (The ones I'm working with are, by construction, but checking that fact before I continue is not a bad idea).
- Extract the number of transient states and the number of absorbing states.
- Put the transition matrix into canonical form (trying to lay this out messes up Bitbucket's formatting, but basically 4 quadrants, Q in the upper left, R in the upper right, a zero matrix in the lower left and an identity matrix in the lower right - you probably already know this) and extract Q and R.
- Calculate the fundamental matrix
(I-Q)**(-1)
The matrix arithmetic really needs numpy (at least, it seems silly to avoid numpy) so would probably have to be optional in Lea anyway. So (4) probably isn't suitable for Lea.
Suggestions:
# The name here is problematic as currently the states method does # something different. But I can't think of a better name for a list of # the states (as Python objects, not probability distributions) all_states = chain.states() # Boolean chain.is_absorbing() # A subset of all_states absorbing = chain.absorbing_states() transition_matrix = chain.transition_matrix() # This is a bit long, not sure if it can be shortened? q, r = chain.transition_matrix_canonical_decomposition()
-
repo owner OK. That sounds interesting and general enough to be integrated in Lea. Let me work on this. Hopefully, I'll commit soon something that you could review.
-
repo owner Fix markov.Chain.str to keep order of states unchanged (refs
#44)→ <<cset b8fa6e6453a9>>
-
repo owner Add methods matrix, reachable_states and absorbing_mc_info in markov.Chain (refs
#44)→ <<cset 278d731f148b>>
-
repo owner Document and change names of attributes/arguments of markov.Chain to be clearer (refs
#44)→ <<cset 4dd78701aecb>>
-
repo owner Correct markov.Chain.matrix method (refs
#44)→ <<cset 9d097bd9a25a>>
-
repo owner Hi Paul,
Sorry for the long delay! I’ve eventually done something on the topic of absorbing MC (I know that you were able to manage, by hard ways, to get the information you need).
Everything is currently on the branch dev_upgrade_markov_chains of lea (to be merged on the main branch). There are 3 new methods on
markov.Chain
:absorbing_mc_info
,matrix
andreachable_states
. The first is the main one, the last two are auxiliary but these could be helpful as such. These methods are documented in the code. Here is an example of use, for an absorbing MC:mc = markov.chain_from_matrix( ( 'A' , 'B', 'C' ), ( 'A', ( 0.5 , 0.3 , 0.2 )), ( 'B', ( 0.0 , 1.0 , 0.0 )), ( 'C', ( 0.3 , 0.5 , 0.2 ))) print(mc.states) # -> ('A', 'B', 'C') print(mc.matrix()) # -> ((0.5, 0.3, 0.2), (0.0, 1.0, 0.0), (0.3, 0.5, 0.2)) print(mc.absorbing_mc_info()) # -> (True, ('A', 'C'), ('B',), ((0.5, 0.2), (0.3, 0.2)), ((0.3,), (0.5,)))
Notes:
- Unlike your suggestions, I’ve preferred to return all data in one single method (
absorbing_mc_info
) because these are closely interdependent. - So far, numpy is not used in the methods; also, the fundamental matrix is not calculated. However, as I’ve done for other dependencies, I may envision an optional support to numpy, for example by adding an optional Boolean arg on
absorbing_mc_info
for asking to get Q/R matrices as numpy arrays and provide (I-Q)**(-1) at the end of the output tuple. - Of course, there remain work to do, at least: adding tests and documenting the new features on the wiki.
I would appreciate if you can give some feedback on these points before I go on.
- Unlike your suggestions, I’ve preferred to return all data in one single method (
-
repo owner - changed status to open
-
repo owner In markov.Chain, fix reachable_states method to remove duplicates and fix absorbing_mc_info to keep order of states (refs
#44)→ <<cset 4aa43be14e96>>
-
reporter Hi, The above looks good to me. I haven't done much more since my original experiments - even though I had to play with internal attributes, that was enough to solve the problem I was working on at the time. But my solution would have been much cleaner with the new methods you're adding here. Optional numpy-based calculation of the fundamental matrix sounds like a reasonable way to go (although of course, it's possible to do that myself using the data you currently return in
absorbing_mc_info
). -
repo owner Thanks for your feedback, Paul. I continue to elaborate this way then.
-
repo owner In markov.Chain, add as_array argument in matrix and absorbing_mc_info methods to return numpy arrays and calculate the fundamental matrix (refs
#44)→ <<cset 1b5fae309d7b>>
-
repo owner Add test_markov.py (refs
#44)→ <<cset fa82826f96d8>>
-
repo owner Add tests in test_markov.py (refs
#44)→ <<cset c773039d7f99>>
-
repo owner Merge dev_upgrade_markov_chains (refs
#44)→ <<cset d7527ea7d638>>
-
repo owner Hi, The new features are documented here on the wiki. I've just released Lea 3.1.0.beta.1, which includes these new features. If something is wrong or improvable, it's still time to react.
-
repo owner - changed status to resolved
-
reporter Looks awesome, thanks so much for doing this :-)
-
repo owner - changed status to closed
-
repo owner Keep ordering of states given in the matrix (refs
#44)→ <<cset 0d1fbe8194a7>>
-
repo owner Fix markov.Chain.str to keep order of states unchanged (refs
#44)→ <<cset 3fb0dc6928e7>>
-
repo owner Add methods matrix, reachable_states and absorbing_mc_info in markov.Chain (refs
#44)→ <<cset 7642b9871393>>
-
repo owner Document and change names of attributes/arguments of markov.Chain to be clearer (refs
#44)→ <<cset a5d3539b9da6>>
-
repo owner Correct markov.Chain.matrix method (refs
#44)→ <<cset 8f60bbcef022>>
-
repo owner In markov.Chain, fix reachable_states method to remove duplicates and fix absorbing_mc_info to keep order of states (refs
#44)→ <<cset b480b7acd7af>>
-
repo owner In markov.Chain, add as_array argument in matrix and absorbing_mc_info methods to return numpy arrays and calculate the fundamental matrix (refs
#44)→ <<cset d69cd41b6260>>
-
repo owner Add test_markov.py (refs
#44)→ <<cset 43a7be542aaa>>
-
repo owner Add tests in test_markov.py (refs
#44)→ <<cset 927f7dcab563>>
-
repo owner Merge dev_upgrade_markov_chains (refs
#44)→ <<cset 9722a6f7167e>>
- Log in to comment
Hi Paul,
Happy to see your interest in Markov chain, a topic, which is for sure not much elaborated in Lea!
Let me first answer on the last point. Your need is addressed by methods described in the third part of the tutorial. You could for example replace your non-obvious expression by
obj.pmf_tuple
(well, you get a tuple, not a list!). I think that I should move this section in the first part of the wiki because it's seemingly a basic need of many users.Now, about the main question, indeed, you didn’t miss anything. There is nothing out-of-the-box to get the transition matrix easily. Python is hopefully tolerant on accessing private attribute : as you have discovered already, you can get the transition NxN matrix as N tuple of N probabilities by
and get the associated state names with
Definitely, I’m willing to add such access methods in Lea package. Now, is it exactly what you want? What method names would be meaningful? BTW, would it be sensible to rename
_next_state_lea_per_state
and promote it as public (and duly document it)?Yes,… It’s now time to give your wish list. :)