Discrete random bounds for general random variables and applications to reliability

We here propose some new algorithms to compute bounds for (1) cumulative density functions of sums of i.i.d. nonnegative random variables, (2) renewal functions and (3) cumulative density functions of geometric sums of i.i.d. nonnegative random variables. The idea is very basic and consists in bounding any general nonnegative random variable X   by two discrete random variables with range in hN$h\mathbb{N}$, which both converge to X as h goes to 0. Numerical experiments are lead on and the results given by the different algorithms are compared to theoretical results in case of i.i.d. exponentially distributed random variables and to other numerical methods in other cases.     

Effective multipoles in random media

Abstract

In a homogeneous medium, the far field generated by a localized source can be expanded in terms of multipoles; the coefficients are determined by the moments of the localized charge distribution. We show that this structure survives to some extent for a random medium in the sense of quantitative stochastic homogenization: In three space dimensions, the effective dipole and quadrupole – but not the octupole – can be inferred without knowing the realization of the random medium far away from the (overall neutral) source and the point of interest. Mathematically, this is achieved by using the two-scale expansion to higher order to construct isomorphisms between the hetero- and homogeneous versions of spaces of harmonic functions that grow at a certain rate, or decay at a certain rate away from the singularity (near the origin); these isomorphisms crucially respect the natural pairing between growing and decaying harmonic functions given by the second Green’s formula. This not only yields effective multipoles (the quotient of the spaces of decaying functions) but also intrinsic moments (taken with respect to the elements of the spaces of growing functions). The construction of these rigid isomorphisms relies on a good (and dimension-dependent) control on the higher-order correctors and their flux potentials.     

On the deviation between the distributions of sums and maximum sums of IID random vectors

Summary For a sequence of independent and identically distributed random vectors, with finite moment of order less than or equal to the second, the rate at which the deviation between the distribution functions of the vectors of partial sums and maximums of partial sums is obtained both when the sample size is fixed and when it is random, satisfying certain regularity conditions. When the second moments exist the rate is of ordern ^−1/4 (in the fixed sample size case). Two applications are given, first, we compliment some recent work of Ahmad (1979,J. Multivariate Anal.,9, 214–222) on rates of convergence for the vector of maximum sums and second, we obtain rates of convergence of the concentration functions of maximum sums for both the fixed and random sample size cases.     

Markov random fields and gibbs random fields

Spitzer has shown that every Markov random field (MRF) is a Gibbs random field (GRF) and vice versa when (i) both are translation invariant, (ii) the MRF is of first order, and (iii) the GRF is defined by a binary, nearest neighbor potential. In both cases, the field (iv) is defined onZ ^v, and (v) at anyxεZ^v, takes on one of two states. The current paper shows that a MRF is a GRF and vice versa even when (i)−(v) are relaxed, i.e., even if one relaxes translation invariance, replaces first order bykth order, allows for many states and replaces finite domains of Z^v by arbitrary finite sets. This is achieved at the expense of using a many body rather than a pair potential, which turns out to be natural even in the classical (nearest neighbor) case when Z^v is replaced by a triangular lattice. The contents of this paper were presented in August, 1971, at a seminar of the Battelle Rencontre in Statistical Mechanics and also at a pair of seminars in December, 1971, at the Weizmann Institute of Science. Partially supported by NSF GP 7469 and a Weizmann Institute senior fellowship while on sabbatical leave from Indiana University.     

The characteristic polynomial of a random permutation matrix at different points

We consider the logarithm of the characteristic polynomial of random permutation matrices, evaluated on a finite set of different points. The permutations are chosen with respect to the Ewens distribution on the symmetric group. We show that the behavior at different points is independent in the limit and are asymptotically normal. Our methods enable us to study also the wreath product of permutation matrices and diagonal matrices with i.i.d. entries and more general class functions on the symmetric group with a multiplicative structure.     

The equivalence between processor sharing and service in random order

In this note we explore a useful equivalence relation for the delay distribution in the G/M/1 queue under two different service disciplines: (i) processor sharing (PS); and (ii) random order of service (ROS). We provide a direct probabilistic argument to show that the sojourn time under PS is equal (in distribution) to the waiting time under ROS of a customer arriving to a non-empty system. We thus conclude that the sojourn time distribution for PS is related to the waiting-time distribution for ROS through a simple multiplicative factor, which corresponds to the probability of a non-empty system at an arrival instant. We verify that previously derived expressions for the sojourn time distribution in the M/M/1 PS queue and the waiting-time distribution in the M/M/1 ROS queue are indeed identical, up to a multiplicative constant. The probabilistic nature of the argument enables us to extend the equivalence result to more general models, such as the M/M/1/K queue and ·/M/1 nodes in product-form networks.     

