Exchangeable and partially exchangeable random partitions

Summary Call a random partition of the positive integerspartially exchangeable if for each finite sequence of positive integersn ₁,...,n _k, the probability that the partition breaks the firstn ₁+...+n_k integers intok particular classes, of sizesn ₁,...,n_k in order of their first elements, has the same valuep(n ₁,...,n_k) for every possible choice of classes subject to the sizes constraint. A random partition is exchangeable iff it is partially exchangeable for a symmetric functionp(n ₁,...n_k). A representation is given for partially exchangeable random partitions which provides a useful variation of Kingman's representation in the exchangeable case. Results are illustrated by the two-parameter generalization of Ewens' partition structure.Research supported by N.S.F. Grants MCS91-07531 and DMS-9404345     

Random walks in random environments without ellipticity

We consider random walks in random environments on Z^d${\mathbb{Z}}^d$. Under a transitivity hypothesis that is much weaker than the customary ellipticity condition, and assuming an absolutely continuous invariant measure on the space of the environments, we prove the ergodicity of the annealed process w.r.t. the dynamics “from the point of view of the particle”. This implies in particular that the environment viewed from the particle is ergodic. As an example of application of this result, we give a general form of the quenched Invariance Principle for walks in doubly stochastic environments with zero local drift (martingale condition).     

The asymptotic behaviour of lovász’ ϑ function for random graphs

We show that for a random graph Lovász’ ϑ function is of order √n.     

Heat-kernel estimates for random walk among random conductances with heavy tail

We study models of discrete-time, symmetric, Z^d${\mathbb{Z}}^d$-valued random walks in random environments, driven by a field of i.i.d. random nearest-neighbor conductances _ωxy∈[0,1]${\omega }_{xy}\in [0,1]$, with polynomial tail near 0 with exponent γ>0$\gamma >0$. We first prove for all d≥5$d\ge 5$ that the return probability shows an anomalous decay (non-Gaussian) that approaches (up to sub-polynomial terms) a random constant times n⁻²$n^{-2}$ when we push the power γ$\gamma$ to zero. In contrast, we prove that the heat-kernel decay is as close as we want, in a logarithmic sense, to the standard decay n^−d/2$n^{-d/2}$ for large values of the parameter γ$\gamma$.     

The Optimal Order for the p-th Moment of Sums of Independent Random Variables with Respect to Symmetric Norms and Related Combinatorial Estimates

For n independent random variables f₁, . . . ,f_n and a symmetric norm || ||_X on ℝⁿ, we show that for 1≤ p < ∞ Here is the disjoint sum of the f_i's and h* is the non-increasing rearrangement. Similar results (where L_p is replaced by a more general rearrangement invariant function space) were obtained first by Litvak, Gordon, Schütt and Werner for Orlicz spaces X and independently by S. Montgomery-Smith [22] for general X but without an explicit analysis of the order of growth for the constant in the upper estimate. The order is optimal and obtained from combinatorial estimates for doubly stochastic matrices. The result extends to Lorentz-norms l_{f, q} on ℝⁿ under mild assumptions on f. We give applications to the theory of noncommutative L_p spaces.     

Asymptotic laws for regenerative compositions: gamma subordinators and the like

For a random closed set obtained by exponential transformation of the closed range of a subordinator, a regenerative composition of generic positive integer n is defined by recording the sizes of clusters of n uniform random points as they are separated by the points of . We focus on the number of parts K_n of the composition when is derived from a gamma subordinator. We prove logarithmic asymptotics of the moments and central limit theorems for K_n and other functionals of the composition such as the number of singletons, doubletons, etc. This study complements our previous work on asymptotics of these functionals when the tail of the Lévy measure is regularly varying at 0+. Research supported in part by N.S.F. Grant DMS-0071448     

A local limit theorem for random walks conditioned to stay positive

We consider a real random walk S_n=X₁+...+X_n attracted (without centering) to the normal law: this means that for a suitable norming sequence a_n we have the weak convergence S_n/a_n⇒ϕ(x)dx, ϕ(x) being the standard normal density. A local refinement of this convergence is provided by Gnedenko's and Stone's Local Limit Theorems, in the lattice and nonlattice case respectively. Now let denote the event (S₁>0,...,S_n>0) and let S_n⁺ denote the random variable S_n conditioned on : it is known that S_n⁺/a_n ↠ ϕ⁺(x) dx, where ϕ⁺(x):=x exp (−x²/2)1_(x≥0). What we establish in this paper is an equivalent of Gnedenko's and Stone's Local Limit Theorems for this weak convergence. We also consider the particular case when X₁ has an absolutely continuous law: in this case the uniform convergence of the density of S_n⁺/a_n towards ϕ⁺(x) holds under a standard additional hypothesis, in analogy to the classical case. We finally discuss an application of our main results to the asymptotic behavior of the joint renewal measure of the ladder variables process. Unlike the classical proofs of the LLT, we make no use of characteristic functions: our techniques are rather taken from the so–called Fluctuation Theory for random walks.     

Distributional limit theorems in infinite ergodic theory

