Random walks supported on random points ofZ/nZ

Summary This paper considers random walks on the integers modn supported onk points and asks how long does it take for these walks to get close to uniformly distributed. Ifk is a constant, Greenhalgh showed that at least some constant timesn ^2/(k–1) steps are necessary to make the distance of the random walk from the uniform distribution small; here we show that ifn is prime, some constant timesn ^2/(k–1) steps suffice to make this distance small for almost all choices ofk points. The proof uses the Upper Bound Lemma of Diaconis and Shahshahani and some averaging techniques. This paper also explores some cases wherek varies withn. In particular, ifk=(logn) ^a , we find different kinds of results for different values ofa, and these results disprove a conjecture of Aldous and Diaconis.Research Supported in Part by a Rackham Faculty Fellowship at the University of Michigan     

Recurrent random walks in nonnegative matrices II

Summary In this paper, we continue the study undertaken in our earlier paper [M1]. One of the main results here can be described as follows. LetX ₀,X ₁, ... be a sequence of iid random affine maps from (R ⁺) ^d into itself. Let us write:W _n X _n X _n –1...X ₀ andZ _n X ₀ X ₁...X _n , where composition of maps is the rule of multiplication. By the attractorA(u),u(R ⁺) ^d , we mean the setA u={y(R⁺)^d:P(W_n uN i.o.) > 0 for every openN containingy}. It is shown that the attractorA(u), under mild conditions, is the support of a stationary probability measure, when the random walk (Z _n ) has at least one recurrent state.     

NILPOTENT GROUPS AND ABELIANIZATION

We study the question of what properties of nilpotent groups are shared by their abelianizations. We identify two such properties—that of being a π-torsion group, where π is a family of primes, and that of having q^th roots, for some prime q. We use these properties to provide simplified proofs of the following theorems in the localization of nilpotent groups.

Let H, K be subgroups of the nilpotent group N and let P be a family of primes. Then [H, K] P = [H_P, K_p]

Let the group G act on the nilpotent group N. Then G acts compatibly on N_p and (Γ^G _i N)_P = Γ^G _i(N_p).

The second theorem above is then applied to the study of the localization of relative groups, in the sense of [4].     

Blackwell's renewal theorem for certain linear submartingales and coupling

The present work surveys some extensions of Blackwell's renewal theorem for a certain class of linear submartingalesS which have been recently obtained by the author. The basic assumption onS is that their conditional increment distribution functions with respect to some filtration are bounded from above and below by integrable distribution functions. Under a further mean stability condition these random walks turn out to be natural candidates for satisfying Blackwell-type renewal theorems. The latter are derived by employing a coupling argument similar to that which has been used in the i.i.d. case by Lindvallet al. A number of applications are also presented.     

L 2-lower bounds for a special class of random walks

Summary We investigate theL ₂-speed of convergence to stationarity for a certain class of random walks on a compact connected Lie group. We give a lower bound on the number of stepsk necessary such that thek-fold convolution power of the original step distribution has anL ₂-density. Our method uses work by Heckman on the asymptotics of multiplicities along a ray of representations. Several examples are presented.This paper is based on parts of the author's doctoral dissertation written at The Johns Hopkins University     

Convergence rates in the strong laws of asymptotically negatively associated random fields

In this paper, a notion of negative side p-mixing (p -mixing) which can be regardedas asymptotic negative association is defined, and some Rosenthal type inequalities for p -mix-ing random fields are established. The complete convergence and almost sure summability onthe convergence rates with respect to the strong law of large numbers are also discussed for p--mixing random fields. The results obtained extend those for negatively associated sequences andp“ -mixing random fields.     

On the Gaussian approximation of vector-valued multiple integrals