Distributional chaos in random dynamical systems

In this paper, we introduce the notion of distributional chaos and the measure of chaos for random dynamical systems generated by two interval maps. We give some sufficient conditions for a zero measure of chaos and examples of chaotic systems. We demonstrate that the chaoticity of the functions that generate a system does not, in general, affect the chaoticity of the system, i.e. a chaotic system can arise from two nonchaotic functions and vice versa. Finally, we show that distributional chaos for random dynamical system is, in some sense, unstable.     

On testing equality of pairwise rank correlations in a multivariate random vector

Spearman’s rank-correlation coefficient (also called Spearman’s rho) represents one of the best-known measures to quantify the degree of dependence between two random variables. As a copula-based dependence measure, it is invariant with respect to the distribution’s univariate marginal distribution functions. In this paper, we consider statistical tests for the hypothesis that all pairwise Spearman’s rank correlation coefficients in a multivariate random vector are equal. The tests are nonparametric and their asymptotic distributions are derived based on the asymptotic behavior of the empirical copula process. Only weak assumptions on the distribution function, such as continuity of the marginal distributions and continuous partial differentiability of the copula, are required for obtaining the results. A nonparametric bootstrap method is suggested for either estimating unknown parameters of the test statistics or for determining the associated critical values. We present a simulation study in order to investigate the power of the proposed tests. The results are compared to a classical parametric test for equal pairwise Pearson’s correlation coefficients in a multivariate random vector. The general setting also allows the derivation of a test for stochastic independence based on Spearman’s rho.     

Annealed deviations of random walk in random scenery

Let (Zn)_n∈N be a d-dimensional random walk in random scenery, i.e., with (Sk)_k∈N0 a random walk in Zd and (Y(z))_z∈Zd an i.i.d. scenery, independent of the walk. The walker's steps have mean zero and some finite exponential moments. We identify the speed and the rate of the logarithmic decay of for various choices of sequences n(bn) in [1,∞). Depending on n(bn) and the upper tails of the scenery, we identify different regimes for the speed of decay and different variational formulas for the rate functions. In contrast to recent work [A. Asselah, F. Castell, Large deviations for Brownian motion in a random scenery, Probab. Theory Related Fields 126 (2003) 497-527] by A. Asselah and F. Castell, we consider sceneries unbounded to infinity. It turns out that there are interesting connections to large deviation properties of self-intersections of the walk, which have been studied recently by X. Chen [X. Chen, Exponential asymptotics and law of the iterated logarithm for intersection local times of random walks, Ann. Probab. 32 (4) 2004].     

Asymptotic direction for random walks in random environments

In this paper we study the existence of an asymptotic direction for random walks in random i.i.d. environments (RWRE). We prove that if the set of directions where the walk is transient contains a non-empty open set, the walk admits an asymptotic direction. The main tool to obtain this result is the construction of a renewal structure with cones. We also prove that RWRE admits at most two opposite asymptotic directions.     

Quenched point-to-point free energy for random walks in random potentials

We consider a random walk in a random potential on a square lattice of arbitrary dimension. The potential is a function of an ergodic environment and steps of the walk. The potential is subject to a moment assumption whose strictness is tied to the mixing of the environment, the best case being the i.i.d. environment. We prove that the infinite volume quenched point-to-point free energy exists and has a variational formula in terms of entropy. We establish regularity properties of the point-to-point free energy, and link it to the infinite volume point-to-line free energy and quenched large deviations of the walk. One corollary is a quenched large deviation principle for random walk in an ergodic random environment, with a continuous rate function.     

Polar sets for anisotropic Gaussian random fields

This paper studies polar sets for anisotropic Gaussian random fields, i.e. sets which a Gaussian random field does not hit almost surely. The main assumptions are that the eigenvalues of the covariance matrix are bounded from below and that the canonical metric associated with the Gaussian random field is dominated by an anisotropic metric. We deduce an upper bound for the hitting probabilities and conclude that sets with small Hausdorff dimension are polar. Moreover, the results allow for a translation of the Gaussian random field by a random field, that is independent of the Gaussian random field and whose sample functions are of bounded Hölder norm.     

