-
作者：Bhattacharya, Bhaswar B.; Mukherjee, Sumit
作者单位：University of Pennsylvania; Columbia University
摘要：In this paper, we study the asymptotics of the degree sequence of permutation graphs associated with a sequence of random permutations. The limiting finite-dimensional distributions of the degree proportions are established using results from graph and permutation limit theories. In particular, we show that for a uniform random permutation, the joint distribution of the degree proportions of the vertices labeled [nr(1)], [nr(2)],..., [nr(s)] in the associated permutation graph converges to ind...
-
作者：Gravner, Janko; Sivakoff, David
作者单位：University of California System; University of California Davis; University System of Ohio; Ohio State University
摘要：Jigsaw percolation is a nonlocal process that iteratively merges connected clusters in a deterministic puzzle graph by using connectivity properties of a random people graph on the same set of vertices. We presume the Erdos-Renyi people graph with edge probability p and investigate the probability that the puzzle is solved, that is, that the process eventually produces a single cluster. In some generality, for puzzle graphs with N vertices of degrees about D (in the appropriate sense), this pr...
-
作者：Braverman, Anton; Dai, J. G.
作者单位：Cornell University
摘要：We consider M/Ph/n + M queueing systems in steady state. We prove that the Wasserstein distance between the stationary distribution of the normalized system size process and that of a piecewise Ornstein Uhlenbeck (OU) process is bounded by C/root T., where the constant C is independent of the arrival rate A and the number of servers n as long as they are in the HalfinWhitt parameter regime. For each integer m > 0, we also establish a similar bound for the difference of the mth steady-state mom...
-
作者：Bank, Peter; Kauppila, Helena
作者单位：Technical University of Berlin; Columbia University
摘要：We develop a general theory of convex duality for certain singular control problems, taking the abstract results by Kramkov and Schachermayer [Ann. Appl Probab. 9 (1999) 904-950] for optimal expected utility from nonnegative random variables to the level of optimal expected utility from increasing, adapted controls. The main contributions are the formulation of a suitable duality framework, the identification of the problem's dual functional as well as the full duality for the primal and dual ...
-
作者：Iyer, Srikanth; Vaze, Rahul
作者单位：Indian Institute of Science (IISC) - Bangalore; Tata Institute of Fundamental Research (TIFR)
摘要：In wireless networks, where each node transmits independently of other nodes in the network (the ALOHA protocol), the expected delay experienced by a packet until it is successfully received at any other node is known to be infinite for the signal-to-interference-plus-noise-ratio (SINR) model with node locations distributed according to a Poisson point process. Consequently, the information velocity, defined as the limit of the ratio of the distance to the destination and the time taken for a ...
-
作者：Blanchet, Jose; Chen, Xinyun; Dong, Jing
作者单位：Columbia University; Wuhan University; Northwestern University
摘要：Consider a multidimensional diffusion process X = {X (t) : t is an element of [0, 1]}. Let epsilon > 0 be a deterministic, user defined, tolerance error parameter. Under standard regularity conditions on the drift and diffusion coefficients of X, we construct a probability space, supporting both X and an explicit, piecewise constant, fully simulatable process X-epsilon such that (sup)(0 <= t <= 1)parallel to X-epsilon (t) - X parallel to(infinity) < epsilon with probability one. Moreover, the ...
-
作者：Goldstein, Larry; Nourdin, Ivan; Peccati, Giovanni
作者单位：University of Southern California; University of Luxembourg
摘要：Intrinsic volumes of convex sets are natural geometric quantities that also play important roles in applications, such as linear inverse problems with con, vex constraints, and constrained statistical inference. It is a well-known fact that, given a closed convex cone CC R-d, its conic intrinsic volumes determine a probability measure on the finite set (0, 1,...., d}, customarily denoted by L(V-C). The aim of the present paper is to provide a Berry Esseen bound for the normal approximation of ...
-
作者：Li, Yao; Young, Lai-Sang
作者单位：University of Massachusetts System; University of Massachusetts Amherst; New York University
摘要：We consider a stochastic particle system in which a finite number of particles interact with one another via a common energy tank. Interaction rate for each particle is proportional to the square root of its kinetic energy, as is consistent with analogous mechanical models. Our main result is that the rate of convergence to equilibrium for such a system is similar to t(-2), more precisely it is faster than a constant times t(-2+epsilon) for any epsilon > 0. A discussion of exponential vs. poly...
-
作者：Bhattacharya, Bhaswar B.; Diaconis, Persi; Mukherjeet, Sumit
作者单位：University of Pennsylvania; Stanford University; Columbia University
摘要：This paper proves limit theorems for the number of monochromatic edges in uniform random colorings of general random graphs. These can be seen as generalizations of the birthday problem (what is the chance that there are two friends with the same birthday?). It is shown that if the number of colors grows to infinity, the asymptotic distribution is either a Poisson mixture or a Normal depending solely on the limiting behavior of the ratio of the number of edges in the graph and the number of co...
-
作者：Pillai, Natesh S.; Smith, Aaron
作者单位：Harvard University; University of Ottawa
摘要：Determining the mixing time of Kac's random walk on the sphere Sn-1 is a long-standing open problem. We show that the total variation mixing time of Kac's walk on Sn-1 is between 1/2n log(n) and 200n log(n) for all n sufficiently large. Our bound is thus optimal up to a constant factor, improving on the best-known upper bound of O(n(5) log(n)(2)) due to Jiang [Ann. AppL Probab. 22 (2012) 1712-1727]. Our main tool is a non-Markovian coupling recently introduced by the second author in [Ann. App...