By combining the findings of two recent, seminal papers by Nualart, Peccati and Tudor, we get that the convergence in law of any sequence of vector-valued multiple integrals F_n towards a centered Gaussian random vector N, with given covariance matrix C, is reduced to just the convergence of: (i) the fourth cumulant of each component of F_n to zero; (ii) the covariance matrix of F_n to C. The aim of this paper is to understand more deeply this somewhat surprising phenomenon. To reach this goal, we offer two results of a different nature. The first one is an explicit bound for d(F,N) in terms of the fourth cumulants of the components of F, when F is a R^d-valued random vector whose components are multiple integrals of possibly different orders, N is the Gaussian counterpart of F (that is, a Gaussian centered vector sharing the same covariance with F) and d stands for the Wasserstein distance. The second one is a new expression for the cumulants of F as above, from which it is easy to derive yet another proof of the previously quoted result by Nualart, Peccati and Tudor.     

An application of prophet regions to optimal stopping with a random number of observations

Let X ₁,X ₂ ,?…?be any sequence of nonnegative integrable random variables, and let N∈{1,2 , …} be a random variable with known distribution, independent of X ₁,X ₂ , …. The optimal stopping value sup _t E(X_t I(N≥ t)) is considered for two players: one who has advance knowledge of the value of N, and another who does not. Sharp ratio and difference inequalities relating the two players' optimal values are given in a number of settings. The key to the proofs is an application of a prophet region for arbitrarily dependent random variables by Hill and Kertz [T.P. Hill and R.P. Kertz (1983). Stop rule inequalities for uniformly bounded sequences of random variables. Trans. Amer. Math. Soc., 278, 197–207].     

Generalized Mehler semigroups and applications

Summary We construct and study generalized Mehler semigroups (p _t ) _t 0 and their associated Markov processesM. The construction methods for (p _t ) _t 0 are based on some new purely functional analytic results implying, in particular, that any strongly continuous semigroup on a Hilbert spaceH can be extended to some larger Hilbert spaceE, with the embeddingHE being Hilbert-Schmidt. The same analytic extension results are applied to construct strong solutions to stochastic differential equations of typedX _t =C dW _t +AX _t dt (with possibly unbounded linear operatorsA andC onH) on a suitably chosen larger spaceE. For Gaussian generalized Mehler semigroups (p _t ) _t 0 with corresponding Markov processM, the associated (non-symmetric) Dirichlet forms (E D(E)) are explicitly calculated and a necessary and sufficient condition for path regularity ofM in terms of (E,D(E)) is proved. Then, using Dirichlet form methods it is shown thatM weakly solves the above stochastic differential equation if the state spaceE is chosen appropriately. Finally, we discuss the differences between these two methods yielding strong resp. weak solutions.     

On the Remainder in an Asymptotic Expansion of the Double Gamma Function

We investigate the remainder R_N(z) in an asymptotic expansion of the logarithm of the double gamma function. We show that (−1)^NR_N(x) is a completely monotonic function.Research supported by the Carlsberg Foundation     

Tree-indexed random walks on groups and first passage percolation

Summary Suppose that i.i.d. random variables are attached to the edges of an infinite tree. When the tree is large enough, the partial sumsS along some of its infinite paths will exhibit behavior atypical for an ordinary random walk. This principle has appeared in works on branching random walks, first-passage percolation, and RWRE on trees. We establish further quantitative versions of this principle, which are applicable in these settings. In particular, different notions of speed for such a tree-indexed walk correspond to different dimension notions for trees. Finally, if the labeling variables take values in a group, then properties of the group (e.g., polynomial growth or a nontrivial Poisson boundary) are reflected in the sample-path behavior of the resulting tree-indexed walk.Partially supported by a grant from the Landau Center for Mathematical AnalysisPartially supported by NSF grant DMS-921 3595     

Order of magnitude bounds for expectations of Δ2-functions of generalized random bilinear forms

Let Φ be a symmetric function, nondecreasing on [0,∞) and satisfying a Δ₂ growth condition, (X ₁,Y ₁), (X ₂,Y ₂),…,(X _n ,Y _n ) be arbitrary independent random vectors such that for any given i either Y _i =X _i or Y _i is independent of all the other variates. The purpose of this paper is to develop an approximation of

Inequalities for sums of independent geometrical random variables

