Tail behavior of conditional sojourn times in Processor-Sharing queues

We investigate the tail behavior of the sojourn-time distribution for a request of a given length in an M/G/1 Processor-Sharing (PS) queue. An exponential asymptote is proven for general service times in two special cases: when the traffic load is sufficiently high and when the request length is sufficiently small. Furthermore, using the branching process technique we derive exact asymptotics of exponential type for the sojourn time in the M/M/1 queue. We obtain an equation for the asymptotic decay rate and an exact expression for the asymptotic constant. The decay rate is studied in detail and is compared to other service disciplines. Finally, using numerical methods, we investigate the accuracy of the exponential asymptote. AMS 2000 Subject Classifications Primary:60K25,Secondary: 60F10,68M20,90B22     

Asymptotics for M/G/1 low-priority waiting-time tail probabilities

We consider the classical M/G/1 queue with two priority classes and the nonpreemptive and preemptive-resume disciplines. We show that the low-priority steady-state waiting-time can be expressed as a geometric random sum of i.i.d. random variables, just like the M/G/1 FIFO waiting-time distribution. We exploit this structures to determine the asymptotic behavior of the tail probabilities. Unlike the FIFO case, there is routinely a region of the parameters such that the tail probabilities have non-exponential asymptotics. This phenomenon even occurs when both service-time distributions are exponential. When non-exponential asymptotics holds, the asymptotic form tends to be determined by the non-exponential asymptotics for the high-priority busy-period distribution. We obtain asymptotic expansions for the low-priority waiting-time distribution by obtaining an asymptotic expansion for the busy-period transform from Kendall's functional equation. We identify the boundary between the exponential and non-exponential asymptotic regions. For the special cases of an exponential high-priority service-time distribution and of common general service-time distributions, we obtain convenient explicit forms for the low-priority waiting-time transform. We also establish asymptotic results for cases with long-tail service-time distributions. As with FIFO, the exponential asymptotics tend to provide excellent approximations, while the non-exponential asymptotics do not, but the asymptotic relations indicate the general form. In all cases, exact results can be obtained by numerically inverting the waiting-time transform. This revised version was published online in June 2006 with corrections to the Cover Date.     

Resurgent aspects of applied exponential asymptotics

In many physical problems, it is important to capture exponentially small effects that lie beyond-all-orders of an algebraic asymptotic expansion; when collected, the full asymptotic expansion is known as a trans-series. Applied exponential asymptotics has been enormously successful in developing practical tools for studying the leading exponentials of a trans-series expansion, typically for singularly perturbed nonlinear differential or integral equations. Separately to applied exponential asymptotics, there exists a related line of research known as Écalle's theory of resurgence, which, via Borel resummation, describes the connection between trans-series and a certain class of holomorphic functions known as resurgent functions. Most applications and examples of Écalle's resurgence theory focus mainly on nonparametric asymptotic expansions (i.e., differential equations without a parameter). The relationships between these latter areas with applied exponential asymptotics have not been thoroughly examined—largely due to differences in language and emphasis. In this work, we establish these connections as an alternative framework to the factorial-over-power ansatz procedure in applied exponential asymptotics and clarify a number of aspects of applied exponential asymptotic methodology, including Van Dyke's rule and the universality of factorial-over-power ansatzes. We provide a number of useful tools for probing more pathological problems in exponential asymptotics and establish a framework for future applications to nonlinear and multidimensional problems in the physical sciences.     

Superinterpolation in Highly Oscillatory Quadrature

Asymptotic expansions for oscillatory integrals typically depend on the values and derivatives of the integrand at a small number of critical points. We show that using values of the integrand at certain complex points close to the critical points can actually yield a higher asymptotic order approximation to the integral. This superinterpolation property has interesting ramifications for numerical methods based on exploiting asymptotic behaviour. The asymptotic convergence rates of Filon-type methods can be doubled at no additional cost. Numerical steepest descent methods already exhibit this high asymptotic order, but their analyticity requirements can be significantly relaxed. The method can be applied to general oscillators with stationary points as well, through a simple change of variables.     

