-
作者：Chi, Zhiyi
作者单位：University of Connecticut
摘要：Let F be a distribution function on the line in the domain of attraction of a stable law with exponent alpha is an element of (0,1/2]. We establish the strong renewal theorem for a random walk S-1, S-2, ... with step distribution F, by extending the large deviations approach in Doney [Probab. Theory Related Fileds 107 (1997) 451-465]. This is done by introducing conditions on F that in general rule out local large deviations bounds of the type P{S-n is an element of(x, x + h]} = O(n)(F) over b...
-
作者：Luczak, Malwina J.; McDiarmid, Colin
作者单位：University of London; Queen Mary University London; University of Oxford
摘要：We consider an online network routing problem in continuous time, where calls have Poisson arrivals and exponential durations. The first-fit dynamic alternative routing algorithm sequentially selects up to d random twolink routes between the two endpoints of a call, via an intermediate node, and assigns the call to the first route with spare capacity on each link, if there is such a route. The balanced dynamic alternative routing algorithm simultaneously selects d random two-link routes, and t...
-
作者：Bandyopadhyay, Antar; Sajadi, Farkhondeh
作者单位：Indian Statistical Institute; Indian Statistical Institute Delhi
摘要：In this work we consider a simple SIR infection spread model on a finite population of n agents represented by a finite graph G. Starting with a fixed set of initial infected vertices the infection spreads in discrete time steps, where each infected vertex tries to infect its neighbors with a fixed probability beta is an element of (0, 1), independently of others. It is assumed that each infected vertex dies out after an unit time and the process continues till all infected vertices die out. T...
-
作者：Meka, Raghu
作者单位：Microsoft
摘要：We give a polynomial time approximation scheme (PTAS) for computing the supremum of a Gaussian process. That is, given a finite set of vectors V subset of R-d, we compute a (1 + epsilon)-factor approximation to E-X <- N-d [sup(v) (is an element of V) vertical bar < v, X >vertical bar] deterministically in time poly(d) . vertical bar V vertical bar(O epsilon(1)). Previously, only a constant factor deterministic polynomial time approximation algorithm was known due to the work of Ding, Lee and P...
-
作者：Bhamidi, Shankar; Steele, J. Michael; Zaman, Tauhid
作者单位：University of North Carolina; University of North Carolina Chapel Hill; University of Pennsylvania; Massachusetts Institute of Technology (MIT)
摘要：Condensation phenomenon is often observed in social networks such as Twitter where one superstar vertex gains a positive fraction of the edges, while the remaining empirical degree distribution still exhibits a power law tail. We formulate a mathematically tractable model for this phenomenon that provides abetter fit to empirical data than the standard preferential attachment model across an array of networks observed in Twitter. Using embeddings in an equivalent continuous time version of the...
-
作者：Robert, Philippe y; Veber, Amandine
作者单位：Institut Polytechnique de Paris; Ecole Polytechnique; ENSTA Paris
摘要：The paper investigates the properties of a class of resource allocation algorithms for communication networks: if a node of this network has x requests to transmit, then it receives a fraction of the capacity proportional to log(1 + x), the logarithm of its current load. A detailed fluid scaling analysis of such a network with two nodes is presented. It is shown that the interaction of several time scales plays an important role in the evolution of such a system, in particular its coordinates ...
-
作者：Billey, Sara; Burdzy, Krzysztof; Pal, Soumik; Sagan, Bruce E.
作者单位：University of Washington; University of Washington Seattle; Michigan State University
摘要：We study a model of mass redistribution on a finite graph. We address the questions of convergence to equilibrium and the rate of convergence. We present theorems on the distribution of empty sites and the distribution of mass at a fixed vertex. These distributions are related to random permutations with certain peak sets.
-
作者：Borodin, Alexei; Bufetov, Alexey; Olshanski, Grigori
作者单位：Massachusetts Institute of Technology (MIT); Kharkevich Institute for Information Transmission Problems of the RAS; Russian Academy of Sciences; HSE University (National Research University Higher School of Economics)
摘要：We prove the existence of a limit shape and give its explicit description for certain probability distribution on signatures (or highest weights for unitary groups). The distributions have representation theoretic origin-they encode decomposition on irreducible characters of the restrictions of certain extreme characters of the infinite-dimensional unitary group U (infinity) to growing finite-dimensional unitary subgroups U (N). The characters of U(infinity) are allowed to depend on N. In a sp...
-
作者：Mueller, Sebastian
作者单位：Aix-Marseille Universite; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI)
摘要：The aim of this paper is to undetline the relation between reversible growth processes and invariant percolation. We present two models of interacting branching random walks (BRWs), truncated BRWs and competing BRWs, where survival of the growth process can be formulated as the existence of an infinite cluster in an invariant percolation on a tree. Our approach is fairly conceptual and allows generalizations to a wider set of reversible growth processes.
-
作者：Davis, M. H. A.; Pistorius, M. R.
作者单位：Imperial College London
摘要：For a given Markov process X and survival function (H) over bar on R+, the inverse first-passage time problem (IFPT) is to find a bather function b : R+ -> [-infinity, +infinity] such that the survival function of the first-passage time tau(b) = inf{t >= 0: X (t) < b(t)} is given by <(H)over bar>. In this paper, we consider a version of the IFPT problem where the bather is fixed at zero and the problem is to find an initial distribution mu and a time-change I such that for the time-changed pro...
