Re: any tool/package to solve markov chain?

*To*: mathgroup at smc.vnet.net*Subject*: [mg51948] Re: [mg51869] any tool/package to solve markov chain?*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Fri, 5 Nov 2004 02:18:59 -0500 (EST)*References*: <200411040649.BAA18023@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Yan ZHANG wrote: > Now, I got a Markov chain and expressed as x=xP where x is the steady state > probability vector and P is the transition matrix. Since the dimension of P > is very big (up to 5000 * 5000), I am hoping that there is a tool or package > in MATHEMATICA to solve this? > > Can you please give some link or reference for this?Thank you very much for > your inforamtion. > What you want is an eigenvector for the eigenvalue of 1. For such matrices this is guaranteed to be the largest eigenvalue. So iterations of the power method will generally get you such a vector efficiently. Below I show an example. First we need to generate Markov matrices. randStochasticMat[dim_] := Transpose[(# / Map[Apply[Plus,#]&, #])& [ Table[Random[], {dim}, {dim}]]] For the steady-state vector iterations we will allow settings for maximum number of iterations and number of digits of agreement in the last two iterations as termination criteria. ssVector[mmat_, maxiters_:100, tol_:10] := Module[ {n, vec, oldvec}, n = Length[mmat]; vec = Table[Random[], {n}]; vec = vec / Norm[vec]; NestWhile [With[{nvec=mat.#}, nvec/Norm[nvec]]&, vec, (Max[Abs[#2-#1]]>10^(-tol))&, 2, maxiters] ] Here is an example (run on a 2.8 GHz machine with a Mathematica development kernel). In[4]:= Timing[mat = randStochasticMat[2000];] Out[4]= {1.7 Second, Null} In[7]:= Timing[ssvec = ssVector[mat];] Out[7]= {0.05 Second, Null} In[10]:= InputForm[Max[Abs[mat.ssvec - ssvec]]] Out[10]//InputForm= 2.3422583317334045*^-13 Daniel Lichtblau Wolfram Research

**References**:**any tool/package to solve markov chain?***From:*"Yan ZHANG" <buaanupt@sina.com>