Coarse-Grained Langevin Approximations and Spatiotemporal Acceleration for Kinetic Monte Carlo Simulations of Diffusion of Interacting Particles

Kinetic Monte Carlo methods provide a powerful computational tool for the simulation of microscopic processes such as the diffusion of interacting particles on a surface, at a detailed atomistic level. However such algorithms are typically computationatly expensive and are restricted to fairly small spatiotemporal scales. One approach towards overcoming this problem was the development of coarse-grained Monte Carlo algorithms. In recent literature, these methods were shown to be capable of efficiently describing much larger length scales while still incorporating information on microscopic interactions and fluctuations. In this paper, a coarse-grained Langevin system of stochastic differential equations as approximations of diffusion of interacting particles is derived, based on these earlier coarse-grained models. The authors demonstrate the asymptotic equivalence of transient and long time behavior of the Langevin approximation and the underlying microscopic process, using asymptotics methods such as large deviations for interacting particles systems, and furthermore, present corresponding numerical simulations, comparing statistical quantities like mean paths, auto correlations and power spectra of the microscopic and the approximating Langevin processes. Finally, it is shown that the Langevin approximations presented here are much more computationally efficient than conventional Kinetic Monte Carlo methods, since in addition to the reduction in the number of spatial degrees of freedom in coarse-grained Monte Carlo methods, the Langevin system of stochastic differential equations allows for multiple particle moves in a single timestep.     

Tail Asymptotics for HOL Priority Queues Handling a Large Number of Independent Stationary Sources

In this paper we study the asymptotics of the tail of the buffer occupancy distribution in buffers accessed by a large number of stationary independent sources and which are served according to a strict HOL priority rule. As in the case of single buffers, the results are valid for a very general class of sources which include long-range dependent sources with bounded instantaneous rates. We first consider the case of two buffers with one of them having strict priority over the other and we obtain asymptotic upper bound for the buffer tail probability for lower priority buffer. We discuss the conditions to have asymptotic equivalents. The asymptotics are studied in terms of a scaling parameter which reflects the server speed, buffer level and the number of sources in such a way that the ratios remain constant. The results are then generalized to the case of M buffers which leads to the source pooling idea. We conclude with numerical validation of our formulae against simulations which show that the asymptotic bounds are tight. We also show that the commonly suggested reduced service rate approximation can give extremely low estimates.     

Circulant Embedding of Approximate Covariances for Inference From Gaussian Data on Large Lattices

Recently proposed computationally efficient Markov chain Monte Carlo (MCMC) and Monte Carlo expectation–maximization (EM) methods for estimating covariance parameters from lattice data rely on successive imputations of values on an embedding lattice that is at least two times larger in each dimension. These methods can be considered exact in some sense, but we demonstrate that using such a large number of imputed values leads to slowly converging Markov chains and EM algorithms. We propose instead the use of a discrete spectral approximation to allow for the implementation of these methods on smaller embedding lattices. While our methods are approximate, our examples indicate that the error introduced by this approximation is small compared to the Monte Carlo errors present in long Markov chains or many iterations of Monte Carlo EM algorithms. Our results are demonstrated in simulation studies, as well as in numerical studies that explore both increasing domain and fixed domain asymptotics. We compare the exact methods to our approximate methods on a large satellite dataset, and show that the approximate methods are also faster to compute, especially when the aliased spectral density is modeled directly. Supplementary materials for this article are available online.     

An algorithm to construct Monte Carlo confidence intervals for an arbitrary function of probability distribution parameters

