Prediction and Conditional Simulation of a 2D Lognormal Diffusion Random Field

This paper describes techniques for estimation, prediction and conditional simulation of two-parameter lognormal diffusion random fields which are diffusions on each coordinate and satisfy a particular Markov property. The estimates of the drift and diffusion coefficients, which characterize the lognormal diffusion random field under certain conditions, are used for obtaining kriging predictors. The conditional simulations are obtained using the estimates of the drift and diffusion coefficients, kriging prediction and unconditional simulation for the lognormal diffusion random field.      

Logarithmic Sobolev,isoperimetry and transport inequalities on graphs

In this paper,we study some functional inequalities(such as Poincaré inequality,logarithmic Sobolev inequality,generalized Cheeger isoperimetric inequality,transportation-information inequality and transportation-entropy inequality) for reversible nearest-neighbor Markov processes on connected finite graphs by means of(random) path method.We provide estimates of the involved constants.     

Quenched invariance principle for simple random walk on discrete point processes

We consider the simple random walk on random graphs generated by discrete point processes. This random walk moves on graphs whose vertex set is a random subset of a cubic lattice and whose edges are lines between any consecutive vertices on lines parallel to each coordinate axis. Under the assumption that the discrete point processes are finitely dependent and stationary, we prove that the quenched invariance principle holds, i.e., for almost every configuration of the point process, the path distribution of the walk converges weakly to that of a Brownian motion.     

Further results on random cubic planar graphs

We provide precise asymptotic estimates for the number of several classes of labeled cubic planar graphs, and we analyze properties of such random graphs under the uniform distribution. This model was first analyzed by Bodirsky and coworkers. We revisit their work and obtain new results on the enumeration of cubic planar graphs and on random cubic planar graphs. In particular, we determine the exact probability of a random cubic planar graph being connected, and we show that the distribution of the number of triangles in random cubic planar graphs is asymptotically normal with linear expectation and variance. To the best of our knowledge, this is the first time one is able to determine the asymptotic distribution for the number of copies of a fixed graph containing a cycle in classes of random planar graphs arising from planar maps.     

Random Walks on Directed Covers of Graphs

Directed covers of finite graphs are also known as periodic trees or trees with finitely many cone types. We expand the existing theory of directed covers of finite graphs to those of infinite graphs. While the lower growth rate still equals the branching number, upper and lower growth rates no longer coincide in general. Furthermore, the behavior of random walks on directed covers of infinite graphs is more subtle. We provide a classification in terms of recurrence and transience and point out that the critical random walk may be recurrent or transient. Our proof is based on the observation that recurrence of the random walk is equivalent to the almost sure extinction of an appropriate branching process. Two examples in random environment are provided: homesick random walk on infinite percolation clusters and random walk in random environment on directed covers. Furthermore, we calculate, under reasonable assumptions, the rate of escape with respect to suitable length functions and prove the existence of the asymptotic entropy providing an explicit formula which is also a new result for directed covers of finite graphs. In particular, the asymptotic entropy of random walks on directed covers of finite graphs is positive if and only if the random walk is transient.     

Harmonic deformation of Delaunay triangulations

We construct harmonic functions on random graphs given by Delaunay triangulations of ergodic point processes as the limit of the zero-temperature harness process.     

On the Choice of Nugget in Kriging Modeling for Deterministic Computer Experiments

Kriging is commonly used for developing emulators as surrogates for computationally intensive simulations. One difficulty with kriging is the potential numerical instability in the computation of the inverse of the covariance matrix, which can lead to large variability and poor performance of the kriging predictor. First, we study some causes of ill-conditioning in kriging. We then study the use of nugget in kriging to overcome the numerical instability. Some asymptotic results on its interpolation bias and mean squared prediction errors are presented. Finally, we study the choice of the nugget parameter based on some algebraic lower bounds and use of a regularizing trace. A simulation study is performed to show the differences between kriging with and without nugget and to demonstrate the advantages of the former. This article has supplementary materials online.     

A gentle introduction to the differential equation method and dynamic concentration

