Random walks on graphs and Monte Carlo methods

被引：6
作者：
Cheng, Wen-Ju [1 ]
Cox, Jim [2 ]
Whitlock, Paula [2 ]
机构：
[1] CUNY, Grad Ctr, Comp Sci, Fifth Ave, New York, NY USA
[2] CUNY Brooklyn Coll, CIS Dept, 2900 Bedford Ave, Brooklyn, NY 11210 USA
来源：
MATHEMATICS AND COMPUTERS IN SIMULATION | 2017年 / 135卷
关键词：
Graph theory; Random walks; Markov chain Monte Carlo; DIRECTED-GRAPHS;
D O I：
10.1016/j.matcom.2015.12.006
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
This paper relates the study of random walks on graphs and directed graphs to random walks that arise in Monte Carlo methods applied to optimization problems. Previous results on simple graphs are surveyed and new results on the mixing times for Markov chains are derived. (C) 2016 International Association for Mathematics and Computers in Simulation (IMACS). Published by Elsevier B.V. All rights reserved.
引用
收藏
页码：86 / 94
页数：9
相关论文
共 14 条
  • [1] [Anonymous], 1984, CARUS MATH MONOGR
  • [2] [Anonymous], 2004, ELECT C COMPUTATIONA, DOI [DOI 10.1145/1060590.1060647, 10.1145/1060590.1060647]
  • [3] An O(log(n)4/3) space algorithm for (s, t) connectivity in undirected graphs
    Armoni, R
    Ta-Shma, A
    Wigderson, A
    Zhou, SY
    [J]. JOURNAL OF THE ACM, 2000, 47 (02) : 294 - 311
  • [4] PERCOLATION THEORY ON DIRECTED GRAPHS
    ARROWSMITH, DK
    ESSAM, JW
    [J]. JOURNAL OF MATHEMATICAL PHYSICS, 1977, 18 (02) : 235 - 238
  • [5] Chandra A. K., 1996, Computational Complexity, V6, P312, DOI 10.1007/BF01270385
  • [6] Chandra A. K., 1989, Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, P574, DOI 10.1145/73007.73062
  • [7] Cheng W.-J., 2014, P 10 INT C THEOR ASP, V8049
  • [8] Laplacians and the Cheeger inequality for directed graphs
    Chung, Fan
    [J]. ANNALS OF COMBINATORICS, 2005, 9 (01) : 1 - 19
  • [9] S-T Connectivity on Digraphs with a Known Stationary Distribution
    Chung, Kai-Min
    Reingold, Omer
    Vadhan, Salil
    [J]. ACM TRANSACTIONS ON ALGORITHMS, 2011, 7 (03)
  • [10] A TIGHT UPPER BOUND ON THE COVER TIME FOR RANDOM-WALKS ON GRAPHS
    FEIGE, U
    [J]. RANDOM STRUCTURES & ALGORITHMS, 1995, 6 (01) : 51 - 54
12