We derive a new algorithm for calculating an exact confidence interval for a parameter of location or scale family, based on a two-sided hypothesis test on the parameter of interest, using some pivotal quantities. We use this algorithm to calculate approximate confidence intervals for the parameter or a function of the parameter of one-parameter continuous distributions. After appropriate heuristic modifications of the algorithm we use it to obtain approximate confidence intervals for a parameter or a function of parameters for multi-parameter continuous distributions. The advantage of the algorithm is that it is general and gives a fast approximation of an exact confidence interval. Some asymptotic (analytical) results are shown which validate the use of the method under certain regularity conditions. In addition, numerical results of the method compare well with those obtained by other known methods of the literature on the exponential, the normal, the gamma and the Weibull distribution.     

Analysis of Wave Propagation in 1D Inhomogeneous Media

In this paper, we consider the one-dimensional inhomogeneous wave equation with particular focus on its spectral asymptotic properties and its numerical resolution. In the first part of the paper, we analyze the asymptotic nodal point distribution of high-frequency eigenfunctions, which, in turn, gives further information about the asymptotic behavior of eigenvalues and eigenfunctions. We then turn to the behavior of eigenfunctions in the high- and low-frequency limit. In the latter case, we derive a homogenization limit, whereas in the first we show that a sort of self-homogenization occurs at high frequencies. We also remark on the structure of the solution operator and its relation to desired properties of any numerical approximation. We subsequently shift our focus to the latter and present a Galerkin scheme based on a spectral integral representation of the propagator in combination with Gaussian quadrature in the spectral variable with a frequency-dependent measure. The proposed scheme yields accurate resolution of both high- and low-frequency components of the solution and as a result proves to be more accurate than available schemes at large time steps for both smooth and nonsmooth speeds of propagation.     

Dynamical characteristics of decaying Lamb couples

A multiple-scale adiabatic asymptotic theory is developed to describe the dissipation of the solitary Lamb couple or modon solutions of the two-dimensional Navier-Stokes equations. The transport equations describing the evolution of the Lamb couple are obtained as solvability conditions for a direct asymptotic expansion assuming a relatively large but finite Reynolds number and are equivalent to globally-integrated leading-order enstrophy and energy balances. The asymptotic theory predicts that the spectral or spatial characteristics of the decaying Lamb couple are temporally invariant and that there is a simple exponential decay in the amplitude and translation speed. We compare the predictions of the theory with a high-resolution numerical simulation. The global and local predictions of the theory and the results of the numerical simulation are in very good agreement. As well, we present a time-series of vorticity-stream function scatter diagrams as derived from the numerical simulation to show that thenon-analytic linear vorticity-stream function relationship is being continuously maintained during the perturbed evolution of the Lamb couple.     

Asymptotic Expansion for the Null Distribution of the <Emphasis Type="Italic">F</Emphasis>-statistic in One-way ANOVA under Non-normality

In this paper we derive the asymptotic expansion of the null distribution of the F-statistic in one-way ANOVA under non-normality. The asymptotic framework is when the number of treatments is moderate but sample size per treatment (replication size) is small. This kind of asymptotics will be relevant, for example, to agricultural screening trials where large number of cultivars are compared with few replications per cultivar. There is also a huge potential for the application of this kind of asymptotics in microarray experiments. Based on the asymptotic expansion we will devise a transformation that speeds up the convergence to the limiting distribution. The results indicate that the approximation based on limiting distribution are unsatisfactory unless number of treatments is very large. Our numerical investigations reveal that our asymptotic expansion performs better than other methods in the literature when there is skewness in the data or even when the data comes from a symmetric distribution with heavy tails.     

On the Cauchy problem for a nonlinear Sobolev type equation

We study the large-time asymptotics of the solution of the Cauchy problem for a nonlinear Sobolev type equation. We show that if initial data are sufficiently small in some norm, then the leading term of the asymptotic expansion is determined by the linear part of the equation and has exponential character, while the nonlinearity affects the decay order of the remainder.     

The arbitrary order implicit multistep schemes of exponential fitting and their applications

