Subexponential asymptotics of a Markov-modulated random walk with queueing applications

Abstract

Let {(X_n,J_n)} be a stationary Markov-modulated random walk on ℝ x E (E is finite), defined by its probability transition matrix measure F = {F_ij}, F_ij(B) = ℙ[X₁ ∈ B, J₁ = j | J₀ = i], B ∈ B(ℝ), i, j ∈ E. If F_ij([x,∞))/(1-H(x)) → W_ij ∈ [0,∞), as x → ∞, for some long-tailed distribution function H, then the ascending ladder heights matrix distribution G₊(x) (right Wiener-Hopf factor) has long-tailed asymptotics. If 𝔼X_n < 0, at least one W_ij > 0, and H(x) is a subexponential distribution function, then the asymptotic behavior of the supremum of this random walk is the same as in the i.i.d. case, and it is given by ℙ[sup_n≥0S_n > x] → (−𝔼X_n)⁻¹ ∫_x^∞ ℙ[X_n > u]du as x → ∞, where S_n = ∑₁ⁿX_k, S₀ = 0. Two general queueing applications of this result are given.First, if the same asymptotic conditions are imposed on a Markov-modulated G/G/1 queue, then the waiting time distribution has the same asymptotics as the waiting time distribution of a GI/GI/1 queue, i.e., it is given by the integrated tail of the service time distribution function divided by the negative drift of the queue increment process. Second, the autocorrelation function of a class of processes constructed by embedding a Markov chain into a subexponential renewal process, has a subexponential tail. When a fluid flow queue is fed by these processes, the queue-length distribution is asymptotically proportional to its autocorrelation function.