Taming reluctant random walks in the positive quadrant

Jeremie Lumbroso, Marni Mishna, Yann Ponty

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)99-114
Number of pages16
JournalElectronic Notes in Discrete Mathematics
Volume59
DOIs
StatePublished - Jun 2017

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Keywords

  • 2D walk
  • analytic combinatorics
  • random generation

Fingerprint Dive into the research topics of 'Taming reluctant random walks in the positive quadrant'. Together they form a unique fingerprint.

  • Cite this