We present a unified approach to the Darling-Kac theorem and the arcsine laws for occupation times and waiting times for ergodic transformations preserving an infinite measure. Our method is based on control of the transfer operator up to the first entrance to a suitable reference set rather than on the full asymptotics of the operator. We illustrate our abstract results by showing that they easily apply to a significant class of infinite measure preserving interval maps. We also show that some of the tools introduced here are useful in the setup of pointwise dual ergodic transformations.     

Sandwiching random graphs: universality between random graph models

The goal of this paper is to establish a connection between two classical models of random graphs: the random graph G(n,p) and the random regular graph G_d(n). This connection appears to be very useful in deriving properties of one model from the other and explains why many graph invariants are universal. In particular, one obtains one-line proofs of several highly non-trivial and recent results on G_d(n).     

The nullity theorem for principal pivot transform

We generalize the nullity theorem of Gustafson (1984) [8] from matrix inversion to principal pivot transform. Several special cases of the obtained result are known in the literature, such as a result concerning local complementation on graphs. As an application, we show that a particular matrix polynomial, the so-called nullity polynomial, is invariant under principal pivot transform.     

Logarithmic speeds for one-dimensional perturbed random walks in random environments

We study the random walk in a random environment on Z⁺={0,1,2,…}${\mathbb{Z}}^{+}=\{0,1,2,\dots \}$, where the environment is subject to a vanishing (random) perturbation. The two particular cases that we consider are: (i) a random walk in a random environment perturbed from Sinai’s regime; (ii) a simple random walk with a random perturbation. We give almost sure results on how far the random walker is from the origin, for almost every environment. We give both upper and lower almost sure bounds. These bounds are of order (logt)^β${(logt)}^{\beta }$, for β∈(1,∞)$\beta \in (1,\infty )$, depending on the perturbation. In addition, in the ergodic cases, we give results on the rate of decay of the stationary distribution.     

Convergence of multi-class systems of fixed possibly infinite sizes

Multi-class systems having possibly both finite and infinite classes are investigated under a natural partial exchangeability assumption. It is proved that the conditional law of such a system, given the vector constituted by the empirical measures of its finite classes and the directing measures of its infinite ones (given by the de Finetti Theorem), corresponds to sampling independently from each class, without replacement from the finite classes and i.i.d. from the directing measure for the infinite ones. The equivalence between the convergence of multi-exchangeable systems with fixed class sizes and the convergence of the corresponding vectors of measures is then established.     

Complete convergence and Cesàro summation for i.i.d. random variables

Summary Various results generalizing summation methods for divergent series of real numbers to analogous results for independent, identically distributed random variables have appeared during the last two decades. The main result of this paper provides necessary and sufficient conditions for the complete convergence of the Cesàro means of i.i.d random variables.     

Loop-erased random walk on the Sierpinski gasket

In this paper the loop-erased random walk on the finite pre-Sierpiński gasket is studied. It is proved that the scaling limit exists and is a continuous process. It is also shown that the path of the limiting process is almost surely self-avoiding, while having Hausdorff dimension strictly greater than 1. The loop-erasing procedure proposed in this paper is formulated by erasing loops, in a sense, in descending order of size. It enables us to obtain exact recursion relations, making direct use of ‘self-similarity’ of a fractal structure, instead of the relation to the uniform spanning tree. This procedure is proved to be equivalent to the standard procedure of chronological loop-erasure.     

Strongly self-dual graphs

We present a class of graphs whose adjacency matrices are nonsingular with integral inverses, denoted h-graphs. If the h-graphs G and H with adjacency matrices M(G) and M(H) satisfy M(G)^-1=SM(H)S, where S is a signature matrix, we refer to H as the dual of G. The dual is a type of graph inverse. If the h-graph G is isomorphic to its dual via a particular isomorphism, we refer to G as strongly self-dual. We investigate the structural and spectral properties of strongly self-dual graphs, with a particular emphasis on identifying when such a graph has 1 as an eigenvalue.     

The shape of random tanglegrams

A tanglegram consists of two binary rooted trees with the same number of leaves and a perfect matching between the leaves of the trees. We show that the two halves of a random tanglegram essentially look like two independently chosen random plane binary trees. This fact is used to derive a number of results on the shape of random tanglegrams, including theorems on the number of cherries and generally occurrences of subtrees, the root branches, the number of automorphisms, and the height. For each of these, we obtain limiting probabilities or distributions. Finally, we investigate the number of matched cherries, for which the limiting distribution is identified as well.     

Nonparametric tests of independence between random vectors

A nonparametric test of the mutual independence between many numerical random vectors is proposed. This test is based on a characterization of mutual independence defined from probabilities of half-spaces in a combinatorial formula of Möbius. As such, it is a natural generalization of tests of independence between univariate random variables using the empirical distribution function. If the number of vectors is p and there are n observations, the test is defined from a collection of processes R_n,A, where A is a subset of {1,…,p} of cardinality |A|>1, which are asymptotically independent and Gaussian. Without the assumption that each vector is one-dimensional with a continuous cumulative distribution function, any test of independence cannot be distribution free. The critical values of the proposed test are thus computed with the bootstrap which is shown to be consistent. Another similar test, with the same asymptotic properties, for the serial independence of a multivariate stationary sequence is also proposed. The proposed test works when some or all of the marginal distributions are singular with respect to Lebesgue measure. Moreover, in singular cases described in Section 4, the test inherits useful invariance properties from the general affine invariance property.