I have a system that is a Markov chain. It is in principle possible to calculate the trasition matrix, given a set of parameters of the system. Calculation may take long but it can be done for some reasonable sets of parameters. Sometimes what I get is a trasition matrix that is to big to be managed by my digital computer (it requires to much memory - but I didn't try to save it on my hard drive). Are there any methods of algorithmically manipulating large Markov chains "by pieces", so to speak? Or perhaps there are some other methods of calculating various properties of systems that correspond to very large Markov chains?
In my case, I get absorbing Markov chains and I would like to calculate various properties, like probability of absorption or expected number of steps to being absorbed etc. Of course, there are appropriate formulae but they are useless if you cannot make the computation.
Possibly the best of the solvers of very big Markov chains that I know of was produced by Will Knottenbelt ([email protected]) when he was my PhD student, and subsequently. The software is called DNAmaca and usually it has a Petri net interface (but not necessarily). It can solve MCs of arbitrary structure (many of the others need special structures like BDDs) with as many as 50M states if you have a cluster of nodes. It used to do over 10M on a single processor as I recall.
Huge Markov chains have a large literature.
You need to use sparse matrix representation and out-of-core solution methods for the linear system of equations.
Just write "out-of-core Markov chain" into google and you get many relevant hits.
How is the Markov chain structured? Is it discrete-time or continuous time? If it is continuous-time, Possibly you can use unifromization or randomizatio (see uniformization (probability) in Wikipedia). In this case, you need to store only the non-zero entries of your matrix. Also, for both discrete-time and continuous-time Markov chains, you usually can only reach a relatively small number of states in one step when starting from a particular state, and you can generate the particular transition rates (or probabilities) on the fly.
Hi,
Can you please give an idea about the data/Matrices dimensions?
Best,
We have a population of N individuals each of which can be in M states. Each function from the set of individuals to the set of states is a state of the Markov chain. So we have M^N states for which we would like to compute transition probabilities. Therefore we have an M^N x M^N matrix of transition probabilities. Say we would like to analyse population of 10 individuals each of which can be in 10 different states. We get 10^10 x 10^10 matrix. However, we would like to analyse larger populations but the size of the population is in the exponent... How far can I get with the computational and memory capabilities of contemporary solutions?
You might wanna look at factored Markov chains. I know research group of Pascal Poupart had some software on this.
You may consider SPNP like software packages to automatically generate and solve large Markov chains. Alternatively use hierarchical/fixed-point iterative methods via software package such as SHARPE. Many real-life large problems are solved using these methods in my latest book: Reliability and Availability Modeling by Cambridge University Press, 2017.
In the attachement I point out the two methods I have used in dealing with this problem
One method is the Recursive Queue Analyzer developed by Wallace and Rosenberg, which represent the CTMC with a regular structure compactly
and then uses the power method
I have experimented with using less detailed representations to solve the same problem -- in my case serialization delays --I had a paper in Perfomanc'83 dealing with one job class and in 1993 with two job classes-
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms