Diffusions in random environment and ballistic behavior

In this article we investigate the ballistic behavior of diffusions in random environment. We introduce conditions in the spirit of (T) and (T^′) of the discrete setting, cf. [A.-S. Sznitman, On a class of transient random walks in random environment, Ann. Probab. 29 (2) (2001) 723–764; A.-S. Sznitman, An effective criterion for ballistic behavior of random walks in random environment, Probab. Theory Related Fields 122 (4) (2002) 509–544], that imply, when d2, a law of large numbers with non-vanishing limiting velocity (which we refer to as ‘ballistic behavior’) and a central limit theorem with non-degenerate covariance matrix. As an application of our results, we consider the class of diffusions where the diffusion matrix is the identity, and give a concrete criterion on the drift term under which the diffusion in random environment exhibits ballistic behavior. This criterion provides examples of diffusions in random environment with ballistic behavior, beyond what was previously known.     

Random walks on finitely structured transfinite networks

A general theory for random walks on transfinite networks whose ranks are arbitrary natural numbers is established herein. In such networks, nodes of higher ranks connect together transfinite networks of lower ranks. The probabilities for transitions through such nodes are obtained as extensions of the Nash-Williams rule for random walks on ordinary infinite networks. The analysis is based on the theory of transfinite electrical networks, but it requires that the transfinite network have a structure that generalizes local-finiteness for ordinary infinite networks. The shorting together of nodes of different ranks are allowed; this complicates transitions through such nodes but provides a considerably more general theory. It is shown that, with respect to any finite set of nodes of any ranks, a transfinite random walk can be represented by an irreducible reversible Makov chain, whose state space is that set of nodes.This work was supported by the National Science Foundation under the grants DMS-9200738 and MIP-9200748.     

Walks on the slit plane

 In the first part of this paper, we enumerate exactly walks on the square lattice that start from the origin, but otherwise avoid the half-line . We call them walks on the slit plane. We count them by their length, and by the coordinates of their endpoint. The corresponding three variable is algebraic of degree 8. Moreover, for any point (i, j), the length for walks of this type ending at (i, j) is also algebraic, of degree 2 or 4, and involves the famous Catalan numbers. Our method is based on the solution of a functional equation, established via a simple combinatorial argument. It actually works for more general models, in which walks take their steps in a finite subset of ℤ² satisfying two simple conditions. The corresponding are always algebraic. In the second part of the paper, we derive from our enumerative results a number of probabilistic corollaries. For instance, we can compute exactly the probability that an ordinary random walk starting from (i, j) hits for the first time the half-line at position (k, 0), for any triple (i, j, k). This generalizes a question raised by R. Kenyon, which was the starting point of this paper. Taking uniformly at random all n-step walks on the slit plane, we also compute the probability that they visit a given point (k, 0), and the average number of visits to this point. In other words, we quantify the transience of the walks. Finally, we derive an explicit limit law for the coordinates of their endpoint. Received: 22 December 2001 / Revised version: 19 February 2002 / Published online: 30 September 2002 Both authors were partially supported by the INRIA, via the cooperative research action Alcophys. Mathematics Subject Classification (2000): O5A15-60C05     

On the norms of group-invariant transition operators on graphs

In this paper we consider reversible random walks on an infinite grapin, invariant under the action of a closed subgroup of automorphisms which acts with a finite number of orbits on the vertex-set. Thel ²-norm (spectral radius) of the simple random walk is equal to one if and only if the group is both amenable and unimodular, and this also holds for arbitrary random walks with bounded invariant measure. In general, the norm is bounded above by the Perron-Frobenius eigenvalue of a finite matrix, and this bound is attained if and only if the group is both amenable and unimodular.     

Random walks on simplicial complexes and harmonics

