کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6875882 1441990 2017 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Total variation discrepancy of deterministic random walks for ergodic Markov chains
ترجمه فارسی عنوان
اختلاف کامل متغیرهای تصادفی قطعی برای زنجیره مارکوف ارگودو
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
, , , ,