Simplicial complexes: Spectrum,homology and random walks

This paper studies the dynamical and asymptotic aspects of high‐dimensional expanders. We define a stochastic process on simplicial complexes of arbitrary dimension, which detects the existence of homology in the same way that a random walk on a finite graph reflects its connectedness. Through this, we obtain high‐dimensional analogues of graph properties such as bipartiteness, return probability, amenability and transience/recurrence. In the second part of the paper we generalize Kesten's result on the spectrum of regular trees, and of the connection between return probabilities and spectral radius. We study the analogue of the Alon‐Boppana theorem on spectral gaps, and exhibit a counterexample for its high‐dimensional counterpart. We show, however, that under some assumptions the theorem does hold ‐ for example, if the codimension‐one skeletons of the complexes in question form a family of expanders. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 225–261, 2017     

Moments of an exponential functional of random walks and permutations with given descent sets

The exponential functional of simple, symmetric random walks with negative drift is an infinite polynomial Y = 1 + ξ₁ + ξ₁ξ₂ + ξ₁ξ₂ξ₃ + ⋯ of independent and identically distributed non-negative random variables. It has moments that are rational functions of the variables μ _k = E(ξ ^k ) < 1 with universal coefficients. It turns out that such a coefficient is equal to the number of permutations with descent set defined by the multiindex of the coefficient. A recursion enumerates all numbers of permutations with given descent sets in the form of a Pascal-type triangle. This revised version was published online in August 2006 with corrections to the Cover Date.     

Branching random walks,stable point processes and regular variation

Using the theory of regular variation, we give a sufficient condition for a point process to be in the superposition domain of attraction of a strictly stable point process. This sufficient condition is used to obtain the weak limit of a sequence of point processes induced by a branching random walk with jointly regularly varying displacements. Because of heavy tails of the step size distribution, we can invoke a one large jump principle at the level of point processes to give an explicit representation of the limiting point process. As a consequence, we extend the main result of Durrett (1983) and verify that two related predictions of Brunet and Derrida (2011) remain valid for this model.     

Random walks in a strongly sparse random environment

The integer points (sites) of the real line are marked by the positions of a standard random walk with positive integer jumps. We say that the set of marked sites is weakly, moderately or strongly sparse depending on whether the jumps of the random walk are supported by a bounded set, have finite or infinite mean, respectively. Focussing on the case of strong sparsity and assuming additionally that the distribution tail of the jumps is regularly varying at infinity we consider a nearest neighbor random walk on the set of integers having jumps $\pm 1$ with probability $1∕2$ at every nonmarked site, whereas a random drift is imposed at every marked site. We prove new distributional limit theorems for the so defined random walk in a strongly sparse random environment, thereby complementing results obtained recently in Buraczewski et al. (2019) for the case of moderate sparsity and in Matzavinos et al. (2016) for the case of weak sparsity. While the random walk in a strongly sparse random environment exhibits either the diffusive scaling inherent to a simple symmetric random walk or a wide range of subdiffusive scalings, the corresponding limit distributions are non-stable.     

Velocity and Lyapounov exponents of some random walks in random environment

We express the asymptotic velocity of random walks in random environment satisfying Kalikow's condition in terms of the Lyapounov exponents which have previously been used in the context of large deviations.     

On the range of reversible random walks onZ 2 in a random environment

In this paper, a weak law of large numbers is obtained for the range of two dimensional reversible random walk in a random environment.Partly supported by NSF of China.     

Correlation functions of the XX Heisenberg magnet and random walks of vicious walkers

We investigate a relation between random walks on a one-dimensional periodic lattice and correlation functions of the XX Heisenberg spin chain. Operator averages over the ferromagnetic state play the role of generating functions of the number of paths traveled by so-called vicious random walkers (vicious walkers annihilate each other if they arrive at the same lattice site). We show that the two-point correlation function of spins calculated over eigenstates of the XX magnet can be interpreted as the generating function of paths traveled by a single walker in a medium characterized by a variable number of vicious neighbors. We obtain answers for the number of paths traveled by the described walker from a fixed lattice site to a sufficiently remote site. We provide asymptotic estimates of the number of paths in the limit of a large number of steps. __________ Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 159, No. 2, pp. 179–193, May, 2009.     

Lower bounds for covering times for reversible Markov chains and random walks on graphs

For simple random walk on aN-vertex graph, the mean time to cover all vertices is at leastcN log(N), wherec>0 is an absolute constant. This is deduced from a more general result about stationary finite-state reversible Markov chains. Under weak conditions, the covering time for such processes is at leastc times the covering time for the corresponding i.i.d. process.     

An elementary approach to Brownian local time based on simple,symmetric random walks