In this paper, we introduce a class of random walks with absorbing states on simplicial complexes. Given a simplicial complex of dimension d, a random walk with an absorbing state is defined which relates to the spectrum of the k‐dimensional Laplacian for 1 ≤ k ≤ d. We study an example of random walks on simplicial complexes in the context of a semi‐supervised learning problem. Specifically, we consider a label propagation algorithm on oriented edges, which applies to a generalization of the partially labelled classification problem on graphs. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 379–405, 2016     

Random walks and the effective resistance sum rules

In this paper, using the intimate relations between random walks and electrical networks, we first prove the following effective resistance local sum rules:

     

Weak convergence to fractional Brownian motion in Brownian scenery

 Kesten and Spitzer have shown that certain random walks in random sceneries converge to stable processes in random sceneries. In this paper, we consider certain random walks in sceneries defined using stationary Gaussian sequence, and show their convergence towards a certain self-similar process that we call fractional Brownian motion in Brownian scenery. Received: 17 April 2002 / Revised version: 11 October 2002 / Published online: 15 April 2003 Research supported by NSFC (10131040). Mathematics Subject Classification (2002): 60J55, 60J15, 60J65 Key words or phrases: Weak convergence – Random walk in random scenery – Local time – Fractional Brownian motion in Brownian scenery     

Expected hitting and cover times of random walks on some special graphs

We give general bounds (and in some cases exact values) for the expected hitting and cover times of the simple random walk on some special undirected connected graphs using symmetry and properties of electrical networks. In particular we give easy proofs for an N–1H_N-1 lower bound and an N² upper bound for the cover time of symmetric graphs and for the fact that the cover time of the unit cube is Φ(NlogN). We giver a counterexample to a conjecture of Freidland about a general bound for hitting times. Using the electric approach, we provide some genral upper and lower bounds for the expected cover times in terms of the diameter of the graph. These bounds are tight in many instances, particularly when the graph is a tree. © 1994 John Wiley & Sons, Inc.     

Stratified random walks on the n-cube

In this paper we present a method for analyzing a general class of random walks on the n-cube (and certain subgraphs of it). These walks all have the property that the transition probabilities depend only on the level of the point at which the walk is. For these walks, we derive sharp bounds on their mixing rates, i.e., the number of steps required to guarantee that the resulting distribution is close to the (uniform) stationary distribution. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 199–222, 1997     

Asymptotically one-dimensional diffusions on the Sierpinski gasket and theabc-gaskets

Summary Diffusion processes on the Sierpinski gasket and theabc-gaskets are constructed as limits of random walks. In terms of the associated renormalization group, the present method uses the inverse trajectories which converge to unstable fixed points corresponding to the random walks on one-dimensional chains. In particular, non-degenerate fixed points are unnecessary for the construction. A limit theorem related to the discrete-time multi-type non-stationary branching processes is applied.     

Current Fluctuations for Independent Random Walks in Multiple Dimensions

Consider a system of particles evolving as independent and identically distributed (i.i.d.) random walks. Initial fluctuations in the particle density get translated over time with velocity [(v)\vec]\vec{v}, the common mean velocity of the random walks. Consider a box centered around an observer who starts at the origin and moves with constant velocity [(v)\vec]\vec{v}. To observe interesting fluctuations beyond the translation of initial density fluctuations, we measure the net flux of particles over time into this moving box. We call this the “box-current” process.     

A generalised inductive approach to the lace expansion

 The lace expansion is a powerful tool for analysing the critical behaviour of self-avoiding walks and percolation. It gives rise to a recursion relation which we abstract and study using an adaptation of the inductive method introduced by den Hollander and the authors. We give conditions under which the solution to the recursion relation behaves as a Gaussian, both in Fourier space and in terms of a local central limit theorem. These conditions are shown elsewhere to hold for sufficiently spread-out models of networks of self-avoiding walks in dimensions d > 4, and for sufficiently spread-out models of critical oriented percolation in dimensions d + 1 > 5, providing a unified approach and an essential ingredient for a detailed analysis of the branching behaviour of these models. Received: 13 September 2000 / Revised version: 16 May 2001 / Published online: 20 December 2001     