We develop the arbitrary order implicit multistep schemes of exponential fitting (EF) for systems of ordinary differential equations. We use an explicit EF scheme to predict an approximation, and then use an implicit EF scheme to correct this prediction. This combination is called a predictor–corrector EF method. We demonstrate the accuracy and efficiency of the new predictor–corrector methods via application to a variety of test cases and comparison with other analytical and numerical results. The numerical results show that the schemes are highly accurate and computationally efficient.     

Computation of viscous or nonviscous conservation law by domain decomposition based on asymptotic analysis

An accurate and efficient numerical method has been developed for a nonlinear diffusion convection-dominated problem. The scheme combines asymptotic methods with usual solution techniques for hyperbolic problems. After having localized shock or corner layers and rescaling, first terms of the inner expansion are computed. Using the same concepts gives a method to compute a very accurate solution of the nonlinear conservation law. Because our numerical scheme is based on a uniform approximation throughout the domain, the shock is localized very accurately and there is practically no smearing out. Numerical computations are presented. Another novel feature is the ability to break down the problem according to subdomains of different local behavior, based on asymptotic analysis, which may make it feasible to do computations with different processors.     

Asymptotic relations in queueing theory

For the GI?G?1 queueing system a number of asymptotic results are reviewed. Discussed are asymptotics related to the time parameter for t → ∞ relaxation times, heavy traffic theory, restricted accessibility with large bounds, approximation by diffusion processes, exponential and regular variation of the tail of the waiting time distribution, limit theorems and extreme value theorems.     

Large buffer asymptotics for generalized processor sharing queues with Gaussian inputs

In this paper we derive large-buffer asymptotics for a two-class Generalized Processor Sharing (GPS) model. We assume both classes to have Gaussian characteristics. We distinguish three cases depending on whether the GPS weights are above or below the average rate at which traffic is sent. First, we calculate exact asymptotic upper and lower bounds, then we calculate the logarithmic asymptotics, and finally we show that the decay rates of the upper and lower bound match. We apply our results to two special Gaussian models: the integrated Gaussian process and the fractional Brownian motion. Finally we derive the logarithmic large-buffer asymptotics for the case where a Gaussian flow interacts with an on-off flow. AMS Subject Classification Primary—60K25; Secondary—68M20, 60G15     

Two-parameter asymptotic approximations in the analysis of a thin solid fixed on a small part of its boundary

Planar elasticity problems are considered for thin domains fixedalong a small part of the end region boundary. The analysisinvolves two small parameters: the normalized thickness of thebody and the normalized length of the fixed part of the boundary.The aim of the paper is to derive an asymptotic approximationof the solution to a boundary-value problem in such a domainand, in particular, analyze the ‘effective boundary conditions’,which occur for the leading-order terms of the asymptotics.We include applications for problems of both anti-plane shearand plane strain elasticity.     

Efficient methods for Volterra integral equations with highly oscillatory Bessel kernels

In this paper, we introduce efficient methods for the approximation of solutions to weakly singular Volterra integral equations of the second kind with highly oscillatory Bessel kernels. Based on the asymptotic analysis of the solution, we derive corresponding convergence rates in terms of the frequency for the Filon method, and for piecewise constant and linear collocation methods. We also present asymptotic schemes for large values of the frequency. These schemes possess the property that the numerical solutions become more accurate as the frequency increases.     

A geometric analysis of front propagation in a family of degenerate reaction-diffusion equations with cutoff

We investigate the effects of a Heaviside cutoff on the dynamics of traveling fronts in a family of scalar reaction-diffusion equations with degenerate polynomial potential that includes the classical Zeldovich equation. We prove the existence and uniqueness of front solutions in the presence of the cutoff, and we derive the leading-order asymptotics of the corresponding propagation speed in terms of the cutoff parameter. For the Zeldovich equation, an explicit solution to the equation without cutoff is known, which allows us to calculate higher-order terms in the resulting expansion for the front speed; in particular, we prove the occurrence of logarithmic (switchback) terms in that case. Our analysis relies on geometric methods from dynamical systems theory and, in particular, on the desingularization technique known as ‘blow-up.’