Summary In this paper we define Brownian local time as the almost sure limit of the local times of a nested sequence of simple, symmetric random walks. The limit is jointly continuous in <InlineEquation ID=IE"1"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"2"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"3"><EquationSource Format="TEX"><![CDATA[$]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>(t,x)$. The rate of convergence is $n^{\frac14} (\log n)^{\frac34}$ that is close to the best possible. The tools we apply are almost exclusively from elementary probability theory.     

Level crossing probabilities II: Polygonal recurrence of multidimensional random walks

In part I we proved for an arbitrary one-dimensional random walk with independent increments that the probability of crossing a level at a given time n is O(n−1/2). In higher dimensions we call a random walk ‘polygonally recurrent’ if there is a bounded set, hit by infinitely many of the straight lines between two consecutive sites a.s. The above estimate implies that three-dimensional random walks with independent components are polygonally transient. Similarly a directionally reinforced random walk on Z³ in the sense of Mauldin, Monticino and von Weizsäcker [R.D. Mauldin, M. Monticino, H. von Weizsäcker, Directionally reinforced random walks, Adv. Math. 117 (1996) 239-252] is transient. On the other hand, we construct an example of a transient but polygonally recurrent random walk with independent components on Z².     

Wiener's test for space-time random walks and its applications

This paper establishes a criterion for whether a -dimensional random walk on the integer lattice visits a space-time subset infinitely often or not. It is a precise analogue of Wiener's test for regularity of a boundary point with respect to the classical Dirichlet problem. The test obtained is applied to strengthen the harder half of Kolmogorov's test for the random walk.

     

A path-transformation for random walks and the Robinson-Schensted correspondence

The author and Marc Yor recently introduced a path-transformation with the property that, for belonging to a certain class of random walks on , the transformed walk has the same law as the original walk conditioned never to exit the Weyl chamber . In this paper, we show that is closely related to the Robinson-Schensted algorithm, and use this connection to give a new proof of the above representation theorem. The new proof is valid for a larger class of random walks and yields additional information about the joint law of and . The corresponding results for the Brownian model are recovered by Donsker's theorem. These are connected with Hermitian Brownian motion and the Gaussian Unitary Ensemble of random matrix theory. The connection we make between the path-transformation and the Robinson-Schensted algorithm also provides a new formula and interpretation for the latter. This can be used to study properties of the Robinson-Schensted algorithm and, moreover, extends easily to a continuous setting.

     

Random walks which prefer unvisited edges: Exploring high girth even degree expanders in linear time

Let be a connected graph with vertices. A simple random walk on the vertex set of G is a process, which at each step moves from its current vertex position to a neighbouring vertex chosen uniformly at random. We consider a modified walk which, whenever possible, chooses an unvisited edge for the next transition; and makes a simple random walk otherwise. We call such a walk an edge‐process (or E‐process). The rule used to choose among unvisited edges at any step has no effect on our analysis. One possible method is to choose an unvisited edge uniformly at random, but we impose no such restriction. For the class of connected even degree graphs of constant maximum degree, we bound the vertex cover time of the E‐process in terms of the edge expansion rate of the graph G, as measured by eigenvalue gap of the transition matrix of a simple random walk on G. A vertex v is ?‐good, if any even degree subgraph containing all edges incident with v contains at least ? vertices. A graph G is ?‐good, if every vertex has the ?‐good property. Let G be an even degree ?‐good expander of bounded maximum degree. Any E‐process on G has vertex cover time This is to be compared with the lower bound on the cover time of any connected graph by a weighted random walk. Our result is independent of the rule used to select the order of the unvisited edges, which could, for example, be chosen on‐line by an adversary. As no walk based process can cover an n vertex graph in less than n – 1 steps, the cover time of the E‐process is of optimal order when . With high probability random r‐regular graphs, even, have . Thus the vertex cover time of the E‐process on such graphs is . © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 36–54, 2015     

Local asymptotic normality of multivariate ARMA processes with a linear trend

The local asymptotic normality (LAN) property is established for multivariate ARMA models with a linear trend or, equivalently, for multivariate general linear models with ARMA error term. In contrast with earlier univariate results, the central sequence here is correlogram-based, i.e. expressed in terms of a generalized concept of residual cross-covariance function.     

A class of infinitely divisible distributions connected to branching processes and random walks

A class of infinitely divisible distributions on {0,1,2,…} is defined by requiring the (discrete) Lévy function to be equal to the probability function except for a very simple factor. These distributions turn out to be special cases of the total offspring distributions in (sub)critical branching processes and can also be interpreted as first passage times in certain random walks. There are connections with Lambert's W function and generalized negative binomial convolutions.     

Global stability of a multistrain SIS model with superinfection and patch structure

We study the global stability of a multistrain SIS model with superinfection and patch structure. We establish an iterative procedure to obtain a sequence of threshold parameters. By a repeated application of a result by Takeuchi et al. [Nonlinear Anal Real World Appl. 2006;7:235–247], we show that these parameters completely determine the global dynamics of the system: for any number of patches and strains with different infectivities, any subset of the strains can stably coexist depending on the particular choice of the parameters.     

Finding blocks and other patterns in a random coloring of ℤ

Let ξ = (ξ_k)_k∈? be i.i.d. with P(ξ_k = 0) = P(ξ_k = 1) = 1/2, and let S: = (S_k) be a symmetric random walk with holding on ?, independent of ξ. We consider the scenery ξ observed along the random walk path S, namely, the process (χ_k := ξ). With high probability, we reconstruct the color and the length of blockⁿ, a block in ξ of length ≥ n close to the origin, given only the observations (χ_k). We find stopping times that stop the random walker with high probability at particular places of the scenery, namely on blockⁿ and in the interval [?3ⁿ,3ⁿ]. Moreover, we reconstruct with high probability a piece of ξ of length of the order 3 around blockⁿ, given only 3 observations collected by the random walker starting on the boundary of blockⁿ. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006