Slowdown estimates and central limit theorem for random walks in random environment

This work is concerned with asymptotic properties of multi-dimensional random walks in random environment. Under Kalikow’s condition, we show a central limit theorem for random walks in random environment on ℤ ^d , when d≥2. We also derive tail estimates on the probability of slowdowns. These latter estimates are of special interest due to the natural interplay between slowdowns and the presence of traps in the medium. The tail behavior of the renewal time constructed in [25] plays an important role in the investigation of both problems. This article also improves the previous work of the author [24], concerning estimates of probabilities of slowdowns for walks which are neutral or biased to the right. Received May 31, 1999 / final version received January 18, 2000?Published online April 19, 2000     

Restricted random walks on a graph

The problem of a restricted random walk on graphs, which keeps track of the number of immediate reversal steps, is considered by using a transfer matrix formulation. A closed-form expression is obtained for the generating function of the number ofn-step walks withr reversal steps for walks on any graph. In the case of graphs of a uniform valence, we show that our result has a probabilistic meaning, and deduce explicit expressions for the generating function in terms of the eigenvalues of the adjacency matrix. Applications to periodic lattices and the complete graph are given.Supported in part by National Science Foundation Grant DMR-9614170.     

Branching Random Walks in Space–Time Random Environment: Survival Probability,Global and Local Growth Rates

We study the survival probability and the growth rate for branching random walks in random environment (BRWRE). The particles perform simple symmetric random walks on the d-dimensional integer lattice, while at each time unit, they split into independent copies according to time–space i.i.d. offspring distributions. The BRWRE is naturally associated with the directed polymers in random environment (DPRE), for which the quantity called the free energy is well studied. We discuss the survival probability (both global and local) for BRWRE and give a criterion for its positivity in terms of the free energy of the associated DPRE. We also show that the global growth rate for the number of particles in BRWRE is given by the free energy of the associated DPRE, though the local growth rate is given by the directional free energy.     

Dynamics of Nonlinear Random Walks on Complex Networks

Journal of Nonlinear Science - In this paper, we study the dynamics of nonlinear random walks. While typical random walks on networks consist of standard Markov chains whose static transition...     

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.     

A maximum principle for node voltages in finitely structured,transfinite, electrical networks

Transfinite electrical networks have unique finite-powered voltage-current regimes given in terms of branch voltages and branch currents, but they do not in general possess unique node voltages. However, if their structures are sufficiently restricted, those node voltages will exist and will satisfy a maximum principle much like that which holds for ordinary infinite electrical networks. The structure that is imposed in order to establish these results generalized the idea of local-finiteness. Other properties that do not hold in general for transfinite networks but do hold under the imposed structure are Kirchhoff's current laws for nodes of any ranks and the permissibility of connecting pure voltage sources to such nodes. This work lays the foundation for a theory of transfinite random walks, which will be the subject of a subsequent work.This work was supported by the National Science Foundation under the grants DMS-9200738 and MIP-9200748.     

A combinatorial formula for Macdonald polynomials

In this paper we use the combinatorics of alcove walks to give uniform combinatorial formulas for Macdonald polynomials for all Lie types. These formulas resemble the formulas of Haglund, Haiman and Loehr for Macdonald polynomials of type GLn. At q=0 these formulas specialize to the formula of Schwer for the Macdonald spherical function in terms of positively folded alcove walks and at q=t=0 these formulas specialize to the formula for the Weyl character in terms of the Littelmann path model (in the positively folded gallery form of Gaussent and Littelmann).     

Long Excursions of a Random Walk

In Csáki et al. ⁽¹⁾ and Révész and Willekens⁽⁹⁾ it was proved that the length of the longest excursion among the first n excursions of a plane random walk is nearly equal to the total sum of the lenghts of these excursions. In this paper several results are proved in the same spirit, for plane random walks and for random walks in higher dimensions.