On Large Deviations of Multivariate Heavy-Tailed Random Walks

Let {S _n ;n=1,2,…} be a random walk in R ^d and E(S ₁)=(μ ₁,…,μ _d ). Let a _j >μ _j for j=1,…,d and A=(a ₁,∞)×⋅⋅⋅×(a _d ,∞). We are interested in the probability P(S _n /n∈A) for large n in the case where the components of S ₁ are heavy tailed. An objective is to associate an exact power with the aforementioned probability. We also derive sharper asymptotic bounds for the probability and show that in essence, the occurrence of the event {S _n /n∈A} is caused by large single increments of the components in a specific way.      

Asymptotics for Random Walks with Dependent Heavy-Tailed Increments

We consider a random walk {S _n} with dependent heavy-tailed increments and negative drift. We study the asymptotics for the tail probability P{sup _n S _n >x} as x. If the increments of {S _n} are independent then the exact asymptotic behavior of P{sup _n S _n >x} is well known. We investigate the case in which the increments are given as a one-sided asymptotically stationary linear process. The tail behavior of sup _n S _n turns out to depend heavily on the coefficients of this linear process.     

Large Deviations View Points for Heavy-Tailed Random Walks

Let X ₁, X ₂,... be a sequence of i.i.d. non-negative random variables with heavy tails. W e study logarithmic asymptotics for the distributions of the partial sums S _n = X ₁ + ··· + X _n . Our main interest is in the crude estimates P(S _n > n ^x ) n ^{–x + 1} for appropriate values of x where is a specific parameter. The related conjecture proposed by Gantert (Stat. Probab. Lett. 49, 113–118) is investigated.     

Discrete and Continuous Time Modulated Random Walks with Heavy-Tailed Increments

We consider a modulated process S which, conditional on a background process X, has independent increments. Assuming that S drifts to −∞ and that its increments (jumps) are heavy-tailed (in a sense made precise in the paper), we exhibit natural conditions under which the asymptotics of the tail distribution of the overall maximum of S can be computed. We present results in discrete and in continuous time. In particular, in the absence of modulation, the process S in continuous time reduces to a Lévy process with heavy-tailed Lévy measure. A central point of the paper is that we make full use of the so-called “principle of a single big jump” in order to obtain both upper and lower bounds. Thus, the proofs are entirely probabilistic. The paper is motivated by queueing and Lévy stochastic networks.     

有向图上的随机游动

设G=(V,Г)是有向图,G上的随机游动X(G)定义如下:位于某个顶点上的一个粒子将以等概率转移到该顶点的所有后继顶点.令M(j,n)表示随机游动X(G)在前n步内访问顶点j的平均次数,用W(j)表示随机游动X(G)到达顶点j所需要的平均步效.我们对M(j,n)和W(j)的值进行了估计,证明了M(j,n)=O(n),并给出了W(j)的上界.     

Random Walks on Dihedral Groups

In this paper, we look at the lower bounds of two specific random walks on the dihedral group. The first theorem discusses a random walk generated with equal probabilities by one rotation and one flip. We show that roughly p ² steps are necessary for the walk to become close to uniformly distributed on all of D _2p where p≥3 is an integer. Next we take a random walk on the dihedral group generated by a random k-subset of the dihedral group. The latter theorem shows that it is necessary to take roughly p ^2/(k−1) steps in the typical random walk to become close to uniformly distributed on all of D _2p . We note that there is at least one rotation and one flip in the k-subset, or the random walk generated by this subset has periodicity problems or will not generate all of D _2p .     

Random Lazy Random Walks on Arbitrary Finite Groups

This paper considers lazy random walks supported on a random subset of k elements of a finite group G with order n. If k=a log₂ n where a>1 is constant, then most such walks take no more than a multiple of log₂ n steps to get close to uniformly distributed on G. If k=log₂ n+f(n) where f(n) and f(n)/log₂ n0 as n, then most such walks take no more than a multiple of (log₂ n) ln(log₂ n) steps to get close to uniformly distributed. To get these results, this paper extends techniques of Erdös and Rényi and of Pak.     

Lamplighter Random Walks on Fractals

We consider on-diagonal heat kernel estimates and the laws of the iterated logarithm for a switch-walk-switch random walk on a lamplighter graph under the condition that the random walk on the underlying graph enjoys sub-Gaussian heat kernel estimates.     