Degeneracy condition for the optimal moment in the optimal stop problem for a functional of a skewed down random walk and its maximum

The paper presents a new class of functions dependent on a skewed down random walk and its maximum such that the optimal moment in the optimal stopping problem for this function on a finite time interval is trivial and equal to the beginning of the interval.     

Generating beta random rate variables from probabilistic estimates of fireline production times

An extension of probabilistic PERT/CPM is proposed as a framework for soliciting expert opinion to characterize random variables for stochastic treatment in simulation models. By eliciting minimum, modal, ninetieth percentile, and maximum estimates, the distribution of variables with probability density functions of beta form can be explicitly characterized without relying on the traditional, but empirically unverified, assumption of a standard deviation equal to one-sixth of the range. This practical and inexpensive technique is illustrated by application to a wildfire protection planning problem – estimating the time required to produce a given length of fireline by different firefighting resources under diverse conditions. The estimated production times are an essential input to a planning model of initial attack on wildland fires used by the California Department of Forestry and Fire Protection, and provide that agency with useful rules-of-thumb for use in firefighter training.     

Size of random Galois lattices and number of closed frequent itemsets

Given a sample of binary random vectors with i.i.d. Bernoulli(p) components, that is equal to 1 (resp. 0) with probability p (resp. 1−p), we first establish a formula for the mean of the size of the random Galois lattice built from this sample, and a more complex one for its variance. Then, noticing that closed α-frequent itemsets are in bijection with closed α-winning coalitions, we establish similar formulas for the mean and the variance of the number of closed α-frequent itemsets. This can be interesting for the study of the complexity of some data mining problems such as association rule mining, sequential pattern mining and classification.     

Hurwitz numbers and products of random matrices

We study multimatrix models, which may be viewed as integrals of products of tau functions depending on the eigenvalues of products of random matrices. We consider tau functions of the two-component Kadomtsev–Petviashvili (KP) hierarchy (semi-infinite relativistic Toda lattice) and of the B-type KP (BKP) hierarchy introduced by Kac and van de Leur. Such integrals are sometimes tau functions themselves. We consider models that generate Hurwitz numbers H^E,F, where E is the Euler characteristic of the base surface and F is the number of branch points. We show that in the case where the integrands contain the product of n > 2 matrices, the integral generates Hurwitz numbers with E ≤ 2 and F ≤ n+2. Both the numbers E and F depend both on n and on the order of the factors in the matrix product. The Euler characteristic E can be either an even or an odd number, i.e., it can match both orientable and nonorientable (Klein) base surfaces depending on the presence of the tau function of the BKP hierarchy in the integrand. We study two cases, the products of complex and the products of unitary matrices.     

Synchronization and functional central limit theorems for interacting reinforced random walks

We obtain Central Limit Theorems in Functional form for a class of time-inhomogeneous interacting random walks. Due to a reinforcement mechanism and interaction, the walks are strongly correlated and converge almost surely to the same, possibly random, limit. We study random walks interacting through a mean-field rule and compare the rate they converge to their limit with the rate of synchronization, i.e. the rate at which their mutual distances converge to zero. We show that, under certain conditions, synchronization is faster than convergence. Even if our focus is on theoretical results, we propose as main motivations two contexts in which such results could directly apply: urn models and opinion dynamics in a random network evolving via preferential attachment.     

Mittag-Leffler vector random fields with Mittag-Leffler direct and cross covariance functions

In terms of the two-parameter Mittag-Leffler function with specified parameters, this paper introduces the Mittag-Leffler vector random field through its finite-dimensional characteristic functions, which is essentially an elliptically contoured one and reduces to a Gaussian one when the two parameters of the Mittag-Leffler function equal 1. Having second-order moments, a Mittag-Leffler vector random field is characterized by its mean function and its covariance matrix function, just like a Gaussian one. In particular, we construct direct and cross covariances of Mittag-Leffler type for such vector random fields.     

The distribution of height and diameter in random non‐plane binary trees

This study is dedicated to precise distributional analyses of the height of non‐plane unlabelled binary trees (“Otter trees”), when trees of a given size are taken with equal likelihood. The height of a rooted tree of size n is proved to admit a limiting theta distribution, both in a central and local sense, and obey moderate as well as large deviations estimates. The approximations obtained for height also yield the limiting distribution of the diameter of unrooted trees. The proofs rely on a precise analysis, in the complex plane and near singularities, of generating functions associated with trees of bounded height. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2012