Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract In Braverman et al. [3], the authors justify the steady-state diffusion approximation of a multiclass queueing network under static buffer priority policy in heavy traffic. A major assumption in [3] is the moment state space collapse (moment-SSC) property of the steady-state queue length. In this paper, we prove that moment-SSC holds under a corresponding state space collapse condition on the fluid model. Our approach is inspired by Dai and Meyn [8], which was later adopted by Budhiraja and Lee [4] to justify the diffusion approximation for generalized Jackson networks. We will verify that the fluid state space collapse holds for various networks. PubDate: 2022-09-13

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract In this paper, we study a functional equation for generating functions of the form \(f(z) = g(z) \sum _{i=1}^M p_i f(\alpha _i(z)) + K(z)\) , viz. a recursion with multiple recursive terms. We derive and analyze the solution of this equation for the case that the \(\alpha _i(z)\) are commutative contraction mappings. The results are applied to a wide range of queueing, autoregressive and branching processes. PubDate: 2022-09-04

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We investigate the tail asymptotics of the response time distribution for the cancel-on-start (c.o.s.) and cancel-on-completion (c.o.c.) variants of redundancy-d scheduling and the fork–join model with heavy-tailed job sizes. We present bounds, which only differ in the pre-factor, for the tail probability of the response time in the case of the first-come first-served discipline. For the c.o.s. variant, we restrict ourselves to redundancy-d scheduling, which is a special case of the fork–join model. In particular, for regularly varying job sizes with tail index- \(\nu \) the tail index of the response time for the c.o.s. variant of redundancy-d equals - \(\min \{d_{\mathrm {cap}}(\nu -1),\nu \}\) , where \(d_{\mathrm {cap}} = \min \{d,N-k\}\) , N is the number of servers and k is the integer part of the load. This result indicates that for \(d_{\mathrm {cap}} < \frac{\nu }{\nu -1}\) the waiting time component is dominant, whereas for \(d_{\mathrm {cap}} > \frac{\nu }{\nu -1}\) the job size component is dominant. Thus, having \(d = \lceil \min \{\frac{\nu }{\nu -1},N-k\} \rceil \) replicas is sufficient to achieve the optimal asymptotic tail behavior of the response time. For the c.o.c. variant of the fork–join ( \(n_{\mathrm {F}},n_{\mathrm {J}}\) ) model, the tail index of the response time, under some assumptions on the load, equals \(1-\nu \) and \(1-(n_{\mathrm {F}}+1-n_{\mathrm {J}})\nu \) , for identical and i.i.d. replicas, respectively; here, the waiting time component is always dominant. PubDate: 2022-09-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We consider a discrete-time two-dimensional quasi-birth-and-death process (2d-QBD process for short) \(\{(\varvec{X}_n,J_n)\}\) on \(\mathbb {Z}_+^2\times S_0\) , where \(\varvec{X}_n=(X_{1,n},X_{2,n})\) is the level state, \(J_n\) the phase state (background state) and \(S_0\) a finite set, and study asymptotic properties of the stationary tail distribution. The 2d-QBD process is an extension of usual one-dimensional QBD process. By using the matrix analytic method of the queueing theory and the complex analytic method, we obtain the asymptotic decay rate of the stationary tail distribution in an arbitrary direction. This result is an extension of the corresponding result for a certain two-dimensional reflecting random work without background processes, obtained by using the large deviation techniques and the singularity analysis methods. We also present a condition ensuring the sequence of the stationary probabilities geometrically decays without power terms, asymptotically. Asymptotic properties of the stationary tail distribution in the coordinate directions in a 2d-QBD process have already been studied in the literature. The results of this paper are also important complements to those results. PubDate: 2022-08-30

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract The H-derivative of the expected supremum of fractional Brownian motion \(\{B_H(t),t\in {\mathbb {R}}_+\}\) with drift \(a\in {\mathbb {R}}\) over time interval [0, T] $$\begin{aligned} \frac{\partial }{\partial H} {\mathbb {E}}\Big (\sup _{t\in [0,T]} B_H(t) - at\Big ) \end{aligned}$$ at \(H=1\) is found. This formula depends on the quantity \({\mathscr {I}}\) , which has a probabilistic form. The numerical value of \({\mathscr {I}}\) is unknown; however, Monte Carlo experiments suggest \({\mathscr {I}}\approx 0.95\) . As a by-product we establish a weak limit theorem in C[0, 1] for the fractional Brownian bridge, as \(H\uparrow 1\) . PubDate: 2022-08-30

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract This paper studies the subexponential asymptotics of the stationary distribution vector of an asymptotically block-Toeplitz and upper block-Hessenberg (atUBH) Markov chain in discrete time. The atUBH Markov chain is a kind of the upper block-Hessenberg (UBH) one and is a generalization of the M/G/1-type one. The atUBH Markov chain typically arises from semi-Markovian retrial queues, as the queue-length process, its embedded process, or appropriately time-scaled versions of these processes. In this paper, we present subexponential and locally subexponential asymptotic formulas for the stationary distribution vector. We then extend the locally subexponential asymptotic formula to a continuous-time version of the atUBH Markov chain by uniformization and change of time scale. This extension expands the applicability of the locally subexponential asymptotic formula. PubDate: 2022-08-30

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract This paper analyzes various stochastic recursions that arise in queueing and insurance risk models with a ‘semi-linear’ dependence structure. For example, an interarrival time depends on the workload, or the capital, immediately after the previous arrival; or the service time of a customer depends on her waiting time. In each case, we derive and solve a fixed-point equation for the Laplace–Stieltjes transform of a key performance measure of the model, like waiting time or ruin time. PubDate: 2022-08-29

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Ticket queues are popular in many service systems. Upon arrival, each customer is issued a numbered ticket and receives service on a first-come-first-served basis according to the ticket number. There is no physical queue; customers may choose to walk away and return later (before their numbers are called) to receive service. We study the problem of optimal staffing in such a system with two capacity levels, where the staffing decision can only be based on ticket numbers, as opposed to the physical queue length in a traditional system. Using renewal reward theorem, we first derive the long-run average total cost (including customer delay and abandonment costs, operating cost and cost for changing staffing levels) and then obtain the optimal solution using fractional programming. In addition, we pursue a random-walk analysis, which leads to some highly accurate approximations. PubDate: 2022-08-26

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We study critical GI/G/1 queues under finite second-moment assumptions. We show that the busy-period distribution is regularly varying with index half. We also review previously known M/G/1/ and M/M/1 derivations, yielding exact asymptotics as well as a similar derivation for GI/M/1. The busy-period asymptotics determine the growth rate of moments of the renewal process counting busy cycles. We further use this to demonstrate a Balancing Reduces Asymptotic Variance of Outputs (BRAVO) phenomenon for the work-output process (namely the busy time). This yields new insight on the BRAVO effect. A second contribution of the paper is in settling previous conjectured results about GI/G/1 and GI/G/s BRAVO. Previously, infinite buffer BRAVO was generally only settled under fourth-moment assumptions together with an assumption about the tail of the busy period. In the current paper, we strengthen the previous results by reducing to assumptions to existence of \(2+\epsilon \) moments. PubDate: 2022-08-22

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract When designing a message transmission system, from the point of view of making sure that the information transmitted is as fresh as possible, two rules of thumb seem reasonable: use small buffers and adopt a last-in-first-out policy. In this paper, the freshness of information is interpreted as the recently studied “age of information” performance measure. Considering it as a stochastic process operating in a stationary regime, we compute the whole marginal distribution of the age of information for some well-performing systems. We assume that the arrival process is Poisson and that the messages have independent service times with common distribution, i.e., the M/GI model. We demonstrate the usefulness of Palm and Markov-renewal theory to derive results for Laplace transforms. Our numerical studies address some aspects of open questions regarding the optimality of previously proposed scheduling policies, and a policy newly considered herein, for AoI management. PubDate: 2022-08-17

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We introduce a transient reflected Brownian motion in a multidimensional orthant, which is either absorbed at the apex of the cone or escapes to infinity. We address the question of computing the absorption probability, as a function of the starting point of the process. We provide a necessary and sufficient condition for the absorption probability to admit an exponential product form, namely that the determinant of the reflection matrix is zero. We call this condition a dual skew symmetry. It recalls the famous skew symmetry introduced by Harrison (Adv Appl Probab 10:886–905, 1978), which characterizes the exponential stationary distributions in the recurrent case. The duality comes from that the partial differential equation satisfied by the absorption probability is dual to the one associated with the stationary distribution in the recurrent case. PubDate: 2022-08-13

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract This paper studies birth and death processes in interactive random environments where the birth and death rates and the dynamics of the state of the environment are dependent on each other. Two models of a random environment are considered: a continuous-time Markov chain (finite or countably infinite) and a reflected (jump) diffusion process. The background is determined by a joint Markov process carrying a specific interactive mechanism, with an explicit invariant measure whose structure is similar to a product form. We discuss a number of queueing and population-growth models and establish conditions under which the above-mentioned invariant measure can be derived. Next, an analysis of the rate of convergence to stationarity is performed for the models under consideration. We consider two settings leading to either an exponential or a polynomial convergence rate. In both cases we assume that the underlying environmental Markov process has an exponential rate of convergence, but the convergence rate of the joint Markov process is determined by certain conditions on the birth and death rates. To prove these results, a coupling method turns out to be useful. PubDate: 2022-08-12

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We study a queueing system with Erlang arrivals with k phases and Erlang service with m phases. Transition rates among phases vary periodically with time. For these systems, we derive an analytic solution for the asymptotic periodic distribution of the level and phase as a function of time within the period. The asymptotic periodic distribution is analogous to a steady-state distribution for a system with constant rates. If the time within the period is considered part of the state, then it is a steady-state distribution. We also obtain waiting time and busy period distributions. These solutions are expressed as infinite series. We provide bounds for the error of the estimate obtained by truncating the series. Examples are provided comparing the solution of the system of ordinary differential equation with a truncated state space to these asymptotic solutions involving remarkably few terms of the infinite series. The method can be generalized to other level independent quasi-birth-death processes if the singularities of the generating function are known. PubDate: 2022-08-10

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We develop new techniques involving group symmetries and complex analysis to obtain exact solutions for the transition probabilities of the M/M/1/k queueing process. These methods are based on the underlying Markovian structure of these random processes and do not involve any generating functions, Laplace transforms, or advanced special functions. Our techniques exploit the intrinsic group symmetries for both the state spaces and the matrix generators of the Markov processes related to the M/M/1/k queue. These results complement and extend the previous transient solutions given by Takács (Introduction to the theory of queues. University texts in the mathematical sciences, Oxford University Press, New York, 1962). Much of the inspiration for this work comes from viewing this queueing process as a fundamental Markovian model for the dynamics of a bike sharing station. The exact transient analysis for a related stopped version of this process can be used to address fundamental decision-making issues for managing bike-sharing services. PubDate: 2022-08-07

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We study a quantum switch that distributes tripartite entangled states to sets of users. The entanglement switching process requires two steps: First, each user attempts to generate bipartite entanglement between itself and the switch, and second, the switch performs local operations and a measurement to create multipartite entanglement for a set of three users. In this work, we study a simple variant of this system, wherein the switch has infinite memory and the links that connect the users to the switch are identical. This problem formulation is of interest to several distributed quantum applications, while the technical aspects of this work result in new contributions within queueing theory. The state of the system is modeled as continuous-time Markov chain (CTMC), and performance metrics of interest (probability of an empty system, switch capacity, expectation, and variance of the number of qubit-pairs stored) are computed via the solution of a two-dimensional functional equation obtained by reducing it to a boundary value problem on a closed curve. This work is a follow-up of Nain et al. (Proc ACM Measure Anal Comput Syst(POMACS) 4, 2020) where a switch distributing entangled multipartite states to sets of users was studied, but only the switch capacity and the expected number of stored qubits were derived. PubDate: 2022-08-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract In recent years, there is a growing attention towards queueing models with customers who choose their service durations. The model assumptions in the existing literature imply that every customer knows his service demand when he enters into the service position. Clearly, this property is not consistent with some real-life situations. Motivated by this issue, the current work includes a single-server queueing model with customers who dynamically choose their service durations. In this setup, the main result is existence of a quadratic price function which (1) implies an optimal resource allocation from a social point of view and (2) internalizes the externalities in the system. In addition, it is explained how to compute its parameters efficiently. PubDate: 2022-08-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We study the tight upper bound of the transient mean waiting time in the classical GI/GI/1 queue over candidate interarrival-time distributions with finite support, given the first two moments of the interarrival time and the full service-time distribution. We formulate the problem as a non-convex nonlinear program. We derive the gradient of the transient mean waiting time and then show that a stationary point of the optimization can be characterized by a linear program. We develop and apply a stochastic variant of the Frank and Wolfe (Naval Res Logist Q 3:95–110, 1956) algorithm to find a stationary point for any given service-time distribution. We also establish necessary conditions and sufficient conditions for stationary points to be three-point distributions or special two-point distributions. We illustrate by applying simulation together with optimization to analyze several examples. PubDate: 2022-08-01

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We study a load balancing system in the many-server heavy-traffic regime. We consider a system with N servers, where jobs arrive to the system according to a Poisson process and have an exponentially distributed size with mean 1. We parametrize the arrival rate so that the arrival rate per server is \(1-N^{-\alpha }\) , where \(\alpha >0\) is a parameter that represents how fast the load grows with respect to the number of servers. The many-server heavy-traffic regime corresponds to the limit as \(N\rightarrow \infty \) , and subsumes several regimes, such as the Halfin–Whitt regime ( \(\alpha =1/2\) ), the NDS regime ( \(\alpha =1\) ), as \(\alpha \downarrow 0\) it approximates mean field and as \(\alpha \rightarrow \infty \) it approximates the classical heavy-traffic regime. Most of the prior work focuses on regimes with \(\alpha \in [0,1]\) . In this paper, we focus on the case when \(\alpha >1\) and the routing algorithm is power-of-d choices with \(d=\lceil cN^\beta \rceil \) for some constants \(c>0\) and \(\beta \ge 0\) . We prove that \(\alpha +\beta >3\) is sufficient to observe that the average queue length scaled by \(N^{1-\alpha }\) converges to an exponential random variable. In other words, if \(\alpha +\beta >3\) , the scaled average queue length behaves similarly to the classical heavy-traffic regime. In particular, this result implies that if d is constant, we require \(\alpha >3\) and if routing occurs according to JSQ we require \(\alpha >2\) . We provide two proofs to our result: one based on the Transform method introduced in Hurtado-Lange and Maguluri (Stoch Syst 10(4):275–309, 2020) and one based on Stein’s method. In the second proof, we also compute the rate of convergence in Wasserstein’s distance. In both cases, we additionally compute the rate of convergence in expected value. All of our proofs are powered by state space collapse. PubDate: 2022-06-21 DOI: 10.1007/s11134-022-09847-7

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract This paper is devoted to the study of the number of customers in infinite-server systems driven by Hawkes processes. In these systems, the self-exciting arrival process is assumed to be represented by a Hawkes process and the self-exciting service process by a state-dependent Hawkes process (sdHawkes process). Under some suitable conditions, for the \(\mathrm{Hawkes/sdHawkes/\infty }\) system, the Markov property of the system is derived. The joint time-dependent distribution of the number of customers in the system, the arrival intensity and the server intensity is characterized by a system of differential equations. Then, the time-dependent results are also deduced for the \(\mathrm{M/sdHawkes/\infty }\) system. PubDate: 2022-04-29 DOI: 10.1007/s11134-022-09813-3