The method of types is one of the most popular techniques in information theory and combinatorics. Two sequences of equal length have the same type if they have identical empirical distributions. In this paper, we focus on Markov types, that is, sequences generated by a Markov source (of order one). We note that sequences having the same Markov type share the same so-called balanced frequency matrix that counts the number of distinct pairs of symbols. We enumerate the number of Markov types for sequences of length over an alphabet of size . This turns out to be asymptotically equivalent to estimating the number of the balanced frequency matrices, the number of integer solutions of a system of linear Diophantine equations, and the number of connected Eulerian multigraphs. For fixed , we prove that the number of Markov types is asymptotically equal to d(m) nm2-m/(m2-m)! where we give an integral representation for d(m). For m →∞, we conclude that asymptotically the number of types is equivalent to √2m3m/2em2/m2m22mπm/2nm2-m provided that m = o(n1/4). These findings are derived by analytical techniques ranging from analytic combinatorics, to multidimensional generating functions, to the saddle point method.

We study the height of a digital search tree (DST) built from n random strings generated by an unbiased memoryless source (i.e., all symbols are equally likely). We shall argue that the height of such a tree is equivalent to the length of the longest phrase in the Lempel--Ziv parsing scheme that partitions a random sequence into n phrases. We also analyze the longest phrase in the Lempel--Ziv scheme in which a string of fixed length m is parsed into a random number of phrases. In the course of our analysis, we shall identify four natural regions of the height distribution and characterize them asymptotically for large n. In particular, for the region where most of the probability mass is concentrated, the asymptotic distribution of the height exhibits an exponential of a Gaussian distribution (with an oscillating term) around the most probable value $k_1 = \lfloor \log_2 n + \sqrt{2\log_2 n} - \log_2 ( \sqrt{2 \log_2 n} ) + \frac{1}{\log 2} - \frac{1}{2} \rfloor +1$. More precisely, we shall prove that the asymptotic distribution of a DST is concentrated on either the one point k 1 or the two points k 1 -1 and k 1 , which actually proves (slightly modified) Kesten's conjecture quoted in [Probab. Theory Related Fields, 79 (1988), pp. 509--542]. Finally, we compare our findings for DST with the asymptotic distributions of the height for other digital trees such as tries and PATRICIA tries. We derive these results by a combination of analytic methods such as generating functions, Laplace transform, the saddle point method, and ideas of applied mathematics such as linearization, asymptotic matching, and the WKB method. Our analysis makes certain assumptions about the forms of some of the asymptotic expansions as well as their asymptotic matching. We also present detailed numerical verification of our results.

We consider a processor shared M/M/1 queue that can accommodate at most a finite number K of customers. Using singular perturbation techniques, we construct asymptotic approximations to the distribution of a customer's sojourn time. We assume that K is large and treat several different cases of the model parameters and also treat different time scales. Extensive numerical comparisons are used to back up our asymptotic formulas.— Author's Abstract

A closed BCMP queuing network consisting of R job classes (chains), K+1 single-server, fixed-rate nodes, and M/sub j/ class j jobs (j=1, 2, . . ., R) is considered. Asymptotic expansions are constructed for the partition function under assumptions (1) K>>1, (2) M/sub j/>>1 for each j, and (3) K/M/sub j/=O(1). Analytic expressions for performance measures such as the mean queue length are also given. The approach employs the ray method and the method of matched asymptotic expansions. Numerical comparisons illustrate the accuracy of the approximations.>

In this paper, a new asymptotic method is developed for analyzing closed BCMP queuing networks with a single class (chain) consisting of a large number of customers, a single infinite server queue, and a large number of single server queues with fixed (state-independent) service rates. Asymptotic approximations are computed for the normalization constant (partition function) starting directly from a recursion relation of Buzen. The approach of the authors employs the ray method of geometrical optics and the method of matched asymptotic expansions. The method is applicable when the servers have nearly equal relative utilizations or can be divided into classes with nearly equal relative utilizations. Numerical comparisons are given that illustrate the accuracy of the asymptotic approximations.

A closed multiple access system composed of M sources and a single service facility is analyzed. The closed network is modeled as a finite source ${M / G / 1}$ queueing system. We consider systems with a large number of sources (i.e. $M \gg 1$) and we assume that the mean time required to process an individual request is short $(O({1 / M}))$. We then construct asymptotic approximations to the stationary distribution of the number of requests in the service facility by using the method of matched asymptotic expansions. We give formulas for the first and second moments of the number of requests, for all traffic intensities.

We consider two parallel, infinite capacity,M/G/1queues characterized by (U_{1}(t), U_{2}(t)) withU_{j}(t)denoting the unfinished work (buffer content) in queuej. A new arrival is assigned to the queue with the smaller buffer content. We construct formal (as opposed to rigorous) asymptotic approximations to the Joint stationary distribution of the Markov process (U_{1}(t), U_{2}(t)), treating separately the asymptotic limits of heavy traffic, light traffic, and large buffer contents. In heavy traffic, the stochastic processesU_{1}(t) + U_{2}(t)andU_{2}(t) - U_{1}(t)become independent, with the distribution ofU_{1}(t) + U_{2}(t)identical to the heavy traffic waiting time distribution in the standardM/G/2queue, and the distribution ofU_{2}(t) - U_{1}(t)closely related to the tail of the service time density. In light traffic, we obtain a formal expansion of the stationary distribution in powers of the arrival rate.

We consider two parallelM/M/1queueing systems where a new arrival (customer, job, message) joins the shorter of the two queues. Such problems arise naturally in computer communications and packet switched data networks. An asymptotic approach is developed to obtain approximations to the steady-state joint distribution of the number of customers in the two systems. We first analyze the case where the two queueing systems are identical and then consider the case when the two servers work at different rates. Our results are shown to agree with the expansions of known exact solutions, when such solutions are available, and to yield new approximations when such solutions are not available.