Group generalized inverses of M-matrices associated with periodic and nonperiodic jacobi matrices

We consider two types of irreducible stochastic matrices —tridiagonal matrices and periodic jacobi matrices —which can be viewed as transition matrices of interval and circular random walks,respcetively. For both types of matrices we give a formula for the group inverse of the associated singular M-matrix. We discuss both the sign patterns and the relative sizes of the entries in these group inverses and apply our results to give qualitative information about random walks on an interval and on a circle.     

Functional equation for the crossover in the model of one-dimensional Weierstrass random walks

We consider the problem of one-dimensional symmetric diffusion in the framework of Markov random walks of the Weierstrass type using two-parameter scaling for the transition probability. We construct a solution for the characteristic Lyapunov function as a sum of regular (homogeneous) and singular (nonhomogeneous) solutions and find the conditions for the crossover from normal to anomalous diffusion.     

Localization in lattice and continuum models of reinforced random walks

We study the singular limit of a class of reinforced random walks on a lattice for which a complete analysis of the existence and stability of solutions is possible. We show that at a sufficiently high total density, the global minimizer of a lattice ‘energy’ or Lyapunov functional corresponds to aggregation at one site. At lower values of the density the stable localized solution coexists with a stable spatially-uniform solution. Similar results apply in the continuum limit, where the singular limit leads to a nonlinear diffusion equation. Numerical simulations of the lattice walk show a complicated coarsening process leading to the final aggregation.     

Harnack inequalities and difference estimates for random walks with infinite range

Difference estimates and Harnack inequalities for mean zero, finite variance random walks with infinite range are considered. An example is given to show that such estimates and inequalities do not hold for all mean zero, finite variance random walks. Conditions are then given under which such results can be proved.Research supported by the National Science Foundation.     

The expansion theorem for the deviation integra

The so-called deviation integral (functional) describes the logarithmic asymptotics of the probabilities of large deviations for random walks generated by sums of random variables or vectors. Here an important role is played by the expansion theorem for the deviation integral in which, for an arbitrary function of bounded variation, the deviation integral is represented as the sum of suitable integrals of the absolutely continuous, singular, and discrete components composing this function. The expansion theorem for the deviation integral was proved by A. A. Borovkov and the author in [9] under some simplifying assumptions. In this article, we waive these assumptions and prove the expansion theorem in the general form.     

Large deviations for random walks in a mixing random environment and other (non‐Markov) random walks

We extend a recent work by S. R. S. Varadhan [8] on large deviations for random walks in a product random environment to include more general random walks on the lattice. In particular, some reinforced random walks and several classes of random walks in Gibbs fields are included. © 2004 Wiley Periodicals, Inc.     

A combinatorial result with applications to self-interacting random walks

We give a series of combinatorial results that can be obtained from any two collections (both indexed by Z×N) of left and right pointing arrows that satisfy some natural relationship. When applied to certain self-interacting random walk couplings, these allow us to reprove some known transience and recurrence results for some simple models. We also obtain new results for one-dimensional multi-excited random walks and for random walks in random environments in all dimensions.     

Reconstruction of periodic sceneries seen along a random walk

This article was motivated by a question of Kesten. Kesten asked for which random walks periodic sceneries can be reconstructed. Among others, he asked the question for random walks which at each step can move by one or two units to the right. Previously, Howard [C.D. Howard, Distinguishing certain random sceneries on Z$\mathbb{Z}$ via random walks, Statist. Probab. Lett. 34 (2) (1997) 123–132] proved that all periodic sceneries can be reconstructed provided they are observed along the path of a simple random walk.     

Continuity for the asymptotic shape in the frog model with random initial configurations

We consider the so-called frog model with random initial configurations, which is described by the following evolution mechanism of simple random walks on the multidimensional cubic lattice: Some particles are randomly assigned to any site of the multidimensional cubic lattice. Initially, only particles at the origin are active and they independently perform simple random walks. The other particles are sleeping and do not move at first. When sleeping particles are hit by an active particle, they become active and start doing independent simple random walks. An interest of this model is how initial configurations affect the asymptotic shape of the set of all sites visited by active particles up to a certain time. Thus, in this paper, we prove continuity for the asymptotic shape in the law of the initial configuration.     

Laws of iterated logarithm for transient random walks in random environments

We consider laws of iterated logarithm for one-dimensional transient random walks in random environments. A quenched law of iterated logarithm is presented for transient random walks in general ergodic random environments, including independent identically distributed environments and uniformly ergodic environments.     

Classifying lattice walks restricted to the quarter plane

