Non-intersecting paths, random tilings and random matrices

 We investigate certain measures induced by families of non-intersecting paths in domino tilings of the Aztec diamond, rhombus tilings of an abc-hexagon, a dimer model on a cylindrical brick lattice and a growth model. The measures obtained, e.g. the Krawtchouk and Hahn ensembles, have the same structure as the eigenvalue measures in random matrix theory like GUE, which can in fact can be obtained from non-intersecting Brownian motions. The derivations of the measures are based on the Karlin-McGregor or Lindstr?m-Gessel-Viennot method. We use the measures to show some asymptotic results for the models. Received: 1 December 2000 / Revised version: 20 May 2001 / Published online: 17 May 2002     

Imprecise random variables,random sets,and Monte Carlo simulation

The paper addresses the evaluation of upper and lower probabilities induced by functions of an imprecise random variable. Given a function g and a family $X_{\lambda }$ of random variables, where the parameter λ ranges in an index set Λ, one may ask for the upper/lower probability that $g(X_{\lambda })$ belongs to some Borel set B. Two interpretations are investigated. In the first case, the upper probability is computed as the supremum of the probabilities that $g(X_{\lambda })$ lies in B. In the second case, one considers the random set generated by all $g(X_{\lambda })$, $\lambda \in \mathrm{\Lambda }$, e.g. by transforming $X_{\lambda }$ to standard normal as a common probability space, and computes the corresponding upper probability. The two results are different, in general. We analyze this situation and highlight the implications for Monte Carlo simulation. Attention is given to efficient simulation procedures and an engineering application is presented.     

Random weighted projections,random quadratic forms and random eigenvectors

We present a concentration result concerning random weighted projections in high dimensional spaces. As applications, we prove (1) New concentration inequalities for random quadratic forms. (2) The infinity norm of most unit eigenvectors of a random ±1 matrix is of order . (3) An estimate on the threshold for the local semi‐circle law which is tight up to a factor. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 792–821, 2015     

On MAXCUT in strictly supercritical random graphs,and coloring of random graphs and random tournaments

We use a theorem by Ding, Lubetzky, and Peres describing the structure of the giant component of random graphs in the strictly supercritical regime, in order to determine the typical size of MAXCUT of in terms of ɛ. We then apply this result to prove the following conjecture by Frieze and Pegden. For every , there exists such that w.h.p. is not homomorphic to the cycle on vertices. We also consider the coloring properties of biased random tournaments. A p‐random tournament on n vertices is obtained from the transitive tournament by reversing each edge independently with probability p. We show that for the chromatic number of a p‐random tournament behaves similarly to that of a random graph with the same edge probability. To treat the case we use the aforementioned result on MAXCUT and show that in fact w.h.p. one needs to reverse edges to make it 2‐colorable.     

Pathwidth, trees, and random embeddings

We prove that, for every integer k≥1, every shortest-path metric on a graph of pathwidth k embeds into a distribution over random trees with distortion at most c=c(k), independent of the graph size. A well-known conjecture of Gupta, Newman, Rabinovich, and Sinclair [12] states that for every minor-closed family of graphs F, there is a constant c(F) such that the multi-commodity max-flow/min-cut gap for every flow instance on a graph from F is at most c(F). The preceding embedding theorem is used to prove this conjecture whenever the family F does not contain all trees.     

Storage problems in continuous time with random inputs,random outputs,and deterministic release

The subject of study here is the model of a dam, with random inputs and outputs along with a deterministic release. The amounts of the Poisson jumps, either up or down, are independently and identically distributed. Closed form solutions are obtained for the Laplace transforms of first passage densities to different situations of overflow or emptiness. These results can throw insights regarding different threshold studies in storage, inventory, biological, and environmental problems. The closed form solutions are obtained by applying imbedding methods for different types of densities conceptualized in novel ways.     

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.     

Rectangular random matrices, related convolution

We characterize asymptotic collective behavior of rectangular random matrices, the sizes of which tend to infinity at different rates. It appears that one can compute the limits of all noncommutative moments (thus all spectral properties) of the random matrices we consider because, when embedded in a space of larger square matrices, independent rectangular random matrices are asymptotically free with amalgamation over a subalgebra. Therefore, we can define a “rectangular-free convolution”, which allows to deduce the singular values of the sum of two large independent rectangular random matrices from the individual singular values. This convolution is linearized by cumulants and by an analytic integral transform, that we called the “rectangular R-transform”.     

Sobolev spaces, dimension, and random series

We investigate dimension-increasing properties of maps in Sobolev spaces; we obtain sharp results with a random process somewhat like Brownian motion.

     

Extending simulation uses of antithetic variables: partially monotone functions, random permutations, and random subsets

We show how to effectively use antithetic variables to evaluate the expected value of (a) functions of independent random variables, when the functions are monotonic in only some of their variables, (b) Schur functions of random permutations, and (c) monotone functions of random subsets.     

The critical random graph,with martingales

We give a short proof that the largest component C ₁ of the random graph G(n, 1/n) is of size approximately n ^2/3. The proof gives explicit bounds for the probability that the ratio is very large or very small. In particular, the probability that n ^−2/3|C ₁| exceeds A is at most e ^{- cA3}{e^{ - c{A^3}}} for some c > 0.     

The multitype branching random walk, II

Limit theorems for the multitype branching random walk as n → ∞ are given (n is the generation number) in the case in which the branching process has a mean matrix which is not positive regular. In particular, the existence of steady state distributions is proven in the subcritical case with immigration, and in the critical case with initial Poisson random fields of particles. In the supercritical case, analogues of the limit theorems of Kesten and Stigum are given.     

Form factors,plane partitions,and random walks

An exactly solvable boson model, the so-called “phase model,” is considered. A relation between certain transition matrix elements of this model and boxed plane partitions, three-dimensional Young diagrams placed into a box of finite size, is established, It is shown that the natural model describing the behavior of friendly walkers, ones that can share the same lattice sites, is the “phase model.” An expression for the number of all admissible nests of lattice paths made by a fixed number of friendly walkers for a certain number of steps is obtained. Bibliography 35 titles. Published in Zapiski Nauchnykh Seminarov POMI, Vol. 360, 2008, pp. 5–30.     

Colorings of spaces,and random graphs

This work deals with some problems on the embeddings of finite geometric graphs into the random ones. In particular, we study here applications of the random graph theory to the Nelson-Erdös-Hadwiger problem on coloring spaces.     

Counting measures,monotone random set functions

Summary This paper arose from work on random processes whose values are measures or more general set functions. Secs. 1–3, which have nothing specifically random, discuss two topologies for certain sigma-finite measures. One, applicable only to counting measures, is a quotient topology which is useful in the finite case but excessively weak in the infinite case. Making use of a well-known result of P. Hall on sets of representatives, we describe this topology and show that it can be enlarged to the stronger one generated by a modification of the Lévy-Prohorov (L-P) metric. Sec. 4 gives a property of the L-P metric for finite integer valued counting measures. The rest of the paper deals with a random monotone non-negative set function in a separable metric space X. If X is complete and if is subadditive and right continuous¹ in probability on certain classes of sets, we show the existence of a version of with right-continuous sample functions. If X is locally compact and is left continuous in probability on a certain class of open sets, there is a left-continuous version. With appropriate additional assumptions, we obtain versions that are measures or capacities. In the latter case, a 0–1 valued set function represents a random closed or compact set. The form of integer-valued strongly subadditive set functions is described for certain cases.Supported in part by National Science Foundation Grant GP-6216