-
作者：Arratia, Richard; Waterman, Michael S.
作者单位：University of Southern California; University of Southern California
摘要：We consider a sequence matching problem involving the optimal alignment score for contiguous subsequences, rewarding matches and penalizing for deletions and mismatches. This score is used by biologists comparing pairs of DNA or protein sequences. We prove that for two sequences of length n, as n -> infinity, there is a phase transition between linear growth in n, when the penalty parameters are small, and logarithmic growth in n, when the penalties are large. The results are valid for indepen...
-
作者：Cohn, Harry; Jagers, Peter
作者单位：University of Melbourne; Chalmers University of Technology; University of Gothenburg
摘要：A conditioning and martingale method is used to relate the asymptotics of uniformly integrable general branching processes in varying environment to the behaviour of their expectations.
-
作者：Dai, J. G.; Vien Nguyen
作者单位：University System of Georgia; Georgia Institute of Technology; Massachusetts Institute of Technology (MIT)
摘要：The subject of this paper is the heavy traffic behavior of a general class of queueing networks with first-in first-out (FIFO) service discipline. For special cases that require various assumptions on the network structure, several authors have proved heavy traffic limit theorems to justify the approximation of queueing networks by reflecting Brownian motions. Based on these theorems, some have conjectured that the Brownian approximation may in fact be valid for a more general class of queuein...
-
作者：Tsitsiklis, John N.
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We provide a short and elementary proof of the Gittins index theorem for the multi armed bandit problem, for the case where each bandit is modeled as a finite-state semi-Markov process. We also indicate how this proof can be extended to the branching bandits and Klimov problems.
-
作者：Fontes, L. R. G.; Newman, Charles M.
作者单位：Universidade de Sao Paulo
-
作者：Meyn, S. P.; Down, D.
作者单位：University of Illinois System; University of Illinois Urbana-Champaign
摘要：In this paper we study open generalized Jackson networks with general arrival streams and general service time distributions. Assuming that the arrival rate does not exceed the network capacity and that the service times possess conditionally bounded second moments, we deduce stability of the network by bounding the expected waiting time for a customer entering the network. For Markovian networks we obtain convergence of the total work in the system, as well as the mean queue size and mean cus...
-
作者：Gandolfi, Alberto; Kesten, Harry
作者单位：University of California System; University of California Berkeley; Cornell University
摘要：Let {X-v: v is an element of Z(d)} be i.i.d. positive random variables and define M-n = max{Sigma X-v is an element of pi(v) : pi a self-avoiding path of length n starting at the origin}, N-n = max{Sigma(v is an element of xi) X-v: xi a lattice animal of size n containing the origin}. In a preceding paper it was shown that if E{X-0(d)(log+ X-0)(d+a)) < infinity for some a > 0, then there exists some constant C such that w.p.1, 0 <= M-n <= N-n <= Cn for all large n. In this part we improve this...
-
作者：Meyn, Sean P.; Tweedie, R. L.
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Colorado State University System; Colorado State University Fort Collins
摘要：The standard Foster-Lyapunov approach to establishing recurrence and ergodicity of Markov chains requires that the one-step mean drift of the chain be negative outside some appropriately finite set. Malyshev and Men'sikov developed a refinement of this approach for countable state space chains, allowing the drift to be negative after a number of steps depending on the starting state. We show that these countable space results are special cases of those in the wider context of phi-irreducible c...
-
作者：Nguyen, Vien
作者单位：Massachusetts Institute of Technology (MIT)
摘要：Consider a feedforward network of single-server stations populated by multiple job types. Each job requires the completion of a number of tasks whose order of execution is determined by a set of deterministic precedence constraints. The precedence requirements allow some tasks to be done in parallel (in which case tasks would fork) and require that others be processed sequentially (where tasks may join). Jobs of a given type share the same precedence constraints, interarrival time distribution...
-
作者：Alon, Noga; Bollobas, Bela; Brightwell, Grajham; Janson, Svante
作者单位：Tel Aviv University; University of Cambridge; University of London; London School Economics & Political Science; Uppsala University
摘要：We study asymptotics of the number of linear extensions of the random G(n, p) partial order, where p is fixed and n -> infinity. In particular, it is shown that the distribution is asymptotically log-normal.