We discuss the differential equation method for establishing dynamic concentration of discrete random processes. We present several relatively simple examples of it and aim to make the method understandable to the unfamiliar reader who has some basic knowledge on probabilistic methods, random graphs and differential equations.     

Connectivity of a general class of inhomogeneous random digraphs

We study a family of directed random graphs whose arcs are sampled independently of each other, and are present in the graph with a probability that depends on the attributes of the vertices involved. In particular, this family of models includes as special cases the directed versions of the Erd?s‐Rényi model, graphs with given expected degrees, the generalized random graph, and the Poissonian random graph. We establish a phase transition for the existence of a giant strongly connected component and provide some other basic properties, including the limiting joint distribution of the degrees and the mean number of arcs. In particular, we show that by choosing the joint distribution of the vertex attributes according to a multivariate regularly varying distribution, one can obtain scale‐free graphs with arbitrary in‐degree/out‐degree dependence.     

Moderate Deviations via Cumulants

The purpose of the present paper is to establish moderate deviation principles for a rather general class of random variables fulfilling certain bounds of the cumulants. We apply a celebrated lemma of the theory of large deviations probabilities due to Rudzkis, Saulis, and Statulevi?ius. The examples of random objects we treat include dependency graphs, subgraph-counting statistics in Erdös–Rényi random graphs and U-statistics. Moreover, we prove moderate deviation principles for certain statistics appearing in random matrix theory, namely characteristic polynomials of random unitary matrices and the number of particles in a growing box of random determinantal point processes such as the number of eigenvalues in the GUE or the number of points in Airy, Bessel, and sine random point fields.     

Geometry of the vacant set left by random walk on random graphs,Wright's constants,and critical random graphs with prescribed degrees

We provide an explicit algorithm for sampling a uniform simple connected random graph with a given degree sequence. By products of this central result include: (1) continuum scaling limits of uniform simple connected graphs with given degree sequence and asymptotics for the number of simple connected graphs with given degree sequence under some regularity conditions, and (2) scaling limits for the metric space structure of the maximal components in the critical regime of both the configuration model and the uniform simple random graph model with prescribed degree sequence under finite third moment assumption on the degree sequence. As a substantive application we answer a question raised by ?erný and Teixeira study by obtaining the metric space scaling limit of maximal components in the vacant set left by random walks on random regular graphs.     

Extreme values of the stationary distribution of random walks on directed graphs

We examine the stationary distribution of random walks on directed graphs. In particular, we focus on the principal ratio, which is the ratio of maximum to minimum values of vertices in the stationary distribution. We give an upper bound for this ratio over all strongly connected graphs on n vertices. We characterize all graphs achieving the upper bound and we give explicit constructions for these extremal graphs. Additionally, we show that under certain conditions, the principal ratio is tightly bounded. We also provide counterexamples to show the principal ratio cannot be tightly bounded under weaker conditions.     

The product representation of a locally dependent random graph

Directed graphs with random black and white colourings of edges such that the colours of edges from different vertices are mutually independent are called locally dependent random graphs. Two random graphs are equivalent if they cannot be distinguished from percolation processes on them if only the vertices are seen. A necessary and sufficient condition is given for when a locally dependent random graph is equivalent to a product random graph; that is one in which the edges can be grouped in such a way that within each group the colours of the edges are equivalent and between groups they are independent. As an application the random graph corresponding to a spatial general epidemic model is considered.     

Topology discovery of sparse random graphs with few participants

We consider the task of topology discovery of sparse random graphs using end‐to‐end random measurements (e.g., delay) between a subset of nodes, referred to as the participants. The rest of the nodes are hidden, and do not provide any information for topology discovery. We consider topology discovery under two routing models: (a) the participants exchange messages along the shortest paths and obtain end‐to‐end measurements, and (b) additionally, the participants exchange messages along the second shortest path. For scenario (a), our proposed algorithm results in a sub‐linear edit‐distance guarantee using a sub‐linear number of uniformly selected participants. For scenario (b), we obtain a much stronger result, and show that we can achieve consistent reconstruction when a sub‐linear number of uniformly selected nodes participate. This implies that accurate discovery of sparse random graphs is tractable using an extremely small number of participants. We finally obtain a lower bound on the number of participants required by any algorithm to reconstruct the original random graph up to a given edit distance. We also demonstrate that while consistent discovery is tractable for sparse random graphs using a small number of participants, in general, there are graphs which cannot be discovered by any algorithm even with a significant number of participants, and with the availability of end‐to‐end information along all the paths between the participants. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Multiple cover time

