Directed forests with application to algorithms related to Markov chains

• Autorzy: Piotr Pokarowski
• Języki publikacji: EN

Abstrakty

EN

This paper is devoted to computational problems related to Markov chains (MC) on a finite state space. We present formulas and bounds for characteristics of MCs using directed forest expansions given by the Matrix Tree Theorem. These results are applied to analysis of direct methods for solving systems of linear equations, aggregation algorithms for nearly completely decomposable MCs and the Markov chain Monte Carlo procedures.

Słowa kluczowe

EN

entrywise relative error; directed forest; Matrix Tree Theorem; directed graph; Simulated Annealing; Markov chains; Metropolis algorithm; direct methods for linear systems; nearly completely decomposable Markov chains; aggregation algorithms; nonhomogeneous Markov chains; Markov Chain Tree Theorem; Markov chain Monte Carlo algorithms; Gibbs sampler

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Applicationes Mathematicae
• Rocznik: 1999
• Tom: 26
• Numer: 4
• Strony: 395-414

Daty

wydano

1999

otrzymano

1998-09-26

Twórcy

autor

Piotr Pokarowski

• Institute of Mathematics, Polish Academy of Sciences, Śniadeckich 8, 00-950 Warsaw, Poland

Bibliografia

• [Al] D. Aldous, Reversible Markov chains and random walks on graphs, preprint, 1994.
• [Bo] V. S. Borkar, Pathwise recurrence orders and simulated annealing, J. Appl. Probab. 29 (1992), 472-476.
• [BoMa] R. Bott and J. P. Mayberry, Matrices and trees, in: Economic Activity Analysis, O. Morgenstern (ed.), Wiley, New York, and Chapman & Hall, London, 1953, 391-400.
• [Cha] S. Chaiken, A combinatorial proof of the all minors matrix tree theorem, SIAM J. Algebraic Discrete Methods 3 (1982), 319-329.
• [Che] W.-K. Chen, Applied Graph Theory, Graphs and Electrical Networks, 2nd ed., North-Holland, New York, 1976.
• [ChiCho] T.-S. Chiang and Y. Chow, Asymptotic behavior of eigenvalues and random updating schemes, Appl. Math. Optim. 28 (1993), 259-275.
• [ConKu] D. P. Connors and P. R. Kumar, Simulated annealing type Markov chains and their balance equations, SIAM J. Control Optim. 27 (1989), 1440-1461.
• [CvDoSa] D. M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs-Theory and Applications, Deutscher Verlag Wiss., Berlin, 1979, and Academic Press, New York, 1979.
• [DeKuKu] M. Desai, S. Kumar and P. R. Kumar, Quasi-statically cooled Markov chains, Probab. Engrg. Inform. Sci. 8 (1994), 1-19.
• [DiSt] P. Diaconis and D. Stroock, Geometric bounds for eigenvalues of Markov chains, Ann. Appl. Probab. 1 (1991), 36-61.
• [Din] I. H. Dinwoodie, A probability inequality for the occupation measure of a reversible Markov chain, ibid. 5 (1995), 37-43.
• [FieSe] M. Fiedler and J. Sedlácek, O w-basich orientovaných grafu, Čas. Pest. Mat. 83 (1958), 214-225 (in Czech).
• [FreWe 1] M. I. Freidlin and A. D. Wentzell, On small random perturbations of dynamical systems, Russian Math. Surveys 25 (1970), 1-55.
• [FreWe 2] M. I. Freidlin and A. D. Wentzell, Random Perturbations of Dynamical Systems, Springer, New York, 1984.
• [GrTaHe] W. K. Grassmann, M. I. Taksar and D. P. Heyman, Regenerative analysis and steady-state distributions for Markov chains, Oper. Res. 33 (1985) 1107-1116.
• [HasHav] R. Hassin and M. Haviv, Mean passage times and nearly uncoupled Markov chains, SIAM J. Discrete Math. 5 (1992), 386-397.
• [HeRe] D. P. Heyman and A. Reeves, Numerical solution of linear equations arising in Markov chain model, ORSA J. Comput. 1 (1989), 52-60.
• [Hi] T. L. Hill, Studies in irreversible thermodynamics IV. Diagrammatic representation of steady state fluxes for unimolecular systems, J. Theoret. Biol. 10 (1966), 442-459.
• [HwSh 1] C.-R. Hwang and S.-J. Sheu, Large-time behavior of perturbed diffusion Markov processes with applications to the second eigenvalue problem for Fokker-Planck operators and simulated annealing, Acta Appl. Math. 19 (1990), 253-295.
• [HwSh 2] C.-R. Hwang and S.-J. Sheu, Singular perturbed Markov chains and exact behaviors of simulated annealing processes, J. Theor. Probab. 5 (1992), 223-249.
• [In] S. Ingrassia, On the rate of convergence of the Metropolis algorithm and Gibbs sampler by geometric bounds, Ann. Appl. Probab. 4 (1994), 347-389.
• [Io] M. Iosifescu, Finite Markov Processes and Their Applications, Wiley, 1980.
• [KeSn] J. G. Kemeny and J. L. Snell, Finite Markov Chains, Van Nostrand, Princeton, 1960.
• [KiGeVe] S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, Optimization by simulated annealing, Science 220 (1983), 671-680.
• [KoVo] H. H. Kohler and E. Vollmerhaus, The frequency of cyclic processes in biological multistate systems, J. Math. Biol. 9 (1980), 275-290.
• [Me et al.] W. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller and E. Teller, Equations of state calculations by fast computing machines, J. Chem. Phys. 21 (1953), 1087-1092.
• [Mo] B. Mohar, The Laplacian spectrum of graphs, in: Y. Alavi et al. (eds.), Graph Theory, Combinatorics and Applications, Wiley, New York, 1991, 871-898.
• [Ni] W. Niemiro, Limit distributions of Simulated Annealing Markov chains, Discussiones Math. 15 (1993), 241-269.
• [NiPo] W. Niemiro and P. Pokarowski, Tail events of some nonhomogeneous Markov chains, Ann. Appl. Probab. 5 (1995), 261-293.
• [O'C] C. A. O'Cinneide, Entrywise perturbation theory and error analysis for Markov chains, Numer. Math. 65 (1993), 109-120.
• [Po 1] P. Pokarowski, Directed forests and algorithms related to Markov chains, Inst. Math., Polish Acad. Sci., 1997 (in Polish).
• [Po 2] P. Pokarowski, Uncoupling measures and eigenvalues of stochastic matrices, J. Appl. Anal. 4 (1998), 261-269.
• [RoWi 1] J. R. Rohlicek and A. S. Willsky, The reduction of Markov generators: An algorithm exposing the role of transient states, J. Assoc. Comput. Mach. 35 (1988), 675-696.
• [RoWi 2] J. R. Rohlicek and A. S. Willsky, Multiple time scale decomposition of discrete time Markov chains, Systems Control Lett. 11 (1988), 309-314.
• [RomSa] F. Romeo and A. Sangiovanni-Vincentelli, A theoretical framework for simulated annealing, Algorithmica 6 (1991), 367-418.
• [Sch 1] P. J. Schweitzer, Perturbation theory and finite Markov chains, J. Appl. Probab. 5 (1968), 401-413.
• [Sch 2] P. J. Schweitzer, Perturbation series expansions of nearly completely decomposable Markov chains, in: J. W. Cohen, O. J. Boxma and H. C. Tijm (eds.), Telegraphic Analysis and Computer Performance Evaluation, Elsevier, North-Holland, Amsterdam, 1986.
• [Sh] B. O. Shubert, A flow-graph formula for the stationary distribution of a Markov chain, IEEE Trans. Systems Man. Cybernet. 5 (1975), 565-566.
• [Si] A. Sinclair, Improved bounds for mixing rates of Markov chains and multicommodity flow, Combin. Probab. Comput. 1 (1992), 351-370.
• [So] A. D. Sokal, Monte Carlo Methods in Statistical Mechanics: Foundations and New Algorithms, Cours de Troisième Cycle de la Physique en Suisse Romande, Lausanne, June 1989 (unpublished).
• [Ste] G. W. Stewart, Introduction to Matrix Computations, Academic Press, New York, 1973.
• [Ste-W] W. J. Stewart, Introduction to the Numerical Solution Markov Chains, Princeton Univ. Press, Princeton, 1994.
• [We] A. D. Wentzell, On the asymptotics of eigenvalues of matrices with elements of order $exp (V_ij/2ε^2)$, Dokl. Akad. Nauk SSSR 202 (1972), 263-265 (in Russian); English transl.: Soviet Math. Dokl. 13 (1972), 65-68.