کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5777184 1632572 2017 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Taming reluctant random walks in the positive quadrant
ترجمه فارسی عنوان
تسخیر بی رحمانه پیاده روی تصادفی در ربع مثبت است
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
A two-dimensional lattice walk model is said to be reluctant if its defining step set has a strong drift away from the negative half-planes. We consider the uniform random generation of reluctant walks of length n in the positive quadrant, noting that a naive rejection from unconstrained walks has exponential time complexity. A baseline algorithm using the recursive method requires Θ(n4) time and memory. We consider an alternative strategy which draws unidimensional walks from a well-chosen half-plane model, as identified by Johnson, Mishna and Yeats. The resulting generator is provably efficient, and typically outperforms the baseline algorithm. A general analysis of its complexity requires further developments to characterize the subexponential growth factors of reluctant walks, and motivates the design of efficient algorithms for the generation of 1D walks taking irrational step sets.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 59, June 2017, Pages 99-114
نویسندگان
, , ,