Non-homogeneous random walks on a semi-infinite strip

We study the asymptotic behaviour of Markov chains ( X n , η n ) on Z + × S , where Z + is the non-negative integers and S is a finite set. Neither coordinate is assumed to be Markov. We assume a moments bound on the jumps of X n , and that, roughly speaking, η n is close to being Markov when X n is large. This departure from much of the literature, which assumes that η n is itself a Markov chain, enables us to probe precisely the recurrence phase transitions by assuming asymptotically zero drift for X n given η n . We give a recurrence classification in terms of increment moment parameters for X n and the stationary distribution for the large- X limit of η n . In the null case we also provide a weak convergence result, which demonstrates a form of asymptotic independence between X n (rescaled) and η n . Our results can be seen as generalizations of Lamperti’s results for non-homogeneous random walks on Z + (the case where S is a singleton). Motivation arises from modulated queues or processes with hidden variables where η n tracks an internal state of the system.