This work considers the nature of generating functions of random lattice walks restricted to the first quadrant. In particular, we find combinatorial criteria to decide if related series are algebraic, transcendental holonomic or otherwise. Complete results for walks taking their steps in a maximum of three directions of restricted amplitude are given, as is a well-supported conjecture for all walks with steps taken from a subset of ²{0,±1}. New enumerative results are presented for several classes, each obtained with a variant of the kernel method.     

A law of the iterated logarithm for Markov chains on ℕ0 associated with orthogonal polynomials

We derive laws of the iterated logarithm for Markov chains on the nonnegative integers whose transition probabilities are associated with a sequence of orthogonal polynomials. These laws can be applied to a large class of birth and death random walks and random walks on polynomial hypergroups. In particular, the results of our paper lead immediately to a law of the iterated logarithm for the growth of the distance of isotropic random walks on infinite distance-transitive graphs as well as on certain finitely generated semigroups from their starting points.     

On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processes

In this paper we define and analyze convergence of the geometric random walks, which are certain random walks on vector spaces over finite fields. We show that the behavior of such walks is given by certain random matroid processes. In particular, the mixing time is given by the expected stopping time, and the cutoff is equivalent to sharp threshold. We also discuss some random geometric random walks as well as some examples and symmetric cases.     

Quantum random walks and their convergence to Evans-Hudson flows

Using coordinate-free basic operators on toy Fock spaces, quantum random walks are defined following the ideas of Attal and Pautrat. Extending the result for one dimensional noise, strong convergence of quantum random walks associated with bounded structure maps to Evans-Hudson flow is proved under suitable assumptions. Starting from the bounded generator of a given uniformly continuous quantum dynamical semigroup on a von Neumann algebra, we have constructed quantum random walks which converges strongly and the strong limit gives an Evans-Hudson dilation for the semigroup.     

Tubular recurrence

We introduce the directed-edge-reinforced random walk and prove that the process is equivalent to a random walk in random environment. Using Oseledec"s multiplicative ergodic theorem, we obtain recurrence and transience criteria for random walks in random environment on graphs with a certain linear structure and apply them to directed-edge-reinforced random walks. This revised version was published online in August 2006 with corrections to the Cover Date.     

Matrix random products with singular harmonic measure

Any Zariski dense countable subgroup of SL(d, \mathbb R){SL(d, \mathbb {R})} is shown to carry a non-degenerate finitely supported symmetric random walk such that its harmonic measure on the flag space is singular. The main ingredients of the proof are: (1) a new upper estimate for the Hausdorff dimension of the projections of the harmonic measure onto Grassmannians in \mathbb R^d{\mathbb {R}^d} in terms of the associated differential entropies and differences between the Lyapunov exponents; (2) an explicit construction of random walks with uniformly bounded entropy and arbitrarily long Lyapunov vector.     

Random walks and the effective resistance of networks

In this article we present an interpretation ofeffective resistance in electrical networks in terms of random walks on underlying graphs. Using this characterization we provide simple and elegant proofs for some known results in random walks and electrical networks. We also interpret the Reciprocity theorem of electrical networks in terms of traversals in random walks. The byproducts are (a) precise version of thetriangle inequality for effective resistances, and (b) an exact formula for the expectedone-way transit time between vertices.     

LYAPOUNOV EXPONENTS AND LAW OF LARGE NUMBERS FOR RANDOM WALK IN RANDOM ENVIRONMENT WITH HOLDING TIMES

In this article, the authors mainly discuss the law of large number under Kalikow＇s condition for multi-dimensional random walks in random environment with holding times. The authors give an expression to the escape speed of random walks in terms of the Lyapounov exponents, which have been precisely used in the context of large deviation.     

随机环境中广义随机游动的灭绝概率

随机环境中广义随机游动(GRWRE)是随机环境中随机游动(RWRE)的推广．该文构造了非负整数集上的GRWRE,证明了这种模型的存在性,并计算了灭绝概率．     

Random Walks on Trees with Finitely Many Cone Types

This paper is devoted to the study of random walks on infinite trees with finitely many cone types (also called periodic trees). We consider nearest neighbour random walks with probabilities adapted to the cone structure of the tree, which include in particular the well studied classes of simple and homesick random walks. We give a simple criterion for transience or recurrence of the random walk and prove that the spectral radius is equal to 1 if and only if the random walk is recurrent. Furthermore, we study the asymptotic behaviour of return probabilitites and prove a local limit theorem. In the transient case, we also prove a law of large numbers and compute the rate of escape of the random walk to infinity, as well as prove a central limit theorem. Finally, we describe the structure of the boundary process and explain its connection with the random walk.