کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875882 | 1441990 | 2017 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Total variation discrepancy of deterministic random walks for ergodic Markov chains
ترجمه فارسی عنوان
اختلاف کامل متغیرهای تصادفی قطعی برای زنجیره مارکوف ارگودو
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Motivated by a derandomization of Markov chain Monte Carlo (MCMC), this paper investigates a deterministic random walk, which is a deterministic process analogous to a random walk. There is some recent progress in the analysis of the vertex-wise discrepancy (i.e., Lâ-discrepancy), while little is known about the total variation discrepancy (i.e., L1-discrepancy), which plays an important role in the analysis of an FPRAS based on MCMC. This paper investigates the L1-discrepancy between the expected number of tokens in a Markov chain and the number of tokens in its corresponding deterministic random walk. First, we give a simple but nontrivial upper bound O(mtâ) of the L1-discrepancy for any ergodic Markov chains, where m is the number of edges of the transition diagram and tâ is the mixing time of the Markov chain. Then, we give a better upper bound O(mtâ) for non-oblivious deterministic random walks, if the corresponding Markov chain is ergodic and lazy. We also present some lower bounds.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 699, 7 November 2017, Pages 63-74
Journal: Theoretical Computer Science - Volume 699, 7 November 2017, Pages 63-74
نویسندگان
Takeharu Shiraga, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita,