More Randomness of Environment Does Not Always Slow Down a Random Walk

We consider a random walk on in a stationary and ergodic random environment, whose states are called types of the vertices of . We find conditions for which the speed of the random walk is positive. In the case of a Markov chain environment with finitely many states, we give an explicit formula for the speed and for the asymptotic proportion of time spent at vertices of a certain type. Using these results, we compare the speed of random walks on in environments of varying randomness.     

Second-Order Subexponential Behavior of Subordinated Sequences

Suppose that , , and are three discrete probability distributions related by the equation (E): , where denotes the k-fold convolution of In this paper, we investigate the relation between the asymptotic behaviors of and . It turns out that, for wide classes of sequences and , relation (E) implies that , where is the mean of . The main object of this paper is to discuss the rate of convergence in this result. In our main results, we obtain O-estimates and exact asymptotic estimates for the difference .     

Packing Measure and Dimension of Random Fractals

We consider random fractals generated by random recursive constructions. We prove that the box-counting and packing dimensions of these random fractals, K, equals , their almost sure Hausdorff dimension. We show that some almost deterministic conditions known to ensure that the Hausdorff measure satisfies also imply that the packing measure satisfies 0< . When these conditions are not satisfied, it is known . Correspondingly, we show that in this case , provided a random strong open set condition is satisfied. We also find gauge functions (t) so that the -packing measure is finite.     

Gibbs Measures and Markov Random Fields with Association $$I $$

We introduce the notions of a Gibbs measure with the corresponding potential with association (where is a subset of the set ) of a Markov random field with memory and measure with association . It is proved that these three notions are equivalent.     

The Eigenvalues of Very Sparse Random Symmetric Matrices

Let W _n be an n × n random symmetric sparse matrix with independent identically distributed entries such that the values 1 and 0 are taken with probabilities p/n and 1-p/n, respectively; here is independent of n. We show that the limit of the expected spectral distribution functions of W _n has a discrete part. Moreover, the set of positive probability points is dense in (- +). In particular, the points , and 0 belong to this set.     

Estimates for the Distributions of the Sums of Subexponential Random Variables

Let be a random walk with independent identically distributed increments . We study the ratios of the probabilities P(S _n >x) / P(₁ > x) for all n and x. For some subclasses of subexponential distributions we find upper estimates uniform in x for the ratios which improve the available estimates for the whole class of subexponential distributions. We give some conditions sufficient for the asymptotic equivalence P(S > x) E P(₁ > x) as x . Here is a positive integer-valued random variable independent of . The estimates obtained are also used to find the asymptotics of the tail distribution of the maximum of a random walk modulated by a regenerative process.     

Time-Localization of Random Distributions on Wiener Space

A nuclear space of distributions on Wiener space was constructed by Gorostiza and Nualart [10] as a framework for studying weak convergence of trajectorial fluctuations of particle systems. A basic problem in recovering the usual time-evolution results from the trajectorial ones consists in associating in a unique way an -valued process to a random distribution on by localizing it at each time t [0,1]. In this paper we solve this problem for a large class of random distributions which includes trajectorial fluctuation limits of some systems of diffusions.     

Selective Limit Theorems for Random Walks on Parabolic Biangle and Triangle Hypergroups

