TY - JOUR

T1 - Taming reluctant random walks in the positive quadrant

AU - Lumbroso, Jeremie

AU - Mishna, Marni

AU - Ponty, Yann

N1 - Publisher Copyright:
© 2017 Elsevier B.V.
Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

PY - 2017/6

Y1 - 2017/6

N2 - 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.

AB - 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.

KW - 2D walk

KW - analytic combinatorics

KW - random generation

UR - http://www.scopus.com/inward/record.url?scp=85020300694&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85020300694&partnerID=8YFLogxK

U2 - 10.1016/j.endm.2017.05.008

DO - 10.1016/j.endm.2017.05.008

M3 - Article

AN - SCOPUS:85020300694

VL - 59

SP - 99

EP - 114

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

SN - 1571-0653

ER -