Directed forests with application to algorithms related to Markov chains

Pokarowski, Piotr

Applicationes Mathematicae, Tome 26 (1999), p. 395-414 / Harvested from The Polish Digital Mathematics Library

Résumé

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.

Détail

Publié le : 1999-01-01

Zbl 0998.60070

EUDML-ID : urn:eudml:doc:219248

Bibliographie

[000] [Al] D. Aldous, Reversible Markov chains and random walks on graphs, preprint, 1994.

[001] [Bo] V. S. Borkar, Pathwise recurrence orders and simulated annealing, J. Appl. Probab. 29 (1992), 472-476. | Zbl 0754.60079

[002] [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.

[003] [Cha] S. Chaiken, A combinatorial proof of the all minors matrix tree theorem, SIAM J. Algebraic Discrete Methods 3 (1982), 319-329. | Zbl 0495.05018

[004] [Che] W.-K. Chen, Applied Graph Theory, Graphs and Electrical Networks, 2nd ed., North-Holland, New York, 1976.

[005] [ChiCho] T.-S. Chiang and Y. Chow, Asymptotic behavior of eigenvalues and random updating schemes, Appl. Math. Optim. 28 (1993), 259-275. | Zbl 0785.15010

[006] [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. | Zbl 0681.60061

[007] [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.

[008] [DeKuKu] M. Desai, S. Kumar and P. R. Kumar, Quasi-statically cooled Markov chains, Probab. Engrg. Inform. Sci. 8 (1994), 1-19.

[009] [DiSt] P. Diaconis and D. Stroock, Geometric bounds for eigenvalues of Markov chains, Ann. Appl. Probab. 1 (1991), 36-61. | Zbl 0731.60061

[010] [Din] I. H. Dinwoodie, A probability inequality for the occupation measure of a reversible Markov chain, ibid. 5 (1995), 37-43. | Zbl 0829.60022

[011] [FieSe] M. Fiedler and J. Sedlácek, O w-basich orientovaných grafu, Čas. Pest. Mat. 83 (1958), 214-225 (in Czech).

[012] [FreWe 1] M. I. Freidlin and A. D. Wentzell, On small random perturbations of dynamical systems, Russian Math. Surveys 25 (1970), 1-55. | Zbl 0297.34053

[013] [FreWe 2] M. I. Freidlin and A. D. Wentzell, Random Perturbations of Dynamical Systems, Springer, New York, 1984.

[014] [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. | Zbl 0576.60083

[015] [HasHav] R. Hassin and M. Haviv, Mean passage times and nearly uncoupled Markov chains, SIAM J. Discrete Math. 5 (1992), 386-397. | Zbl 0754.60071

[016] [HeRe] D. P. Heyman and A. Reeves, Numerical solution of linear equations arising in Markov chain model, ORSA J. Comput. 1 (1989), 52-60. | Zbl 0757.65156

[017] [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.

[018] [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. | Zbl 0708.60056

[019] [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. | Zbl 0755.60047

[020] [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. | Zbl 0802.60061

[021] [Io] M. Iosifescu, Finite Markov Processes and Their Applications, Wiley, 1980.

[022] [KeSn] J. G. Kemeny and J. L. Snell, Finite Markov Chains, Van Nostrand, Princeton, 1960.

[023] [KiGeVe] S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, Optimization by simulated annealing, Science 220 (1983), 671-680. | Zbl 1225.90162

[024] [KoVo] H. H. Kohler and E. Vollmerhaus, The frequency of cyclic processes in biological multistate systems, J. Math. Biol. 9 (1980), 275-290. | Zbl 0433.60075

[025] [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.

[026] [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. | Zbl 0840.05059

[027] [Ni] W. Niemiro, Limit distributions of Simulated Annealing Markov chains, Discussiones Math. 15 (1993), 241-269. | Zbl 0854.60067

[028] [NiPo] W. Niemiro and P. Pokarowski, Tail events of some nonhomogeneous Markov chains, Ann. Appl. Probab. 5 (1995), 261-293. | Zbl 0826.60055

[029] [O'C] C. A. O'Cinneide, Entrywise perturbation theory and error analysis for Markov chains, Numer. Math. 65 (1993), 109-120.

[030] [Po 1] P. Pokarowski, Directed forests and algorithms related to Markov chains, Inst. Math., Polish Acad. Sci., 1997 (in Polish).

[031] [Po 2] P. Pokarowski, Uncoupling measures and eigenvalues of stochastic matrices, J. Appl. Anal. 4 (1998), 261-269.

[032] [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. | Zbl 0643.60057

[033] [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. | Zbl 0658.60102

[034] [RomSa] F. Romeo and A. Sangiovanni-Vincentelli, A theoretical framework for simulated annealing, Algorithmica 6 (1991), 367-418. | Zbl 0717.90061

[035] [Sch 1] P. J. Schweitzer, Perturbation theory and finite Markov chains, J. Appl. Probab. 5 (1968), 401-413. | Zbl 0196.19803

[036] [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.

[037] [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. | Zbl 0344.60040

[038] [Si] A. Sinclair, Improved bounds for mixing rates of Markov chains and multicommodity flow, Combin. Probab. Comput. 1 (1992), 351-370. | Zbl 0801.90039

[039] [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).

[040] [Ste] G. W. Stewart, Introduction to Matrix Computations, Academic Press, New York, 1973.

[041] [Ste-W] W. J. Stewart, Introduction to the Numerical Solution Markov Chains, Princeton Univ. Press, Princeton, 1994.

[042] [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.