Let K be respectively the parabolic biangle and the triangle in and be a sequence in [0, +[ such that lim_p (p)=+. According to Koornwinder and Schwartz,⁽⁷⁾ for each there exist a convolution structure (*_(p)) such that (K, *_(p)) is a commutative hypergroup. Consider now a random walk on (K, *_(p)), assume that this random walk is stopped after j(p) steps. Then under certain conditions given below we prove that the random variables on K admit a selective limit theorems. The proofs depend on limit relations between the characters of these hypergroups and Laguerre polynomials that we give in this work.     

RUC-Bases in Orlicz and Lorentz Operator Spaces

If is an RUC-basis in somecouple of non-commutative L _p-spaces, then is an RUC-basic sequence in any non-commutative Orlicz or Lorentz space which is an interpolation space for this couple.     

Dynamic ℤ d -Random Walks in a Random Scenery: A Strong Law of Large Numbers

In this paper, we study a _d -random walk on nearest neighbours with transition probabilities generated by a dynamical system . We prove, at first, that under some hypotheses, verifies a local limit theorem. Then, we study these walks in a random scenery , a sequence of independent, identically distributed and centred random variables and show that for certain dynamic random walks, satisfies a strong law of large numbers.     

Large Deviations for Sums of Independent Heavy-Tailed Random Variables

We obtain precise large deviations for heavy-tailed random sums , of independent random variables. are nonnegative integer-valued random variables independent of r.v. (X _i )i N with distribution functions F _i. We assume that the average of right tails of distribution functions F _i is equivalent to some distribution function with regularly varying tail. An example with the Pareto law as the limit function is given.     

Large deviations for trajectories of sums of independent random variables

Given a sequence of independent, but not necessarily identically distributed random variables,Y _i , letS _k denote thekth partial sum. Define a function by taking to be the piecewise linear interpolant of the points (k, S _k ), evaluated att, whereS ₀=0, andk=0, 1, 2,... Fort[0, 1], let . The are called trajectories. With regularity and moment conditions on theY _i , a large deviation principle is proved for the .     

On Universal Representation of Random Graphs

It is shown that every probability measure on the interval [0, 1] gives rise to a unique infinite random graph g on vertices {v₁, v₂, . . .} and a sequence of random graphs gn on vertices {v₁, . . . , v_n} such that . In particular, for Bernoulli graphs with stable property Q, can be strengthened to: probability space (, F, P), set of infinite graphs G(Q) , F with property Q such that .AMS Subject Classification: 05C80, 05C62.     

Symmetric Distributions of Random Measures in Higher Dimensions

An infinite sequence of random variables X=(X ₁, X ₂,...) is said to be spreadable if all subsequences of X have the same distribution. Ryll-Nardzewski showed that X is spreadable iff it is exchangeable. This result has been generalized to various discrete parameter and higher dimensional settings. In this paper we show that a random measure on the tetrahedral space is spreadable, iff it can be extended to an exchangeable random measure on . The result is a continuous parameter version of a theorem by Kallenberg.     

On Large Deviations of Vector-Valued Additive Functions of a Markov Gaussian Field

We prove a local limit theorem for large deviations of the sums , where , is a Markov Gaussian random field, is a bounded vector-valued function, and . This paper generalizes the paper [13].     

Hiding Cliques for Cryptographic Security

We demonstrate how a well studied combinatorial optimizationproblem may be used as a new cryptographic primitive. The problemin question is that of finding a "large" clique in a randomgraph. While the largest clique in a random graph with nvertices and edge probability p is very likely tobe of size about , it is widely conjecturedthat no polynomial-time algorithm exists which finds a cliqueof size with significantprobability for any constant > 0. We presenta very simple method of exploiting this conjecture by hidinglarge cliques in random graphs. In particular, we show that ifthe conjecture is true, then when a large clique—of size,say, is randomlyinserted (hidden) in a random graph, finding a clique ofsize remains hard.Our analysis also covers the case of high edge probabilitieswhich allows us to insert cliques of size up to . Our result suggests several cryptographicapplications, such as a simple one-way function.     

The Minimal Subgroup of a Random Walk

It is proved that for each random walk (S _n ) _n0 on ^d there exists a smallest measurable subgroup of ^d , called minimal subgroup of (S _n ) _n0, such that P(S _n )=1 for all n1. can be defined as the set of all x ^d for which the difference of the time averages n ^{–1 n} _k=1 P(S _k ) and n ^{–1 n} _k=1 P(S _k +x) converges to 0 in total variation norm as n. The related subgroup * consisting of all x ^d for which lim _n P(S _n )–P(S _n +x)=0 is also considered and shown to be the minimal subgroup of the symmetrization of (S _n ) _n0. In the final section we consider quasi-invariance and admissible shifts of probability measures on ^d . The main result shows that, up to regular linear transformations, the only subgroups of ^d admitting a quasi-invariant measure are those of the form ₁×...× _k × ^l–k ×{0} ^d–l , 0kld, with ₁,..., _k being countable subgroups of . The proof is based on a result recently proved by Kharazishvili⁽³⁾ which states no uncountable proper subgroup of admits a quasi-invariant measure.     

Markov Chains on Graphs and Brownian Motion

We consider random walks with small fixed steps inside of edges of a graph , prescribing a natural rule of probabilities of jumps over a vertex. We show that after an appropriate rescaling such random walks weakly converge to the natural Brownian motion on constructed in Ref. 1.     

Divergence of a Random Walk Through Deterministic and Random Subsequences

Let {S _n} _n0 be a random walk on the line. We give criteria for the existence of a nonrandom sequence n _i for which respectively We thereby obtain conditions for to be a strong limit point of {S _n} or {S _n /n}. The first of these properties is shown to be equivalent to for some sequence a _i , where T(a) is the exit time from the interval [–a,a]. We also obtain a general equivalence between and for an increasing function fand suitable sequences n _i and a _i. These sorts of properties are of interest in sequential analysis. Known conditions for and (divergence through the whole sequence n) are also simplified.     

Geometry of \mathbb{Z}^d and the Central Limit Theorem for Weakly Dependent Random Fields

We study the asymptotic distribution of where A is a subset of , A _N = A[–N, N] ^d , v(A) = lim _N card(A _N) (2N+1) ^–d (0, 1) and X is a stationary weakly dependent random field. We show that the geometry of A has a relevant influence on the problem. More specifically, S _N(A, X) is asymptotically normal for each X that satisfies certain mixting hypotheses if and only if has a limit F(n; A) as N for each . We also study the class of sets A that satisfy this condition.