Summary We give a survey of known results regarding Schur-convexity of probability distribution functions. Then we prove that the functionF(p ₁,...,p_n;t)=P(X₁+...+X_n≤t) is Schur-concave with respect to (p ₁,...,p_n) for every realt, whereX _i are independent geometric random variables with parametersp _i. A generalization to negative binomial random variables is also presented.     

On the conjecture of hajós

Hajós conjectured that everys-chromatic graph contains a subdivision ofK _s, the complete graph ons vertices. Catlin disproved this conjecture. We prove that almost all graphs are counter-examles in a very strong sense.     

The generalized Banach match-box problem: Application in disc storage management

A computer system manages disc storage of finite capacity c blocks. This storage must be divided among N files in such a way that the expected number of disc accesses accomplished until the necessary reorganization is maximized. Each access to the disc appends a record of a fixed length to the ith file with probability p _i (i=1,h., N). The reorganization is needed when the chosen file has run out of space. It is shown that the above problem is a generalization of Banach's match-box problem known from the probability theory. A detailed separate analysis for the N=2 case and for the multivariate case is performed and some approximate results for large c are given.     

On estimation of a density and its derivatives

Summary Letf _n ^(p) be a recursive kernel estimate off ^(p) thepth order derivative of the probability density functionf, based on a random sample of sizen. In this paper, we provide bounds for the moments of and show that the rate of almost sure convergence of to zero isO(n ^−α), α<(r−p)/(2r+1), iff ^(r),r>p≧0, is a continuousL ₂(−∞, ∞) function. Similar rate-factor is also obtained for the almost sure convergence of to zero under different conditions onf. This work was supported in part by the Research Foundation of SUNY.     

Infinite divisibility of sub-stable processes. II. Logarithm of probability measure

We show that in some cases it is possible to get the Lévy measure v for an infinitely divisible distribution μ as a limit of some signed measuresL _N(μ) based on the convolution powers of μ. In the paper we give a collection of results in this area and apply the method to the investigation of the infinite divisibility of sub-stable random vectors onR ⁿ. Proceedings of the XVII Seminar on Stability Problems for Stochastic Models, Kazan, Russian, 1995, Part I.     

New global optima results for the Kauffman NK model: handling dependency

The Kauffman NK model has been used in theoretical biology, physics and business organizations to model complex systems with interacting components. This paper presents new global optima results for the NK model by developing tools for handling dependency in the cases where K grows with N; this generalizes the previous work that focused on the analysis of the (independent) case K=N−1. A dependency graph is defined and studied to handle dependencies among underlying random variables in the NK model. Order statistics (with dependencies) and the expected value of the global optima, E _{N, K} , are bounded using equitable coloring of the dependency graph. These bounds convert the problem of bounding order statistics of dependent random variables into that of independent random variables while incorporating quantitative information about the mutual dependencies between the underlying random variables. An alternative upper bound on E _{N, K} using direct arguments is also proposed. A detailed analysis of E _{N, K} for K close to N (K=N−α and K=β N, α ∈ Z ⁺,β ∈ (0,1)) is given for underlying uniform and normal distributions. Finally, for bounded underlying distributions, the global optima is shown to be concentrated around its mean E _{N, K} .     

Pseudo-character expansions forU(N)-invariant spin models onCP N−1

We define a set of orthogonal functions on the complex projective spaceCP ^N–1, and compute their Clebsch-Gordan coefficients as well as a large class of 6-j symbols. We also provide all the needed formulae for the generation of high-temperature expansions forU(N)-invariant spin models defined onCP ^N–1.     

Random orders

Letk andn be positive integers and fix a setS of cardinalityn; letP _k (n) be the (partial) order onS given by the intersection ofk randomly and independently chosen linear orders onS. We begin study of the basic parameters ofP _k (n) (e.g., height, width, number of extremal elements) for fixedk and largen. Our object is to illustrate some techniques for dealing with these random orders and to lay the groundwork for future research, hoping that they will be found to have useful properties not obtainable by known constructions.Supported by NSF grant MCS 84-02054.