TABLE OF CONTENTS Up to this point all our CFTP methods and applications have applied only to Markov chains which are in some sense bounded (strictly speaking, uniformly ergodic in the sense of Definition 28). We now discuss how to lift this restriction.
We begin by considering some precursor notions from queueing theory ( 3.1), and then define the important theoretical notions of uniform and geometric ergodicity ( 3.2) and discuss their relationship with classic CFTP ( 3.3). This leads straight to the idea of dominated CFTP (dom CFTP), introduced in 3.4, which can apply to geometrically ergodic (and hence unbounded ) Markov chains. We describe this idea carefully in the simple but prototypical context of birth-death processes ( 3.5) and present an application to point processes ( 3.6). We conclude by describing a general theorem on the validity of dom CFTP ( 3.7).
Consider a GI/G/1 queue (intervals between customer arrivals are independent and identically distributed, as are the service times required by customers though of course service time and inter-arrival time have different distributions). Lindley noticed a beautiful representation for waiting time W n of customer n in terms of services S n and inter-arrivals X n , based on the observation that S n ?X n +1 (if positive) is the extra amount of time for which customer n+1 must wait as compared to customer n.
Theorem 21: Lindley s equation: Consider the waiting time identity for the GI/G/