Motivated by applications in Markov estimation and distributed computing, we define the blanket time of an undirected graph G to be the expected time for a random walk to hit every vertex of G within a constant factor of the number of times predicted by the stationary distribution. Thus the blanket time is, essentially, the number of steps required of a random walk in order that the observed distribution reflect the stationary distribution. We provide substantial evidence for the following conjecture: that the blanket time of a graph never exceeds the cover time by more than a constant factor. In other words, at the cost of a multiplicative constant one can hit every vertex often instead of merely once. We prove the conjecture in the case where the cover time and maximum hitting time differ by a logarithmic factor. This case includes almost all graphs, as well as most “natural” graphs: the hypercube, k-dimensional lattices for k ≥ 2, balanced k-ary trees, and expanders. We further prove the conjecture for perhaps the most natural graphs not falling in the above case: paths and cycles. Finally, we prove the conjecture in the case of independent stochastic processes. © 1996 John Wiley & Sons, Inc. Random Struct. Alg., 9 , 403–411 (1996)     

Prediction and Inference for Truncated Spatial Data

Abstract

Spatial data in mining, hydrology, and pollution monitoring commonly have a substantial proportion of zeros. One way to model such data is to suppose that some pointwise transformation of the observations follows the law of a truncated Gaussian random field. This article considers Monte Carlo methods for prediction and inference problems based on this model. In particular, a method for computing the conditional distribution of the random field at an unobserved location, given the data, is described. These results are compared to those obtained by simple kriging and indicator cokriging. Simple kriging is shown to give highly misleading results about conditional distributions; indicator cokriging does quite a bit better but still can give answers that are substantially different from the conditional distributions. A slight modification of this basic technique is developed for calculating the likelihood function for such models, which provides a method for computing maximum likelihood estimates of unknown parameters and Bayesian predictive distributions for values of the process at unobserved locations.     

Greedy maximal independent sets via local limits

The random greedy algorithm for finding a maximal independent set in a graph constructs a maximal independent set by inspecting the graph's vertices in a random order, adding the current vertex to the independent set if it is not adjacent to any previously added vertex. In this paper, we present a general framework for computing the asymptotic density of the random greedy independent set for sequences of (possibly random) graphs by employing a notion of local convergence. We use this framework to give straightforward proofs for results on previously studied families of graphs, like paths and binomial random graphs, and to study new ones, like random trees and sparse random planar graphs. We conclude by analysing the random greedy algorithm more closely when the base graph is a tree.     

Coalescent random walks on graphs

Inspired by coalescent theory in biology, we introduce a stochastic model called “multi-person simple random walks” or “coalescent random walks” on a graph G. There are any finite number of persons distributed randomly at the vertices of G. In each step of this discrete time Markov chain, we randomly pick up a person and move it to a random adjacent vertex. To study this model, we introduce the tensor powers of graphs and the tensor products of Markov processes. Then the coalescent random walk on graph G becomes the simple random walk on a tensor power of G. We give estimates of expected number of steps for these persons to meet all together at a specific vertex. For regular graphs, our estimates are exact.     

Random Latin square graphs

In this paper we introduce new models of random graphs, arising from Latin squares which include random Cayley graphs as a special case. We investigate some properties of these graphs including their clique, independence and chromatic numbers, their expansion properties as well as their connectivity and Hamiltonicity. The results obtained are compared with other models of random graphs and several similarities and differences are pointed out. For many properties our results for the general case are as strong as the known results for random Cayley graphs and sometimes improve the previously best results for the Cayley case. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011