Moderate Deviations for Random Sums of Heavy-Tailed Random Variables

Let {Xn;n≥ 1} be a sequence of independent non-negative random variables with common distribution function F having extended regularly varying tail and finite mean μ = E（X1） and let {N（t）; t ≥0} be a random process taking non-negative integer values with finite mean λ（t） = E（N（t）） and independent of {Xn; n ≥1}. In this paper, asymptotic expressions of P（（X1 ＋… ＋XN（t）） -λ（t）μ 〉 x） uniformly for x ∈[γb（t）, ∞） are obtained, where γ〉 0 and b（t） can be taken to be a positive function with limt→∞ b（t）/λ（t） = 0.     

Random Walks on Planar Crystallographic Groups

For the example of the group G = pgg generated by two orthogonal gliding symmetries, we calculate the generating matrix. For the same example, we reduce the property of random walks on planar crystallographic groups to the local behavior of the resolvent. Bibliography: 8 titles.     

Dynamic Random Walks on Heisenberg Groups

We prove a Guivarc’h law of large numbers and a central limit theorem for dynamic random walks on Heisenberg groups. The limiting distribution is explicitely given. To our knowledge this is the first study of dynamic random walks on non-commutative Lie groups.      

Weak Mixing of Random Walks on Groups

Let G be a locally compact -compact group with right Haar measure m and a regular probability measure on G. We say that is weakly mixing if for all gL (G) and all fL ¹(G) with fdm=0 we have n ^{–1 n} _k=1| ^k *f,g|0. We show that is weakly mixing if and only if is ergodic and strictly aperiodic. To prove this we use and prove some results about unimodular eigenvalues for general Markov operators.     

Random Walks on Wreath Products of Groups

We bound the rate of convergence to uniformity for a certain random walk on the complete monomial groups GS _n for any group G. Specifically, we determine that n log n+ n log (|G|–1|) steps are both necessary and sufficient for ² distance to become small. We also determine that n log n steps are both necessary and sufficient for total variation distance to become small. These results provide rates of convergence for random walks on a number of groups of interest: the hyperoctahedral group ₂S _n , the generalized symmetric group _m S _n , and S _m S _n . In the special case of the hyperoctahedral group, our random walk exhibits the cutoff phenomenon.     

Random Walks in Random Media on a Cayley Tree

We present sufficient conditions for the transience of random walks with bounded jumps in random media on a Cayley tree.     

Fastest Coupling of Random Walks

A new coupling of one-dimensional random walks is describedwhich tries to control the coupling by keeping the separationof the two random walks of constant sign. It turns out thatamong such monotone couplings there is an optimal one-step couplingwhich maximises the second moment of the difference (assumingthis is finite), and this coupling is ‘fast’ inthe sense that for a random walk with a unimodal step distributionthe coupling time achieved by using the new coupling at eachstep is stochastically no larger than any other coupling. Thisis applied to the case of symmetric unimodal distributions.     

Random Walks on Directed Covers of Graphs

Directed covers of finite graphs are also known as periodic trees or trees with finitely many cone types. We expand the existing theory of directed covers of finite graphs to those of infinite graphs. While the lower growth rate still equals the branching number, upper and lower growth rates no longer coincide in general. Furthermore, the behavior of random walks on directed covers of infinite graphs is more subtle. We provide a classification in terms of recurrence and transience and point out that the critical random walk may be recurrent or transient. Our proof is based on the observation that recurrence of the random walk is equivalent to the almost sure extinction of an appropriate branching process. Two examples in random environment are provided: homesick random walk on infinite percolation clusters and random walk in random environment on directed covers. Furthermore, we calculate, under reasonable assumptions, the rate of escape with respect to suitable length functions and prove the existence of the asymptotic entropy providing an explicit formula which is also a new result for directed covers of finite graphs. In particular, the asymptotic entropy of random walks on directed covers of finite graphs is positive if and only if the random walk is transient.     

半直线上随机环境中可逗留随机游动的常返性

本文主要讨论了在独立但不同分布环境下，半直线上可逗留随机环境中随机游动的常返性和非常返性，并进一步研究了常返性中的正常返性和零常返性．     

一类随机环境中的随机游动

在Solomn的模型的基础上对一类随机环境中随机游动进行了讨论，并得出了一个常返性准则和一些极限性质。