-
作者：Gamarnik, David; Sudan, Madhu
作者单位：Massachusetts Institute of Technology (MIT); Harvard University
摘要：Local algorithms on graphs are algorithms that run in parallel on the nodes of a graph to compute some global structural feature of the graph. Such algorithms use only local information available at nodes to determine local aspects of the global structure, while also potentially using some randomness. Recent research has shown that such algorithms show significant promise in computing structures like large independent sets in graphs locally. Indeed the promise led to a conjecture by Hatami, Lo...
-
作者：Cass, Thomas; Ogrodnik, Marcel
作者单位：Imperial College London
摘要：The accumulated local p-variation functional [Ann. Probab. 41 (213) 3026-3050] arises naturally in the theory of rough paths in estimates both for solutions to rough differential equations (RDEs), and for the higher-order terms of the signature (or Lyons lift). In stochastic examples, it has been observed that the tails of the accumulated local p-variation functional typically decay much faster than the tails of classical p-variation. This observation has been decisive, for example, for proble...
-
作者：Jung, Paul; Owada, Takashi; Samorodnitsky, Gennady
作者单位：Korea Advanced Institute of Science & Technology (KAIST); Purdue University System; Purdue University; Cornell University; Cornell University
摘要：We prove a functional central limit theorem for partial sums of symmetric stationary long-range dependent heavy tailed infinitely divisible processes. The limiting stable process is particularly interesting due to its long memory which is quantified by a Mittag Leffler process induced by an associated Harris chain, at the discrete-time level. Previous results in Owada and Samorodnitsky [Ann. Probab. 43 (2015) 240-285] dealt with positive dependence in the increment process, whereas this paper ...
-
作者：Bhamidi, Shankar; van der Hofstad, Remco; Hooghiemstra, Gerard
作者单位：University of North Carolina; University of North Carolina Chapel Hill; Eindhoven University of Technology; Delft University of Technology
摘要：We consider first passage percolation on the configuration model with n vertices, and general independent and identically distributed edge weights assumed to have a density. Assuming that the degree distribution satisfies a uniform X-2 log X-condition, we analyze the asymptotic distribution for the minimal weight path between a pair of typical vertices, as well the number of edges on this path namely the hopcount. Writing L-n for the weight of the optimal path, we show that Ln (log n)/alpha(n)...
-
作者：Chernozhukov, Victor; Chetverikov, Denis; Kato, Kengo
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); University of California System; University of California Los Angeles; University of Tokyo
摘要：This paper derives central limit and bootstrap theorems for probabilities that sums of centered high-dimensional random vectors hit hyperrectangles and sparsely convex sets. Specifically, we derive Gaussian and bootstrap approximations for probabilities P(n(-1/2) Sigma(n)(i=1) X-i is an element of A) where X-1,...,X-n are independent random vectors in R-p and A is a hyperrectangle, or more generally, a sparsely convex set, and show that the approximation error converges to zero even if p = p(n...
-
作者：Cotar, Codina; Thacker, Debleena
作者单位：University of London; University College London; Lund University
摘要：In this paper, we introduce a new simple but powerful general technique for the study of edge- and vertex-reinforced processes with super-linear reinforcement, based on the use of order statistics for the number of edge, respectively of vertex, traversals. The technique relies on upper bound estimates for the number of edge traversals, proved in a different context by Cotar and Limic [Ann. AppL Probab. 19 (2009) 1972-2007] for finite graphs with edge reinforcement. We apply our new method both...
-
作者：Obloj, Jan; Spoida, Peter
作者单位：University of Oxford
摘要：We solve the n-marginal Skorokhod embedding problem for a continuous local martingale and a sequence of probability measures mu(1),...,mu(n) which are in convex order and satisfy an additional technical assumption. Our construction is explicit and is a multiple marginal generalization of the Azema and Yor [In Seminaire de Probabilites, XIII (Univ. Strasbourg, Strasbourg, 1977/78) (1979) 90-115 Springer] solution. In particular, we recover the stopping boundaries obtained by Brown, Hobson and R...
-
作者：Bahlali, Khaled; Eddahbi, M'hamed; Ouknine, Youssef
作者单位：Universite de Toulon; Aix-Marseille Universite; Centre National de la Recherche Scientifique (CNRS); King Saud University; Cadi Ayyad University of Marrakech
摘要：We establish a Krylov-type estimate and an Ito-Krylov change of variable formula for the solutions of one-dimensional quadratic backward stochastic differential equations (QBSDEs) with a measurable generator and an arbitrary terminal datum. This allows us to prove various existence and uniqueness results for some classes of QBSDEs with a square integrable terminal condition and sometimes a merely measurable generator. It turns out that neither the existence of exponential moments of the termin...
-
作者：Friz, Peter K.; Shekhar, Atul
作者单位：Technical University of Berlin; Leibniz Association; Weierstrass Institute for Applied Analysis & Stochastics; Indian Statistical Institute; Indian Statistical Institute Bangalore
摘要：We consider rough paths with jumps. In particular, the analogue of Lyons' extension theorem and rough integration are established in a jump setting, offering a pathwise view on stochastic integration against cadlag processes. A class of Levy rough paths is introduced and characterized by a sub-ellipticity condition on the left-invariant diffusion vector fields and a certain integrability property of the Carnot-Caratheodory norm with respect to the Levy measure on the group, using Hunt's framew...
-
作者：Gantert, Nina; Guo, Xiaoqin; Nagel, Jan
作者单位：Technical University of Munich; Purdue University System; Purdue University
摘要：We consider random walk among i.i.d., uniformly elliptic conductances on Z(d), and prove the Einstein relation (see Theorem 1). It says that the derivative of the velocity of a biased walk as a function of the bias equals the diffusivity in equilibrium. For fixed bias, we show that there is an invariant measure for the environment seen from the particle. These invariant measures are often called steady states. The Einstein relation follows at least for d >= 3, from an expansion of the steady s...
