Search

The aim of this paper is to develop a method for proving almost sure convergence in the Gromov-Hausdorff-Prokhorov topology for a class of models of growing random graphs that generalises Rémy's algorithm for binary trees. We describe the obtained limits using some iterative gluing construction that generalises the famous line-breaking construction of Aldous' Brownian tree, and we characterize some of them using the self-similarity property in law that they satisfy. To do that, we develop a framework in which a metric space is constructed by gluing smaller metric spaces, called blocks, along the structure of a (possibly infinite) discrete tree. Our growing random graphs seen as metric spaces can be understood in this framework, that is, as evolving blocks glued along a growing discrete tree structure. Their scaling limit convergence can then be obtained by separately proving the almost sure convergence of every block and verifying some relative compactness property for the whole structure. For the particular models that we study, the discrete tree structure behind the construction has the distribution of an affine preferential attachment tree or a weighted recursive tree. We strongly rely on results concerning those two models and their connection, obtained in the companion paper Sénizergues (2021). [ABSTRACT FROM AUTHOR]

Let {Xi(t): t ∈ S ⊂ Rd}i=1,2,...,n be independent copies of a stationary centered Gaussian field with almost surely smooth sample paths. In this paper, we are interested in the con- junction probability defined as P (∃t ∈ S: Xi(t) ≥ u, ∀i = 1, 2, . . ., n) for a given threshold level u. As u → ∞, we will provide an asymptotic formula for the conjunction probability. This asymptotic formula is derived from the behaviour of the volume of the set of local maximum points. The proof relies on a result of Azaïs and Wschebor (2014) describing the shape of the excursion set of a stationary centered Gaussian field. Our result partially confirms the validity of the Euler characteristic method. [ABSTRACT FROM AUTHOR]

We work on a Galton-Watson tree with random weights, in the so-called "subdiffusive" regime. We study the rate of decay of the conductance between the root and the n-th level of the tree, as n goes to infinity, by a mostly analytic method. It turns out the order of magnitude of the expectation of this conductance can be less than 1=n (in contrast with the results of Addario-Berry-Broutin-Lugosi and Chen-Hu-Lin), depending on the value of the second zero of the characteristic function associated to the model. We also prove the almost sure (and in Lp for some p > 1) convergence of this conductance divided by its expectation towards the limit of the additive martingale. [ABSTRACT FROM AUTHOR]

Considering a real-valued diffusion, a real-valued reward function and a positive discount rate, we provide an algorithm to solve the optimal stopping problem consisting in finding the optimal expected discounted reward and the optimal stopping time at which it is attained. Our approach is based on Dynkin's characterization of the value function. The combination of Riesz's representation of α-excessive functions and the inversion formula gives the density of the representing measure, being only necessary to determine its support. This last task is accomplished through an algorithm. The proposed method always arrives to the solution, thus no verification is needed, giving, in particular, the shape of the stopping region. Generalizations to diffusions with atoms in the speed measure and to non smooth payoffs are analyzed. [ABSTRACT FROM AUTHOR]

We prove a large deviation principle for a greedy exploration process on an Erdös-Rényi (ER) graph when the number of nodes goes to infinity. To prove our main result, we use the general strategy to study large deviations of processes proposed by Feng and Kurtz (2006), based on the convergence of non-linear semigroups. The rate function can be expressed in a closed-form formula, and associated optimization problems can be solved explicitly, providing the large deviation trajectory. Also, we derive large deviation results for the size of the maximum independent set discovered by such an algorithm and analyse the probability that it exceeds known bounds for the maximal independent set. We also analyse the link between these results and the landscape complexity of the independent set and the exploration dynamic. [ABSTRACT FROM AUTHOR]