Bibliography

• [1] S.R. Adke and S.M. Manjunath(1984) An introduction to finite markov processes. Wiley. Cited by: 2.9.
• [2] R.J. Adler and R. Epstein(1987) Some central limit theorems for Markov paths and some properties of Gaussian random fields. Stochastic Process. Appl. 24, pp. 157–202. Cited by: 14.6.2.
• [3] M. Ajtai, J. Komlós and E. Szemerédi(1983) Sorting in $c\log n$ parallel steps. Combinatorica 3, pp. 1–19. Cited by: 10.6.
• [4] M. Ajtai, J. Komlós and E. Szemerédi(1987) Deterministic simulation in logspace. pp. 132–140. Cited by: 10.4.1, 10.6, 10.6.
• [5] D.J. Aldous and A. Bandyopadhyay(2001) How to combine fast heuristic Markov chain Monte Carlo with slow exact sampling. Note: Unpublished Cited by: 11.6.2.
• [6] D.J. Aldous and M. Brown(1992) Inequalities for rare events in time-reversible Markov chains I. Lecture Notes, Vol. 22, pp. 1–16. Cited by: 3.8.
• [7] D.J. Aldous and P. Diaconis(1986) Shuffling cards and stopping times. Amer. Math. Monthly 93, pp. 333–348. Cited by: 4.7, 9.7.
• [8] D.J. Aldous and P. Diaconis(1987) Strong uniform times and finite random walks. Adv. in Appl. Math. 8, pp. 69–97. Cited by: 4.7, 7.1.7, 7.4, 9.7.
• [9] D.J. Aldous and B. Larget(1992) A tree-based scaling exponent for random cluster models. J. Phys. A: Math. Gen. 25, pp. L1065–L1069. Cited by: 9.7.
• [10] D.J. Aldous, L. Lovász and P. Winkler(1997) Mixing times for uniformly ergodic Markov chains. Stochastic Process. Appl. 71, pp. 165–185. Cited by: 13.4.
• [11] D.J. Aldous(1982) Markov chains with almost exponential hitting times. Stochastic Process. Appl. 13, pp. 305–310. Cited by: 3.8.
• [12] D.J. Aldous(1982) Some inequalities for reversible Markov chains. J. London Math. Soc. (2) 25, pp. 564–576. Cited by: 10.9, 4.3.1, 4.3.2, 4.3.2, 4.7, 4.7.
• [13] D.J. Aldous(1983) Minimization algorithms and random walk on the d-cube. Ann. Probab. 11, pp. 403–413. Cited by: 10.4.2.
• [14] D.J. Aldous(1983) On the time taken by random walks on finite groups to visit every state. Z. Wahrsch. Verw. Gebiete 62, pp. 361–374. Cited by: 13.4, 7.4.
• [15] D.J. Aldous(1983) Random walks on finite groups and rapidly mixing Markov chains. Seminaire de Probabilites XVII, pp. 243–297. Note: Lecture Notes in Math. 986 Cited by: 12.2, 14.8.
• [16] D.J. Aldous(1987) On the Markov chain simulation method for uniform combinatorial distributions and simulated annealing. Probab. Engineering Inform. Sci. 1, pp. 33–46. Cited by: 4.7, 7.1.8.
• [17] D.J. Aldous(1988) Finite-time implications of relaxation times for stochastically monotone processes. Probab. Th. Rel. Fields 77, pp. 137–145. Cited by: 4.7, 9.5, 9.5.
• [18] D.J. Aldous(1989) Hitting times for random walks on vertex-transitive graphs. Math. Proc. Cambridge Philos. Soc. 106, pp. 179–191. Cited by: 3.8, 7.1.4, 7.4.
• [19] D.J. Aldous(1990) The random walk construction of uniform spanning trees and uniform labelled trees. SIAM J. Discrete Math. 3, pp. 450–465. Cited by: 9.7.
• [20] D.J. Aldous(1991) Meeting times for independent Markov chains. Stochastic Process. Appl. 38, pp. 185–193. Cited by: 14.2.
• [21] D.J. Aldous(1991) Random walk covering of some special trees. J. Math. Analysis Appl. 157, pp. 271–283. Cited by: 13.4, 6.6.2, 6.9, 6.27.
• [22] D.J. Aldous(1991) The continuum random tree II: an overview. pp. 23–70. Cited by: 13.4.
• [23] D.J. Aldous(1991) Threshold limits for cover times. J. Theoretical Probab. 4, pp. 197–211. Cited by: 6.33.
• [24] D.J. Aldous(1995) On simulating a Markov chain stationary distribution when transition probabilities are unknown. IMA Volumes in Mathematics and its Applications, Vol. 72, pp. 1–9. Cited by: 9.3.2, 9.3.2.
• [25] R. Aleliunas(1979) Random walks, universal traversal sequences, and the complexity of maze traversal. pp. 218–233. Cited by: 4.7, 6.1, 6.8.1, 6.8.2, 6.9, 6.34.
• [26] N. Alon, U. Feige, A. Wigderson and D. Zuckerman(1995) Derandomized graph products. Comput. Complexity 5, pp. 60–75. Cited by: 10.7.3, 3.8.
• [27] N. Alon and Y. Roichman(1994) Random Cayley graphs and expanders. Random Struct. Alg. 5, pp. 271–284. Cited by: 13.4.
• [28] N. Alon and J. H. Spencer(1992) The probabilistic method. Wiley. Cited by: 1.1.3, 10.7.2, 6.9.
• [29] N. Alon(1986) Eigenvalues and expanders. Combinatorica 6, pp. 83–96. Cited by: 10.6, 4.7.
• [30] V. Anantharam and P. Tsoucas(1989) A proof of the Markov chain tree theorem. Stat. Probab. Letters 8, pp. 189–192. Cited by: 9.7.
• [31] W.J. Anderson(1991) Continuous-time Markov chains. Springer–Verlag. Cited by: 2.9, 5.4, 5.4.
• [32] D. Applegate, R. Kannan and N. Polson(1990) Random polynomial time algorithms for sampling from joint distributions. Technical report Carnegie-Mellon. Cited by: 5.2.
• [33] D. Applegate and R. Kannan(1991) Sampling and integration of log-concave functions. pp. 156–163. Cited by: 10.6, 5.2.
• [34] S. Asmussen, P.W. Glynn and H. Thorisson(1992) Stationarity detection in the initial transient problem. ACM Trans. Modeling and Computer Sim. 2, pp. 130–157. Cited by: 9.7.
• [35] S. Asmussen(1987) Applied probability and queues. Wiley. Cited by: 2.9, 4.7.
• [36] L. Babai(1991) Local expansion of vertex-transitive graphs and random generation in finite groups. pp. 164–174. Cited by: 10.7.3, 3.8, 7.1.8.
• [37] L. Babai(1994) Probably true theorems, cry wolf?. Notices Amer. Math. Soc. 41, pp. 453–454. Cited by: 10.3.1.
• [38] P. Baldi and Y. Rinott(1989) Asymptotic normality of some graph-related statistics. J. Appl. Probab. 26, pp. 171–175. Cited by: 14.8.
• [39] C. Bandle(1980) Isoperimetric inequalities and applications. Pitman, Boston MA. Cited by: 4.4.3.
• [40] M.T. Barlow(1991) Random walks and diffusions on fractals. pp. 1025–1035. Cited by: 13.4.
• [41] M.T. Barlow(1998) Diffusions on fractals. Lecture Notes in Math., Vol. 1690. Cited by: 13.4.
• [42] G. Barnes and U. Feige(1996) Short random walks on graphs. SIAM J. Discrete Math. 9, pp. 19–28. Cited by: 6.9.
• [43] M.F. Barnsley and J.H. Elton(1988) A new class of Markov processes for image encoding. Adv. in Appl. Probab. 20, pp. 14–32. Cited by: 9.7.
• [44] J.R. Baxter and R.V. Chacon(1976) Stopping times for recurrent Markov processes. Illinois J. Math. 20, pp. 467–475. Cited by: 2.10.1.
• [45] K.A. Berman and M. Konsowa(1990) Random paths, electrical networks and reversible Markov chains. SIAM J. Discrete Math. 3, pp. 311–319. Cited by: 3.8.
• [46] J. Besag and P.J. Greene(1993) Spatial statistics and Bayesian computation. J. Royal Statist. Soc. (B) 55, pp. 25–37. Note: Followed by discussion Cited by: 11.7.
• [47] S. Bhatt and J. Cai(1993) Taking random walks to grow trees in hypercubes. J. Assoc. Comput. Mach. 40, pp. 741–764. Cited by: 10.4.3, 10.4.3.
• [48] N. L. Biggs(1974) Algebraic graph theory. Cambridge University Press. Cited by: 7.4, 7.
• [49] N. L. Biggs(1993) Potential theory on distance-regular graphs. Combin. Probab. Comput. 2, pp. 243–255. Cited by: 7.3.4, 7.3.
• [50] L.J. Billera and P. Diaconis(2000) A geometric interpretation of the Metropolis algorithm. Note: Unpublished Cited by: 11.7.
• [51] N. H. Bingham(1991) Fluctuation theory for the Ehrenfest urn. Adv. in Appl. Probab. 23, pp. 598–611. Cited by: 5.4, 5.4, 5.4.
• [52] D. Boivin(1993) Weak convergence for reversible random walks in a random environment. Ann. Probab. 21, pp. 1427–1440. Cited by: 13.3.6.
• [53] B. Bollobás(1985) Random graphs. Academic Press, London. Cited by: 9.3.1.
• [54] B. Bollobás(1988) The isoperimetric number of random regular graphs. European J. Combin. 9, pp. 241–244. Cited by: 13.4.
• [55] E. Bolthausen(1980) The Berry-Esseen theorem for functionals of discrete Markov chains. Z. Wahrsch. Verw. Gebiete 54, pp. 59–73. Cited by: 4.7.
• [56] A. Borodin, W.L. Ruzzo and M. Tompa(1992) Lower bounds on the length of universal traversal sequences. J. Computer Systems Sci. 45, pp. 180–203. Cited by: 6.9.
• [57] K. Borre and P. Meissl(1974) Strength analysis of leveling-type networks. Geodaetisk Institut, Copenhagen. Note: Volume 50 Cited by: 3.7.1, 3.8.
• [58] O. Bottema(1935) Uber die Irrfahrt in einem Strassennetz. Math. Z. 39, pp. 137–145. Cited by: 3.8.
• [59] R.C. Bradley, W. Bryc and S. Janson(1987) On dominations between measures of dependence. J. Multivariate Anal. 23, pp. 312–329. Cited by: 4.7.
• [60] L.A. Breyer and G.O. Roberts(1998) From Metropolis to diffusions: Gibbs states and optimal scaling. Technical report Statistical Lab., Cambridge U.K.. Cited by: 11.7.
• [61] G. Brightwell and P. Winkler(1990) Extremal cover times for random walks on trees. J. Graph Theory 14, pp. 547–554. Cited by: 6.7.
• [62] G. Brightwell and P. Winkler(1990) Maximum hitting time for random walks on graphs. Random Struct. Alg. 1, pp. 263–276. Cited by: 6.11.
• [63] P.J. Brockwell and R.A. Davis(1987) Time series: theory and methods. Springer–Verlag. Cited by: 11.7.
• [64] A. Broder, A.R. Karlin, P. Raghavan and E. Upfal(1989) Trading space for time in undirected $s-t$ connectivity. pp. 543–549. Cited by: 6.4.1, 6.8.2, 6.9.
• [65] A. Broder and A.R. Karlin(1989) Bounds on the cover time. J. Theoretical Probab. 2, pp. 101–120. Cited by: 3.8, 3.8, 6.9.
• [66] A. Broder and E. Shamir(1987) On the second eigenvalue of random regular graphs. pp. 286–294. Cited by: 13.4.
• [67] A. Z. Broder, A. M. Frieze and E. Upfal(1994) Existence and construction of edge disjoint paths on expander graphs. SIAM J. Comput. 23, pp. 976–989. Cited by: 10.2.2.
• [68] A. Z. Broder, A. M. Frieze and E. Upfal(1999) Static and dynamic path selection on expander graphs: a random walk approach. Random Struct. Alg. 14, pp. 87–109. Cited by: 10.6.
• [69] A. Broder(1986) How hard is it to marry at random? (on the approximation of the permanent). pp. 50–58. Cited by: 10.5.2.
• [70] A. Broder(1989) Generating random spanning trees. pp. 442–447. Cited by: 9.7.
• [71] A.E. Brouwer, A.M. Cohen and A. Neumaier(1989) Distance regular graphs. Springer–Verlag. Cited by: 7.2.4, 7.3.4, 7.3, 7.3, 7.4.
• [72] M. Brown(1983) Approximating IMRL distributions by exponential distributions, with applications to first passage times. Ann. Probab. 11, pp. 419–427. Cited by: 3.5.4, 3.8.
• [73] M. Brown(1990) Consequences of monotonicity for Markov transition functions. Technical report City College, CUNY. Cited by: 3.8, 3.8, 9.7.
• [74] M. Brown(1999) Interlacing eigenvalues in time reversible Markov chains. Math. Oper. Res. 24, pp. 847–864. Cited by: 3.8.
• [75] M.J.A.M. Brummelhuis and H.J. Hilhorst(1991) Covering of a finite lattice by a random walk. Physica A 176, pp. 387–408. Cited by: 7.4.
• [76] D. Brydges, S.N. Evans and J.Z. Imbrie(1992) Self-avoiding walk on a hierarchical lattice in four dimensions. Ann. Probab. 20, pp. 82–124. Cited by: 13.4.
• [77] R. Bubley, M. Dyer and C. Greenhill(1998) Beating the $2\Delta$ bound for approximately counting colorings: a computer-assisted proof of rapid mixing. New York, pp. 355–363. Cited by: 12.1.12, 12.2.
• [78] R. Bubley, M. Dyer and M. Jerrum(1998) An elementary analysis of a procedure for sampling points in a convex body. Random Struct. Alg. 12, pp. 213–235. Cited by: 10.5.1, 11.6.1, 13.1.3.
• [79] R. Bubley and M. Dyer(1997) Path coupling: a technique for proving rapid mixing in Markov chains. pp. 223–231. Cited by: 12.1.12.
• [80] R. Bubley and M. Dyer(1999) Faster random generation of linear extensions. Discrete Math. 201, pp. 81–88. Cited by: 12.1.13.
• [81] F. Buckley and F. Harary(1990) Distance in graphs. Addison-Wesley. Cited by: 5.3.1.
• [82] K. Burdzy and W.S. Kendall(2000) Efficient Markovian couplings: examples and counterexamples. Ann. Appl. Probab. 10, pp. 362–409. Cited by: 13.4.
• [83] R. Burton and R. Pemantle(1993) Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances. Ann. Probab. 21, pp. 1329–1371. Cited by: 9.7, 9.7.
• [84] E.A. Carlen, S. Kusuoka and D.W. Stroock(1987) Upper bounds for symmetric Markov transition functions. Ann. Inst. H. Poincaré Probab. Statist. Suppl. 2, pp. 245–287. Cited by: 6.9.
• [85] A.K. Chandra, P. Raghavan, W.L. Ruzzo, R. Smolensky and P. Tiwari(1996/7) The electrical resistance of a graph captures its commute and cover times. Comput. Complexity 6, pp. 312–340. Note: Extended abstract originally published in Proc. 21st ACM Symp. Theory of Computing (1989) 574-586 Cited by: 10.6, 13.2.3, 3.3.3, 3.8, 6.9.
• [86] G. Chartrand and L. Lesniak(1986) Graphs and digraphs. 2nd edition, Wadsworth, Monterey CA. Cited by: 4.1, 6.5.1.
• [87] J. Cheeger(1970) A lower bound for the lowest eigenvalue for the Laplacian. pp. 195–199. Cited by: 4.7.
• [88] M. F. Chen(1992) From Markov chains to non-equilibrium particle systems. World Scientific, Singapore. Cited by: 1.2.3, 3.8, 3.8.
• [89] M. F. Chen(1996) Trilogy of couplings and general formulas for lower bound of spectral gap. Lecture Notes in Statistics, pp. 123–136. Cited by: 13.4.
• [90] M. F. Chen(1999) Eigenvalues, inequalities and ergodic theory II. Adv. Math. (China) 28, pp. 481–505. Cited by: 13.4.
• [91] M.-H. Chen, Q.-M. Shao and J.G. Ibrahim(2000) Monte carlo methods in bayesian computation. Springer–Verlag. Cited by: 11.7.
• [92] F.R.K. Chung, P. Diaconis and R. L. Graham(1987) A random walk problem arising in random number generation. Ann. Probab. 15, pp. 1148–1165. Cited by: 7.4.
• [93] F.R.K. Chung and S.-T. Yau(1995) Eigenvalues of graphs and Sobolev inequalities. Combin. Probab. Comput. 4, pp. 11–25. Cited by: 3.8.
• [94] F.R.K. Chung(1979) On concentrators, superconcentrators, and nonblocking networks. Bell System Tech. J. 58, pp. 1765–1777. Cited by: 13.4.
• [95] F.R.K. Chung(1997) Spectral graph theory. CBMS Regional Conference Series in Mathematics, Vol. 92, Amer. Math. Soc.. Cited by: 1.2.3, 10.1.1, 10.2, 10.6, 10.6, 10.6.
• [96] K.L. Chung(1967) Markov chains with stationary transition probabilities. Second edition, Springer–Verlag. Cited by: 2.9.
• [97] A. Cohen and A. Widgerson(1989) Dispensers, deterministic amplification, and weak random sources. pp. 14–19. Cited by: 10.6.
• [98] A. Condon and D. Hernek(1994) Random walks on colored graphs. Random Struct. Alg. 5, pp. 285–303. Cited by: 6.9.
• [99] D. Coppersmith, P. Doyle, P. Raghavan and M. Snir(1993) Random walks on weighted graphs and applications to on-line algorithms. J. Assoc. Comput. Mach. 40, pp. 421–453. Cited by: 10.4.4, 10.10, 3.8, 3.8.
• [100] D. Coppersmith, U. Feige and J. Shearer(1996) Random walks on regular and irregular graphs. SIAM J. Discrete Math. 9, pp. 301–308. Cited by: 6.9, 6.9.
• [101] D. Coppersmith, P. Tetali and P. Winkler(1993) Collisions among random walks on a graph. SIAM J. Discrete Math. 6, pp. 363–374. Cited by: 3.1.1, 3.8.
• [102] M.K. Cowles and B.P. Carlin(1996) Markov chain Monte Carlo convergence diagnostics: a comparative review. J. Amer. Statist. Assoc. 91, pp. 883–904. Cited by: 11.7.
• [103] J.T. Cox and D. Griffeath(1990) Mean field asymptotics for the planar stepping stone model. Proc. London Math. Soc. 61, pp. 189–208. Cited by: 14.8.
• [104] J.T. Cox(1989) Coalescing random walks and voter model consensus times on the torus in $Z^{d}$. Ann. Probab. 17, pp. 1333–1366. Cited by: 14.3.3, 14.3.5.
• [105] S. L. Cuéllar-Montoya(1997) A rapidly mixing stochastic system of finite interacting particles on the circle. Stochastic Process. Appl. 67, pp. 69–99. Cited by: 14.7.
• [106] D.M. Cvetkovic, M. Doob, I. Gutman and A. Torgasev(1988) Recent results in the theory of graph spectra. North-Holland. Note: Annals of Discrete Math. 36 Cited by: 10.6.
• [107] D.M. Cvetkovic, M. Doob and H. Sachs(1980) Spectra of graphs. Academic Press. Cited by: 10.6, 3.8.
• [108] C. Dellacherie and P.-A. Meyer(1983) Probabilités et potentiel: théorie discrète du potentiel. Hermann, Paris. Cited by: 9.7.
• [109] L. Devroye and A. Sbihi(1990) Random walks on highly-symmetric graphs. J. Theoretical Probab. 3, pp. 497–514. Cited by: 7.3.2, 7.4.
• [110] L. Devroye and A. Sbihi(1992) Inequalities for random walks on trees. Vol. 2, pp. 35–45. Cited by: 6.9.
• [111] L. Devroye(1986) Nonuniform random number generation. Springer–Verlag. Cited by: 11.7.
• [112] P. Diaconis and J.A. Fill(1990) Examples for the theory of strong stationary duality with countable state spaces. Prob. Engineering Inform. Sci. 4, pp. 157–180. Cited by: 4.7, 9.7.
• [113] P. Diaconis and J.A. Fill(1990) Strong stationary times via a new form of duality. Ann. Probab. 18, pp. 1483–1522. Cited by: 4.7, 5.1.3, 9.7.
• [114] P. Diaconis, R.L. Graham and J.A. Morrison(1990) Asymptotic analysis of a random walk on a hypercube with many dimensions. Random Struct. Alg. 1, pp. 51–72. Cited by: 5.2.
• [115] P. Diaconis and L. Saloff-Coste(1993) Comparison theorems for random walk on finite groups. Ann. Probab. 21, pp. 2131–2156. Cited by: 14.5.1, 14.8, 7.1.9, 7.2.1, 7.4, 8.1, 8.1, 8.3, 8.
• [116] P. Diaconis and L. Saloff-Coste(1993) Comparison theorems for reversible Markov chains. Ann. Appl. Probab. 3, pp. 696–730. Cited by: 8.1, 8.1, 8.1, 8.1, 8.
• [117] P. Diaconis and L. Saloff-Coste(1996) Logarithmic Sobolev inequalities for finite Markov chains. Ann. Appl. Probab. 6, pp. 695–750. Cited by: 8.4.1, 8.4.2, 8.4.2, 8.4.3, 8.4.3, 8.4, 8.
• [118] P. Diaconis and L. Saloff-Coste(1996) Nash inequalities for finite Markov chains. J. Theoretical Probab. 9, pp. 459–510. Cited by: 8.2.3, 8.
• [119] P. Diaconis and L. Saloff-Coste(1998) What do we know about the Metropolis algorithm?. J. Comput. System Sci. 57, pp. 20–36. Cited by: 11.7.
• [120] P. Diaconis and M. Shahshahani(1981) Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete 57, pp. 159–179. Cited by: 7.2.1, 8.9.
• [121] P. Diaconis and M. Shahshahani(1986) Time to reach stationarity in the Bernouilli-Laplace diffusion model. SIAM J. Math. Anal. 18, pp. 208–218. Cited by: 7.3.2.
• [122] P. Diaconis and D. Stroock(1991) Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Probab. 1, pp. 36–61. Cited by: 3.8, 4.4.3, 4.4.3, 4.5.2, 4.7.
• [123] P. Diaconis(1988) Group representations in probability and statistics. Institute of Mathematical Statistics, Hayward CA. Cited by: 1.2.3, 5.2, 5.2, 7.2.1, 7.3.2, 7.3.5, 7.4, 7, 8.9, 9.1.3.
• [124] P. Diaconis(1996) Notes on the hit-and-run algorithm. Note: Unpublished Cited by: 11.2.2.
• [125] I.H. Dinwoodie(1995) A probability inequality for the occupation measure of a reversible Markov chain. Ann. Appl. Probab. 5, pp. 37–43. Cited by: 10.7.1.
• [126] W. Doeblin(1938) Exposé de la theorie des chaînes simples constantes de Markov à un nombre fini d’états. Rev. Math. Union Interbalkanique 2, pp. 77–105. Cited by: 12.2.
• [127] P. Donnelly, P. Lloyd and A. Sudbury(1994) Approach to stationarity of the Bernouilli-Laplace diffusion model. Adv. in Appl. Probab. 26, pp. 715–727. Cited by: 7.3.2.
• [128] P. Donnelly and D. Welsh(1983) Finite particle systems and infection models. Math. Proc. Cambridge Philos. Soc. 94, pp. 167–182. Cited by: 14.8.
• [129] P. Donnelly and D. Welsh(1984) The antivoter problem: random $2$-colourings of graphs. pp. 133–144. Cited by: 14.4, 14.4, 14.8.
• [130] C. Dou and M. Hildebrand(1996) Enumeration and random random walks on finite groups. Ann. Probab. 24, pp. 987–1000. Cited by: 13.4.
• [131] P.G. Doyle and J.L. Snell(1984) Random walks and electrical networks. Mathematical Association of America, Washington DC. Cited by: 1.2.3, 13.2.2, 3.3.3, 3.7.1, 3.8, 3.8.
• [132] R. Durrett(1988) Lecture notes on particle systems and percolation. Wadsworth, Pacific Grove CA. Cited by: 14.3.3, 14.8, 14.
• [133] R. Durrett(1991) Probability: theory and examples. Wadsworth, Pacific Grove CA. Cited by: 1.2.2, 1.2.3, 13.1.1, 13.1.1, 13.1.4, 13.1.6, 13.2.1, 13.2.2, 13.2.4, 13.4, 2.3, 2.3, 2.5.3, 2.8.1, 2.8.3, 2.9, 2.9, 3.5.3, 3.7, 4.7, 4.7, 6.2, 7.4.
• [134] M. Dyer, A. Frieze and R. Kannan(1989) A random polynomial time algorithm for approximating the volume of convex bodies. pp. 375–381. Cited by: 10.5.1.
• [135] M. Dyer, A. Frieze and R. Kannan(1991) A random polynomial time algorithm for approximating the volume of convex bodies. J. Assoc. Computing Machinery 38, pp. 1–17. Cited by: 10.5.1.
• [136] M. Dyer and A. Frieze(1991) Computing the volume of convex bodies: a case where randomness provably helps. Proc. Symp. Applied Math., Vol. 44, pp. 123–170. Cited by: 10.6.
• [137] M. Dyer and C. Greenhill(1998) A genuinely polynomial-time algorithm for sampling two-rowed contingency tables. Technical report University of Leeds, U.K.. Note: Unpublished Cited by: 12.2.
• [138] M.L. Eaton(1997) Admissability in quadratically regular problems and recurrence of symmetric Markov chains: why the connection?. J. Statist. Plann. Inference 64, pp. 231–247. Cited by: 13.4.
• [139] R.G. Edwards and A.D. Sokal(1988) Generalization of the Fortuin-Kasteleyn-Swendsen-Wang representation and Monte Carlo algorithm. Phys. Rev. D 38, pp. 2009–2012. Cited by: 11.7.
• [140] B. Efron and C. Stein(1981) The jackknife estimate of variance. Ann. Statist. 10, pp. 586–596. Cited by: 4.7.
• [141] S.N. Ethier and T. G. Kurtz(1986) Markov processes: characterization and convergence. Wiley, New York. Cited by: 13.1.1.
• [142] U. Feige(1995) A tight lower bound on the cover time for random walks on graphs. Random Struct. Alg. 6, pp. 433–438. Cited by: 6.6.4.
• [143] U. Feige(1995) A tight upper bound on the cover time for random walks on graphs. Random Struct. Alg. 6. Cited by: 6.12.
• [144] U. Feige(1996/7) Collecting coupons on trees, and the cover time of random walks. Comput. Complexity 6, pp. 341–356. Cited by: 6.12, 6.15.
• [145] W. Feller(1971) An introduction to probability theory and its applications. 2nd edition, Vol. II, Wiley. Cited by: 14.6.2.
• [146] M. Fiedler, C.R. Johnson, T.L. Markham and M. Neumann(1985) A trace inequality for $M$-matrices and the symmetrizability of a real matrix by a positive diagonal matrix. Linear Alg. Appl. 71, pp. 81–94. Cited by: 9.4.2, 9.4.2.
• [147] M. Fiedler(1972) Bounds for eigenvalues of doubly stochastic matrices. Linear Algebra Appl. 5, pp. 299–310. Cited by: 4.7.
• [148] J. A. Fill and R. Pemantle(1993) Percolation, first-passage percolation and covering times for Richardson’s model on the $n$-cube. Ann. Appl. Probab. 3, pp. 593–629. Cited by: 14.8.
• [149] J.A. Fill(1991) Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process. Ann. Appl. Probab. 1, pp. 62–87. Cited by: 8.1.
• [150] J.A. Fill(1991) Time to stationarity for a continuous-time Markov chain. Prob. Engineering Inform. Sci. 5, pp. 45–70. Cited by: 4.7, 9.7.
• [151] J.A. Fill(1992) Strong stationary duality for continuous-time Markov chains. part I: theory. J. Theoretical Probab. 5, pp. 45–70. Cited by: 4.7, 9.7.
• [152] L. Flatto, A.M. Odlyzko and D.B. Wales(1985) Random shuffles and group representations. Ann. Probab. 13, pp. 154–178. Cited by: 6.9, 7.2.1.
• [153] R.M. Foster(1949) The average impedance of an electrical network. Ann Arbor, MI, pp. 333–340. Cited by: 3.3.4.
• [154] D. Freedman(1983) Markov chains. Springer–Verlag. Note: Reprint of 1971 Holden-Day edition Cited by: 2.9.
• [155] J. Friedman, J. Kahn and E. Szemeredi(1989) On the second eigenvalue in random regular graphs. pp. 587–598. Cited by: 13.4.
• [156] J. Friedman(1991) On the second eigenvalue and random walk in random regular graphs. Combinatorica 11, pp. 331–362. Cited by: 13.4.
• [157] J. Friedman (Ed.)(1993) Expanding graphs. Amer. Math. Soc.. Note: DIMACS volume 10 Cited by: 10.1.1, 10.6.
• [158] A. Frieze, R. Kannan and N. Polson(1994) Sampling from log-concave distributions. Ann. Appl. Probab. 4, pp. 812–837. Cited by: 10.6, 4.7.
• [159] M. Fukushima(1980) Dirichlet forms and Markov processes. North-Holland. Cited by: 3.8.
• [160] A. Gelman, G.O. Roberts and W.R. Gilks(1996) Efficient Metropolis jumping rules. Vol. 5, pp. 599–608. Cited by: 11.7.
• [161] A. Gelman and D.B. Rubin(1992) Inference from iterative simulation using multiple sequences. Statistical Science 7, pp. 457–472. Note: With discussion Cited by: 11.7.
• [162] S. Geman and D. Geman(1984) Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images. IEEE Trans. Pattern Anal. Mach. Intell. 6, pp. 721–741. Cited by: 11.7.
• [163] C.J. Geyer(1991) Markov chain Monte Carlo maximum likelihood. pp. 156–163. Cited by: 11.3.3.
• [164] A. Giacometti(1995) Exact closed form of the return probability on the Bethe lattice. J. Phys. A: Math. Gen. 28, pp. L13–L17. Cited by: 13.2.7.
• [165] W.R. Gilks, S. Richardson and D.J. Spiegelhalter (Eds.)(1996) Markov chain Monte Carlo in practice. Chapman and Hall, London. Cited by: 11.7.
• [166] W.R. Gilks, G.O. Roberts and E.I. George(1994) Adaptive direction sampling. The Statistician 43, pp. 179–189. Cited by: 11.3.4.
• [167] D. Gillman(1998) A Chernoff bound for random walks on expander graphs. SIAM J. Comput. 27, pp. 1203–1220. Cited by: 10.7.1.
• [168] F. Gobel and A.A. Jagers(1974) Random walks on graphs. Stochastic Process. Appl. 2, pp. 311–336. Cited by: 3.8, 7.4.
• [169] S. Golstein(1979) Maximal coupling. Z. Wahrsch. Verw. Gebiete 46, pp. 193–204. Cited by: 9.7.
• [170] J. Goodman and A. Sokal(1989) Multigrid Monte Carlo method: conceptual foundations. Phys. Rev. D 40, pp. 2037–2071. Cited by: 11.7.
• [171] D. Griffeath and T. M. Liggett(1982) Critical phenomena for Spitzer’s reversible nearest particle systems. Ann. Probab. 10, pp. 881–895. Cited by: 3.8.
• [172] D. Griffeath(1974-75) A maximal coupling for Markov chains. Z. Wahrsch. Verw. Gebiete, pp. 95–106. Cited by: 12.2.
• [173] D. Griffeath(1979) Additive and cancellative interacting particle systems. Lecture Notes in Math., Vol. 724, Springer–Verlag. Cited by: 14.4, 14.
• [174] P. Griffin(1990) Accelerating beyond the third dimension: returning to the origin in a simple random walk. Mathematical Scientist 15, pp. 24–35. Cited by: 13.2.4.
• [175] G. Grimmett and H. Kesten(1984) Random electrical networks on complete graphs. J. London Math. Soc. (2) 30, pp. 171–192. Cited by: 13.3.5, 13.4.
• [176] G. Grimmett and D. Stirzaker(1982) Probability and random processes. Oxford University Press. Cited by: 2.9.
• [177] G. Grimmett(1993) Random graphical networks. Networks and Chaos — Statistical and Probabilistic Aspects, pp. 288–301. Note: Monogr. Statist. Appl. Prob. 50 Cited by: 13.4.
• [178] H. Haken(1978) Synergetics. Springer-Verlag. Cited by: 9.7.
• [179] T. Hara and G. Slade(1992) The number and size of branched polymers in high dimensions. J. Statist. Phys. 67, pp. 1009–1038. Cited by: 6.2.
• [180] W.K. Hastings(1970) Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57, pp. 97–109. Cited by: 11.7.
• [181] R. Holley and D. Stroock(1987) Logarithmic Sobolev inequalitites and stochastic Ising models. J. Statist. Phys. 46, pp. 1159–1194. Cited by: 8.4.5.
• [182] D.F. Holt(1981) A graph which is edge-transitive but not arc-transitive. J. Graph Theory 5, pp. 201–204. Cited by: 7.4.
• [183] R.A. Horn and C.R. Johnson(1985) Matrix analysis. Cambridge University Press. Cited by: 3.4, 3.6.3, 3.6.5, 8.1.
• [184] B.D. Hughes(1995) Random walks and random environments. Oxford University Press. Cited by: 13.2.4, 13.3.6.
• [185] K. Hukushima and K. Nemoto(1996) Exchange Monte Carlo method and application to spin glass simulations. J. Physics Soc. Japan 65, pp. 1604–1608. Cited by: 11.3.3.
• [186] J.J. Hunter(1983) Mathematical techniques of applied probability. Academic Press. Cited by: 1.2.3, 2.10.2, 2.9, 2.9.
• [187] J.-P. Imhof(1985) On Brownian bridge and excursion. Studia Sci. Math. Hungar. 20, pp. 1–10. Cited by: 6.9.
• [188] R. Impagliazzo and D. Zuckerman(1989) How to recycle random bits. pp. 248–253. Cited by: 10.4.1, 10.6.
• [189] M. Iosifescu(1980) Finite markov processes and their applications. Wiley. Cited by: 2.9.
• [190] R. Isaacs(1965) Differential games. Wiley. Cited by: 4.7.
• [191] D. Isaacson and R. Madsen(1976) Markov chains: theory and applications. Wiley. Cited by: 2.9.
• [192] I. Iscoe, D. McDonald and K. Qian(1993) Capacity of ATM switches. Ann. Appl. Probab. 3, pp. 277–295. Cited by: 3.8.
• [193] I. Iscoe and D. McDonald(1994) Asymptotics of exit times for Markov jump processes I. Ann. Probab. 22, pp. 372–397. Cited by: 3.8.
• [194] S. Janson(1997) Gaussian hilbert spaces. Cambridge Tracts in Mathematics, Cambridge University Press. Cited by: 2.9, 3.8.
• [195] E. Janvresse(2001) Spectral gap for Kac’s model of the Boltzmann equation. Ann. Probab. 29, pp. 288–304. Cited by: 13.4.
• [196] M. Jerrum and A. Sinclair(1989) Approximating the permanent. SIAM J. Computing 18, pp. 1149–1178. Cited by: 10.6.
• [197] M. Jerrum and A. Sinclair(1996) The Markov chain Monte Carlo method: an approach to approximate counting and integration. Boston MA, pp. 482–520. Cited by: 10.5.2, 10.6.
• [198] M. Jerrum(1993) Uniform sampling modulo a group of symmetries using Markov chain simulation. pp. 37–48. Note: DIMACS, volume 10 Cited by: 12.2, 14.7.
• [199] M. Jerrum(1998) Mathematical foundations of the Markov chain Monte Carlo method. Algorithms and Combinatorics, pp. 116–165. Cited by: 10.5.2, 10.6.
• [200] M.R. Jerrum, L.G. Valiant and V.V. Vazirani(1986) Random generation of combinatorial structures from a uniform distribution. Theor. Computer Sci. 43, pp. 169–188. Cited by: 10.6.
• [201] M.R. Jerrum(1995) A very simple algorithm for estimating the number of $k$-colorings of a low-degree graph. Random Struct. Alg. 7, pp. 157–165. Cited by: 12.2.
• [202] C.D. M. Jr.(1975) The role of the group generalized inverse in the theory of finite Markov chains. SIAM Review 17, pp. 443–464. Cited by: 2.9.
• [203] N. Kahale(1995) Eigenvalues and expansion of regular graphs. J. ACM 42, pp. 1091–1106. Cited by: 3.8.
• [204] N. Kahale(1997) Large deviation bounds for Markov chains. Combin. Probab. Comput. 6, pp. 465–474. Cited by: 10.7.1.
• [205] J.D. Kahn, N. Linial, N. Nisan and M.E. Saks(1989) On the cover time of random walks on graphs. J. Theoretical Probab. 2, pp. 121–128. Cited by: 6.1.
• [206] R. Kannan, L. Lovász and M. Simonovits(1997) Random walks and an $O^{*}$$(n^{5})$ volume algorithm for convex bodies. Random Struct. Alg. 11, pp. 1–50. Cited by: 10.5.1.
• [207] S. Karlin, B. Lindquist and Y. Yao(1993) Markov chains on hypercubes: spectral representations and several majorization relations. Random Struct. Alg. 4, pp. 1–36. Cited by: 7.4.
• [208] S. Karlin and H.M. Taylor(1975) A first course in stochastic processes. Second edition, Academic Press. Cited by: 13.1.1, 2.8.1, 2.9, 5.1.2.
• [209] S. Karlin and H.M. Taylor(1981) A second course in stochastic processes. Academic Press. Cited by: 13.4, 2.9, 5.1.3.
• [210] R.M. Karp, M. Luby and N. Madras(1989) Monte Carlo approximation algorithms for enumeration problems. J. Algorithms 10, pp. 429–448. Cited by: 10.6.
• [211] A. Karzanov and L. Khachiyan(1991) On the conductance of order Markov chains. Order 8, pp. 7–15. Cited by: 12.2.
• [212] J. Keilson(1979) Markov chain models - rarity and exponentiality. Springer–Verlag. Cited by: 1.2.3, 3.8, 3.8, 7.4.
• [213] F.P. Kelly(1979) Reversibility and stochastic networks. Wiley. Cited by: 1.2.3, 2.9, 3.8, 3.8, 3.8.
• [214] J.G. Kemeny, J. Snell and A.W. Knapp(1976) Denumerable markov chains. 2nd edition, Springer–Verlag. Cited by: 2.9, 3.8.
• [215] J.G. Kemeny and J.L. Snell(1960) Finite markov chains. Van Nostrand. Cited by: 1.2.3, 2.10.2, 2.9, 2.9, 2.9, 2.9.
• [216] J.H.B. Kemperman(1961) The passage problem for a stationary markov chain. University of Chicago Press. Cited by: 5.4, 5.4.
• [217] C. Kipnis and S.R.S. Varadhan(1986) Central limit theorem for additive functionals of reversible Markov processes and applications to simple exclusions. Comm. Math. Phys. 104, pp. 1–19. Cited by: 13.4.
• [218] W.B. Krebs(1995) Brownian motion on the continuum tree. Probab. Th. Rel. Fields 101, pp. 421–433. Cited by: 13.4.
• [219] J.C. Lagarias and A. Weiss(1992) The $3x+1$ problem: two stochastic models. Ann. Appl. Probab. 2, pp. 229–261. Cited by: 6.2.
• [220] H.J. Landau and A.M. Odlyzko(1981) Bounds for eigenvalues of certain stochastic matrices. Linear Algebra Appl. 38, pp. 5–15. Cited by: 5.4.
• [221] L. Lange and J.W. Miller(1992) A random ladder game: permutations, eigenvalues, and convergence of markov chains. College Math. Journal 23, pp. 373–385. Cited by: 14.8.
• [222] G. Lawler(1993) On the covering time of a disc by simple random walk in two dimensions. Seminar in Stochastic Processes 1992, pp. 189–208. Cited by: 7.2.2, 7.4.
• [223] G.F. Lawler and A.D. Sokal(1988) Bounds on the ${L}^{2}$ spectrum for Markov chains and Markov proceses. Trans. Amer. Math. Soc. 309, pp. 557–580. Cited by: 4.7.
• [224] T. Leighton and S. Rao(1988) An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. pp. 422–431. Cited by: 4.7.
• [225] G. Letac and L. Takács(1980) Random walks on a 600-cell. SIAM J. Alg. Discrete Math. 1, pp. 114–120. Cited by: 7.3.2.
• [226] G. Letac and L. Takács(1980) Random walks on a dodecahedron. J. Appl. Probab. 17, pp. 373–384. Cited by: 7.3.2.
• [227] G. Letac(1981) Problemes classiques de probabilite sur un couple de Gelfand. Analytic Methods in Probability Theory, Note: Lecture Notes in Math. 861 Cited by: 7.3.5.
• [228] G. Letac(1982) Les fonctions spheriques d’un couple de Gelfand symmetrique et les chaines de Markov. Adv. in Appl. Probab. 14, pp. 272–294. Cited by: 7.3.5.
• [229] G. Letac(1986) A contraction principle for certain Markov chains and its applications. Random Matrices and Their Applications, Contemp. Math., Vol. 50, pp. 263–273. Cited by: 9.7.
• [230] P. Lezaud(1998) Chernoff-type bound for finite Markov chains. Ann. Appl. Probab. 8, pp. 849–867. Cited by: 10.7.1.
• [231] T.M. Liggett(1976) Coupling the simple exclusion process. Ann. Probab. 4, pp. 339–356. Cited by: 12.2.
• [232] T.M. Liggett(1985) Interacting particle systems. Springer–Verlag. Cited by: 1.2.3, 14.4, 14.8, 14.
• [233] T. Lindstrøm(1989) Brownian motion on nested fractals. Memoirs of the A.M.S. 420. Cited by: 13.4.
• [234] T. Lindvaal(1992) Lectures on the coupling method. Wiley, New York. Cited by: 12.2, 13.4, 14.7.1, 14.8, 14.8, 14.8, 9.1, 9.7.
• [235] J.S. Liu, F. Liang and W.H. Wong(xxx) The use of multiple-try method and local optimization in Metropolis sampling. JASA xxx, pp. xxx. Cited by: 11.3.2, 11.3.4, 11.7.
• [236] J.S. Liu(1996) Metropolized independent sampling with comparisons to rejection sampling and importance sampling. Statistics and Computing 6, pp. 113–119. Cited by: 11.4.2.
• [237] J.S. Liu(2001) Monte carlo techniques in scientific computing. Springer–Verlag. Cited by: 11.2.2, 11.7, 11.7, 11.
• [238] L. Lovász and M. Simonovits(1990) The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume. pp. 346–355. Cited by: 10.6, 4.7.
• [239] L. Lovász and M. Simonovits(1993) Random walks in a convex body and an improved volume algorithm. Random Struct. Alg. 4, pp. 359–412. Cited by: 10.6.
• [240] L. Lovász and P. Winkler(1995) Efficient stopping rules for Markov chains. pp. 76–82. Cited by: 2.10.1, 2.9, 4.7, 9.3.1, 9.6.1, 9.7.
• [241] L. Lovász and P. Winkler(1995) Exact mixing in an unknown Markov chain. Electronic J. Combinatorics 2, pp. #R15. Cited by: 9.3.1, 9.7.
• [242] L. Lovász(1993) Combinatorial problems and exercises. North-Holland. Note: Second Edition Cited by: 1.2.3.
• [243] A. Lubotzky(1994) Discrete groups, expanding graphs and invariant measures. Birkhauser. Note: Progress in Mathematics, vol. 125 Cited by: 10.1.1, 10.1.1, 13.3.1, 13.4.
• [244] M. Luby and E. Vigoda(1999) Fast convergence of the Glauber dynamics for sampling independent sets. Technical report ICSI, Berkeley CA. Cited by: 12.1.12, 12.2.
• [245] R. Lyons, R. Pemantle and Y. Peres(1995) Ergodic theory on Galton–Watson trees: speed of random walk and dimension of harmonic measure. Ergodic Theory Dynam. Systems 15, pp. 593–619. Cited by: 13.3.3, 13.3.3.
• [246] R. Lyons, R. Pemantle and Y. Peres(1996) Biased random walks on Galton–Watson trees. Probab. Th. Rel. Fields 106, pp. 249–264. Cited by: 13.3.3, 13.3.3, 13.3.3.
• [247] R. Lyons, R. Pemantle and Y. Peres(1996) Unsolved problems concerning random walks on trees. in K. Athreya and P. Jagers (Eds.), Classical and Modern Branching Processes, pp. 223–238. Cited by: 13.3.3, 13.4.
• [248] R. Lyons and R. Pemantle(1992) Random walk in a random environment and first-passage percolation on trees. Ann. Probab. 20, pp. 125–136. Cited by: 13.3.3.
• [249] R. Lyons and Y. Peres(2002) Probability on trees and networks. Cambridge University Press. Note: In preparation Cited by: 13.3.3, 13.4, 3.8, 9.7.
• [250] R. Lyons(1992) Random walks, capacity, and percolation on trees. Ann. Probab. 20, pp. 2043–2088. Cited by: 5.4.
• [251] T.J. Lyons(1983) A simple criterion for transience of a reversible Markov chain. Ann. Probab. 11, pp. 393–402. Cited by: 3.8.
• [252] N. Madras and G. Slade(1993) The self-avoiding walk. Birkhauser. Cited by: 11.1.2.
• [253] M. B. Marcus and J. Rosen(1992) Sample path properties of the local times of strongly symmetric Markov processes via Gaussian processes. Ann. Probab. 20, pp. 1603–1684. Cited by: 14.6.2.
• [254] E. Marinari and G. Parisi(1992) Simulated tempering: a new Monte Carlo scheme. Europhysics Letters 19, pp. 451–458. Cited by: 11.3.3.
• [255] P.C. Matthews(1985) Covering problems for random walks on spheres and finite groups. Ph.D. Thesis, Statistics, Stanford. Cited by: 7.4.
• [256] P.C. Matthews(1988) A strong uniform time for random transpositions. J. Theoretical Probab. 1, pp. 411–423. Cited by: 4.7.
• [257] P.C. Matthews(1988) Covering problems for Brownian motion on spheres. Ann. Probab. 16, pp. 189–199. Cited by: 2.9, 2.26.
• [258] P.C. Matthews(1988) Covering problems for Markov chains. Ann. Probab. 16, pp. 1215–1228. Cited by: 2.9, 7.1.5, 7.4.
• [259] P.C. Matthews(1990) Mixing rates for Brownian motion in a convex polyhedron. J. Appl. Probab. 27, pp. 259–268. Cited by: 13.4.
• [260] P.C. Matthews(1992) Strong stationary times and eigenvalues. J. Appl. Probab. 29, pp. 228–233. Cited by: 4.7.
• [261] J.E. Mazo(1982) Some extremal Markov chains. Bell System Tech. J. 61, pp. 2065–2080. Cited by: 5.4.
• [262] N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller and E. Teller(1953) Equations of state calculations by fast computing machine. J. Chem. Phys. 21, pp. 1087–1091. Cited by: 11.7.
• [263] S.P. Meyn and R.L. Tweedie(1993) Markov chains and stochastic stability. Springer–Verlag. Cited by: 13.4, 13.4, 2.9, 4.7.
• [264] J.W. Moon(1973) Random walks on random trees. J. Austral. Math. Soc. 15, pp. 42–53. Cited by: 13.3.4, 13.3.4, 13.4, 5.4.
• [265] R. Motwani and P. Raghavan(1995) Randomized algorithms. Cambridge University Press. Cited by: 1.2.2, 10.3.1, 10.6, 10.6, 10.6, 10.6.
• [266] C. St. J. A. Nash-Williams(1959) Random walks and electric currents in networks. Proc. Cambridge Philos. Soc. 55, pp. 181–194. Cited by: 3.8.
• [267] R.M. Neal(1996) Bayesian learning for neural networks. Lecture Notes in Statistics, Springer–Verlag. Cited by: 11.7.
• [268] R.M. Neal(1996) Sampling from multimodal distributions using tempered transitions. Statistics and Computing 6, pp. 353–366. Cited by: 11.7.
• [269] C. Neuhauser and A. Sudbury(1993) The biased annihilating branching process. Adv. in Appl. Probab. 25, pp. 24–38. Cited by: 14.6.1.
• [270] J.R. Norris(1997) Markov chains. Cambridge University Press. Cited by: 1.2.3, 12.2, 13.1.1, 2.1.1, 2.1.2, 2.1, 2.1, 2.9, 2.1, 2.2.
• [271] I. Pak(1999) Random walk on finite groups with few random generators. Electon. J. Probab. 4 (1), pp. 1–11. Cited by: 13.4.
• [272] J. L. Palacios(1990) Bounds on expected hitting times for a random walk on a connected graph. Linear Algebra Appl. 141, pp. 241–252. Cited by: 5.4.
• [273] J. L. Palacios(1992) A bound for the covering time of random walks on graphs. Statistics and Probab. Lett. 14, pp. 9–11. Cited by: 6.9.
• [274] J. L. Palacios(1992) Expected cover times of random walks on symmetric graphs. J. Theoretical Probab. 5, pp. 597–600. Cited by: 7.4.
• [275] J. L. Palacios(1993) Fluctuation theory for the Ehrenfest urn model via electrical networks. Adv. in Appl. Probab. 25, pp. 472–476. Cited by: 5.4, 7.3.2.
• [276] J.L. Palacios(1990) On a result of Aleliunas et al. concerning random walks on graphs. Prob. Engineering Inform. Sci. 4, pp. 489–492. Cited by: 6.9.
• [277] L. Pearce(1980) Random walks on trees. Discrete Math. 30, pp. 269–276. Cited by: 5.3.2.
• [278] R. Pemantle(1991) Choosing a spanning tree for the integer lattice uniformly. Ann. Probab. 19, pp. 1559–1574. Cited by: 9.7.
• [279] R. Pemantle(1995) Uniform random spanning trees. Boca Raton, FL, pp. 1–54. Cited by: 9.2.2, 9.7, 9.7.
• [280] P. Peskun(1973) Optimal Monte Carlo sampling using Markov chains. Biometrika 60, pp. 607–612. Cited by: 11.1, 11.5, 3.4.
• [281] N. Pippenger(1977) Superconcentrators. SIAM J. Comput. 6, pp. 298–304. Cited by: 13.4.
• [282] J.W. Pitman(1976) On coupling of Markov chains. Z. Wahrsch. Verw. Gebiete 35, pp. 313–322. Cited by: 12.2.
• [283] J.W. Pitman(1977) Occupation measures for Markov chains. Adv. in Appl. Probab. 9, pp. 69–86. Cited by: 2.9.
• [284] U. Porod(1995) $L_{2}$ lower bounds for a special class of random walks. Probab. Th. Rel. Fields 101, pp. 277–289. Cited by: 13.4.
• [285] U. Porod(1996) The cut-off phenomenon for random reflections. Ann. Probab. 24, pp. 74–96. Cited by: 13.1.5, 13.4.
• [286] J. Propp and D. Wilson(1996) Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Struct. Alg. 9, pp. 223–252. Cited by: 9.3.3.
• [287] Y. Rabani, Y. Rabinovich and A. Sinclair(1995) A computational view of population genetics. pp. 83–92. Cited by: 12.2.
• [288] P. Revesz(1990) Random walk in random and non-random scenery. World Scientific, Singapore. Cited by: 7.4.
• [289] D. Revuz(1984) Markov chains. Second edition, North-Holland. Cited by: 2.9, 9.7.
• [290] C.P. Robert and G. Casella(2000) Monte carlo statistical methods. Springer–Verlag. Cited by: 11.7.
• [291] C.P. Robert (Ed.)(1998) Discretization and MCMC convergence assesment. Lecture Notes in Statistics, Springer–Verlag. Cited by: 11.7.
• [292] G.O. Roberts, A. Gelman and W.R. Gilks(1997) Weak convergence and optimal scaling of random walk Metropolis algorithms. Ann. Appl. Probab. 7, pp. 110–120. Cited by: 11.5.1, 11.5.2.
• [293] G.O. Roberts and R.L. Tweedie(1996) Geometric convergence and central limit theorems for multidimensional Hastings and Metropolis algorithms. Biometrika 83, pp. 95–110. Cited by: 11.7.
• [294] G.O. Roberts(1998) Optimal Metropolis algorithms for product measures on the vertices of a hypercube. Stochastics Stochastic Rep. 62, pp. 275–283. Cited by: 11.5.2.
• [295] L.C.G. Rogers and D. Williams(1994) Diffusions, Markov processes and martingales: foundations. Second edition, Vol. 1, Wiley. Cited by: 13.4.
• [296] Y. Roichman(1996) On random random walks. Ann. Probab. 24, pp. 1001–1011. Cited by: 13.3.1.
• [297] V. I. Romanovsky(1970) Discrete markov chains. Wolthers-Noordhoff. Note: English translation of Russian original Cited by: 2.9.
• [298] J. S. Rosenthal(1994) Random rotations: characters and random walks on $SO(N)$. Ann. Probab. 22, pp. 398–423. Cited by: 13.4.
• [299] S. M. Ross(1981) A random graph. J. Appl. Probab. 18, pp. 309–315. Cited by: 9.3.1.
• [300] S. Ross(1983) Stochastic processes. Wiley. Cited by: 2.2.1.
• [301] H. Rost(1971) The stopping distributions of a Markov process. Inventiones Math. 14, pp. 1–16. Cited by: 2.10.1, 9.7.
• [302] O. S. Rothaus(1981) Diffusion on compact Riemannian manifolds and logarithmic Sobolev inequalities. J. Funct. Anal. 42, pp. 102–109. Cited by: 8.4.1.
• [303] W. Rudin(1987) Real and complex analysis. 3rd edition, McGraw–Hill Book Co., New York. Cited by: 8.2.2.
• [304] L. Saloff-Coste(1997) Lectures on finite Markov chains. Lectures on probability theory and statistics (Saint-Flour, 1996), pp. 301–413. Cited by: 8.6.
• [305] P. Sarnak(1990) Some applications of modular forms. Cambridge University Press. Note: Cambridge Tracts in Math. 99 Cited by: 13.4.
• [306] A.M. Sbihi(1990) Covering times for random walks on graphs. Ph.D. Thesis, McGill University. Cited by: 6.9, 6.9, 6.9, 7.4, 7.4.
• [307] A. J. Sinclair(1992) Improved bounds for mixing rates of Markov chains and multicommodity flow. Combin. Probab. Comput. 1, pp. 351–370. Cited by: 4.3.5, 4.4.3, 4.7.
• [308] A. J. Sinclair(1993) Algorithms for random generation and counting. Birkhauser. Cited by: 10.6, 10.6, 10.6.
• [309] A. Sinclair and M. Jerrum(1989) Approximate counting, uniform generation and rapidly mixing Markov chains. Information and Computation 82, pp. 93–133. Cited by: 4.7.
• [310] R.L. Smith(1984) Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions. Operations Research 32, pp. 1296–1308. Cited by: 11.7.
• [311] A.D. Sokal(1989) Monte Carlo methods in statistical mechanics: foundations and new algorithms. Cited by: 11.1.2, 11.7.
• [312] R. Solovay and V. Strassen(1977) A fast Monte-Carlo test for primality. SIAM J. Comput. 6, pp. 84–85. Cited by: 10.8.
• [313] R. Stanley(1999) Enumerative combinatorics, vol. 2. Cambridge University Press. Cited by: 13.3.4.
• [314] W.J. Stewart(1995) Introduction to the numerical solution of Markov chains. Princeton University Press. Cited by: 2.9.
• [315] D. Stoyan(1983) Comparison methods for queues and other stochastic models. Wiley. Cited by: 14.8.
• [316] W.G. Sullivan(1984) $L^{2}$ spectral gap and jump processes. Z. Wahrsch. Verw. Gebiete 67, pp. 387–398. Cited by: 9.7.
• [317] D.E. Symer(1984) Expanded ergodic Markov chains and cycling systems. Note: Senior thesis, Dartmouth College Cited by: 9.7.
• [318] R. Syski(1992) Passage times for Markov chains. IOS Press, Amsterdam. Cited by: 2.9.
• [319] L. Takács(1981) Random flights on regular polytopes. SIAM J. Alg. Discrete Meth. 2, pp. 153–171. Cited by: 7.3.2, 7.4.
• [320] L. Takács(1984) Random flights on regular graphs. Adv. in Appl. Probab. 16, pp. 618–637. Cited by: 7.3.2, 7.4.
• [321] M. Tanushev and R. Arratia(1997) A note on distributional equality in the cyclic tour property for Markov chains. Combin. Probab. Comput. 6, pp. 493–496. Cited by: 3.8.
• [322] A. Telcs(1990) Spectra of graphs and fractal dimensions I. Probab. Th. Rel. Fields 85, pp. 489–497. Cited by: 13.4.
• [323] A. Telcs(1995) Spectra of graphs and fractal dimensions II. J. Theoretical Probab. 8, pp. 77–96. Cited by: 13.4.
• [324] P. Tetali and P. Winkler(1993) Simultaneous reversible Markov chains. Vol. 1, pp. 433–451. Cited by: 3.8.
• [325] P. Tetali(1991) Random walks and the effective resistance of networks. J. Theoretical Probab. 4, pp. 101–109. Cited by: 3.8.
• [326] P. Tetali(1994) An extension of Foster’s network theorem. Combin. Probab. Comput. 3, pp. 421–427. Cited by: 3.8.
• [327] P. Tetali(1994) Design of on-line algorithms using hitting times. Note: Bell Labs Cited by: 10.6, 9.4.2.
• [328] H. Thorisson(2000) Coupling, stationarity and regeneration. Springer–Verlag. Cited by: 13.4.
• [329] E. van Doorn(1981) Stochastic monotonicity and queueing applications of birth-death processes. Lecture Notes in Stat., Vol. 4, Springer–Verlag. Cited by: 14.8.
• [330] A.R.D. van Slijpe(1984) Random walks on regular polyhedra and other distance-regular graphs. Statist. Neerlandica 38, pp. 273–292. Cited by: 7.1.3, 7.3.2, 7.4.
• [331] A.R.D. van Slijpe(1986) Random walks on the triangular prism and other vertex-transitive graphs. J. Comput. Appl. Math. 15, pp. 383–394. Cited by: 7.3.2, 7.4.
• [332] N. Th. Varopoulos, L. Saloff-Coste and T. Coulhon(1992) Analysis and geometry on groups. Cambridge University Press. Cited by: 1.2.3.
• [333] E. Vigoda(1999) Improved bounds for sampling colorings. Note: C.S. Dept., U.C. Berkeley Cited by: 12.1.12, 12.2.
• [334] I.C. Walters(1996) The ever expanding expander coefficients. Bull. Inst. Combin. Appl. 17, pp. 79–86. Cited by: 10.6.
• [335] K. Weber(1990) Random spread of information, random graph processes and random walks. pp. 361–366. Cited by: 14.8.
• [336] H.S. Wilf(1989) The editor’s corner: the white screen problem. Amer. Math. Monthly 96, pp. 704–707. Cited by: 1.1.2.
• [337] H.S. Wilf(1990) Computer-generated proofs of $54$ binomial coefficient idenitites. Note: U. Penn. Cited by: 5.4.
• [338] D.B. Wilson(2004) Mixing times of lozenge tiling and card shuffling Markov chains. Ann. Appl. Probab. 14, pp. 274–325. Cited by: 12.1.9.
• [339] W. Woess(2000) Random walks on infinite graphs and groups. Cambridge Tracts Math., Cambridge Univ. Press. Cited by: 13.2.10, 13.2.3, 13.2.7, 13.2, 13.4, 13.4.
• [340] O. Yaron(1988) Random walks on trees. Technical report Hebrew University, Jerusalem. Cited by: 5.3.2.
• [341] D. Zuckerman(1989) Covering times of random walks on bounded degree trees and other graphs. J. Theoretical Probab. 2, pp. 147–157. Cited by: 3.8, 6.9.
• [342] D. Zuckerman(1991) On the time to traverse all edges in a graph. Information Proc. Letters. 38, pp. 335–337. Cited by: 6.1.
• [343] D. Zuckerman(1992) A technique for lower bounding the cover time. SIAM J. Discrete Math. 5, pp. 81–87. Cited by: 6.9, 6.9, 7.4, 7.4.