Directed forests with application to algorithms related to Markov chains

 Access to full text

 Full (PDF)

1. [Al] D. Aldous, Reversible Markov chains and random walks on graphs, preprint, 1994. 
2. [Bo] V. S. Borkar, Pathwise recurrence orders and simulated annealing, J. Appl. Probab. 29 (1992), 472-476. Zbl0754.60079
3. [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. 
4. [Cha] S. Chaiken, A combinatorial proof of the all minors matrix tree theorem, SIAM J. Algebraic Discrete Methods 3 (1982), 319-329. Zbl0495.05018
5. [Che] W.-K. Chen, Applied Graph Theory, Graphs and Electrical Networks, 2nd ed., North-Holland, New York, 1976. 
6. [ChiCho] T.-S. Chiang and Y. Chow, Asymptotic behavior of eigenvalues and random updating schemes, Appl. Math. Optim. 28 (1993), 259-275. Zbl0785.15010
7. [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. Zbl0681.60061
8. [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. 
9. [DeKuKu] M. Desai, S. Kumar and P. R. Kumar, Quasi-statically cooled Markov chains, Probab. Engrg. Inform. Sci. 8 (1994), 1-19. 
10. [DiSt] P. Diaconis and D. Stroock, Geometric bounds for eigenvalues of Markov chains, Ann. Appl. Probab. 1 (1991), 36-61. Zbl0731.60061
11. [Din] I. H. Dinwoodie, A probability inequality for the occupation measure of a reversible Markov chain, ibid. 5 (1995), 37-43. Zbl0829.60022
12. [FieSe] M. Fiedler and J. Sedlácek, O w-basich orientovaných grafu, Čas. Pest. Mat. 83 (1958), 214-225 (in Czech). 
13. [FreWe 1] M. I. Freidlin and A. D. Wentzell, On small random perturbations of dynamical systems, Russian Math. Surveys 25 (1970), 1-55. Zbl0297.34053
14. [FreWe 2] M. I. Freidlin and A. D. Wentzell, Random Perturbations of Dynamical Systems, Springer, New York, 1984. 
15. [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. Zbl0576.60083
16. [HasHav] R. Hassin and M. Haviv, Mean passage times and nearly uncoupled Markov chains, SIAM J. Discrete Math. 5 (1992), 386-397. Zbl0754.60071
17. [HeRe] D. P. Heyman and A. Reeves, Numerical solution of linear equations arising in Markov chain model, ORSA J. Comput. 1 (1989), 52-60. Zbl0757.65156
18. [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. 
19. [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. Zbl0708.60056
20. [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. Zbl0755.60047
21. [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. Zbl0802.60061
22. [Io] M. Iosifescu, Finite Markov Processes and Their Applications, Wiley, 1980. 
23. [KeSn] J. G. Kemeny and J. L. Snell, Finite Markov Chains, Van Nostrand, Princeton, 1960. 
24. [KiGeVe] S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, Optimization by simulated annealing, Science 220 (1983), 671-680. Zbl1225.90162
25. [KoVo] H. H. Kohler and E. Vollmerhaus, The frequency of cyclic processes in biological multistate systems, J. Math. Biol. 9 (1980), 275-290. Zbl0433.60075
26. [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. 
27. [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. Zbl0840.05059
28. [Ni] W. Niemiro, Limit distributions of Simulated Annealing Markov chains, Discussiones Math. 15 (1993), 241-269. Zbl0854.60067
29. [NiPo] W. Niemiro and P. Pokarowski, Tail events of some nonhomogeneous Markov chains, Ann. Appl. Probab. 5 (1995), 261-293. Zbl0826.60055
30. [O'C] C. A. O'Cinneide, Entrywise perturbation theory and error analysis for Markov chains, Numer. Math. 65 (1993), 109-120. 
31. [Po 1] P. Pokarowski, Directed forests and algorithms related to Markov chains, Inst. Math., Polish Acad. Sci., 1997 (in Polish). 
32. [Po 2] P. Pokarowski, Uncoupling measures and eigenvalues of stochastic matrices, J. Appl. Anal. 4 (1998), 261-269. 
33. [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. Zbl0643.60057
34. [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. Zbl0658.60102
35. [RomSa] F. Romeo and A. Sangiovanni-Vincentelli, A theoretical framework for simulated annealing, Algorithmica 6 (1991), 367-418. Zbl0717.90061
36. [Sch 1] P. J. Schweitzer, Perturbation theory and finite Markov chains, J. Appl. Probab. 5 (1968), 401-413. Zbl0196.19803
37. [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. 
38. [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. Zbl0344.60040
39. [Si] A. Sinclair, Improved bounds for mixing rates of Markov chains and multicommodity flow, Combin. Probab. Comput. 1 (1992), 351-370. Zbl0801.90039
40. [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). 
41. [Ste] G. W. Stewart, Introduction to Matrix Computations, Academic Press, New York, 1973. 
42. [Ste-W] W. J. Stewart, Introduction to the Numerical Solution Markov Chains, Princeton Univ. Press, Princeton, 1994. 
43. [We] A. D. Wentzell, On the asymptotics of eigenvalues of matrices with elements of order $exp(V_{i}j/2{\epsilon }^2)$, Dokl. Akad. Nauk SSSR 202 (1972), 263-265 (in Russian); English transl.: Soviet Math. Dokl. 13 (1972), 65-68.