Let Xn(Λ) be the number of nonoverlapping occurrences of a simple pattern Λ in a sequence of independent and identically distributed (i.i.d.) multistate trials. For fixed k, the exact tail probability P{Xn (∧) < k} is difficult to compute and tends to 0 exponentially as n → ∞. In this paper we use the finite Markov chain imbedding technique and standard matrix theory results to obtain an approximation for this tail probability. The result is extended to compound patterns, Markov-dependent multistate trials, and overlapping occurrences of Λ. Numerical comparisons with Poisson and normal approximations are provided. Results indicate that the proposed approximations perform very well and do significantly better than the Poisson and normal approximations in many cases.

In this paper we derive asymptotically exact expressions for buffer overflow probabilities and cell loss probabilities for a finite buffer which is fed by a large number of independent and stationary sources. The technique is based on scaling, measure change and local limit theorems and extends the recent results of Courcoubetis and Weber on buffer overflow asymptotics. We discuss the cases when the buffers are of the same order as the transmission bandwidth as well as the case of small buffers. Moreover we show that the results hold for a wide variety of traffic sources including ON/OFF sources with heavy-tailed distributed ON periods, which are typical candidates for so-called ‘self-similar’ inputs, showing that the asymptotic cell loss probability behaves in much the same manner for such sources as for the Markovian type of sources, which has important implications for statistical multiplexing. Numerical validation of the results against simulations are also reported.