Random walks on quasisymmetric functions

Conditions are provided under which an endomorphism on quasisymmetric functions gives rise to a left random walk on the descent algebra which is also a lumping of a left random walk on permutations. Spectral results are also obtained. Several important random walks are now realized this way: Stanley's QS-distribution results from endomorphisms given by evaluation maps, a-shuffles result from the ath convolution power of the universal character, and the Tchebyshev operator of the second kind introduced recently by Ehrenborg and Readdy yields traditional riffle shuffles. A conjecture of Ehrenborg regarding the spectra for a family of random walks on ab-words is proven. A theorem of Stembridge from the theory of enriched P-partitions is also recovered as a special case.     

Extreme values of the stationary distribution of random walks on directed graphs

We examine the stationary distribution of random walks on directed graphs. In particular, we focus on the principal ratio, which is the ratio of maximum to minimum values of vertices in the stationary distribution. We give an upper bound for this ratio over all strongly connected graphs on n vertices. We characterize all graphs achieving the upper bound and we give explicit constructions for these extremal graphs. Additionally, we show that under certain conditions, the principal ratio is tightly bounded. We also provide counterexamples to show the principal ratio cannot be tightly bounded under weaker conditions.     

Non-homogeneous random walks on a semi-infinite strip

We study the asymptotic behaviour of Markov chains (_Xn,_ηn)$(X_n,{\eta }_n)$ on _Z+×S${\mathbb{Z}}_{+}\times S$, where _Z+${\mathbb{Z}}_{+}$ is the non-negative integers and S$S$ is a finite set. Neither coordinate is assumed to be Markov. We assume a moments bound on the jumps of _Xn$X_n$, and that, roughly speaking, _ηn${\eta }_n$ is close to being Markov when _Xn$X_n$ is large. This departure from much of the literature, which assumes that _ηn${\eta }_n$ is itself a Markov chain, enables us to probe precisely the recurrence phase transitions by assuming asymptotically zero drift for _Xn$X_n$ given _ηn${\eta }_n$. We give a recurrence classification in terms of increment moment parameters for _Xn$X_n$ and the stationary distribution for the large- X$X$ limit of _ηn${\eta }_n$. In the null case we also provide a weak convergence result, which demonstrates a form of asymptotic independence between _Xn$X_n$ (rescaled) and _ηn${\eta }_n$. Our results can be seen as generalizations of Lamperti’s results for non-homogeneous random walks on _Z+${\mathbb{Z}}_{+}$ (the case where S$S$ is a singleton). Motivation arises from modulated queues or processes with hidden variables where _ηn${\eta }_n$ tracks an internal state of the system.     

Random walks on generalized lattices

A generalized lattice is a graph on which the groupZ ^d acts almost transitively. The relations among various features of random walks on generalized lattices are studied. In particular we relate the mean displacement, the drift-freeness of the random walk and the existence of linear harmonic functions. Applications to recurrence criteria are given.     

Component structure in the evolution of random hypergraphs

The component structure of the most general random hypergraphs, with edges of differen sizes, is analyzed. We show that, as this is the case for random graphs, there is a “double jump” in the probable and almost sure size of the greatest component of hypergraphs, when the average vertex degree passes the value 1.     

Sharp concentration of the chromatic number on random graphsG n,p

The distribution of the chromatic number on random graphsG _{n, p} is quite sharply concentrated. For fixedp it concentrates almost surely in √n ω(n) consecutive integers where ω(n) approaches infinity arbitrarily slowly. If the average degreepn is less thann ^1/6, it concentrates almost surely in five consecutive integers. Large deviation estimates for martingales are used in the proof.     

Intersections of random walks and Wiener sausages in four dimensions

Let {S ₁ (n)} _n0and {S ₂ (n)} _n0be independent simple random walks in Z ⁴ starting at the origin, and let % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXafv3ySLgzGmvETj2BSbqefm0B1jxALjhiov2D% aebbfv3ySLgzGueE0jxyaibaiGc9yrFr0xXdbba91rFfpec8Eeeu0x% Xdbba9frFj0-OqFfea0dXdd9vqaq-JfrVkFHe9pgea0dXdar-Jb9hs% 0dXdbPYxe9vr0-vr0-vqpWqaaeaabiGaciaacaqabeaadaqaaqGaaO% qaaiabfc6aqnaaBaaaleaacaqGPbaabeaatCvAUfKttLearyqr1ngB% Prgaiuaakiab-HcaOiaadggacaGGSaGaamOyaiab-LcaPiabg2da9i% ab-Tha7Hqbciab+Hha4jabgIGiolab+PfaAnaaCaaaleqabaGaaGin% aaaakiaacQdaieGacaqFtbWaaSbaaSqaaiaabMgaaeqaaOGae8hkaG% Iaa0xBaiab-LcaPiabg2da9iab+Hha4baa!5761!\[\Pi _{\rm{i}} (a,b) = \{ x \in Z^4 :S_{\rm{i}} (m) = x\]for the some % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXafv3ySLgzGmvETj2BSbqefm0B1jxALjhiov2D% aebbfv3ySLgzGueE0jxyaibaiGc9yrFr0xXdbba91rFfpec8Eeeu0x% Xdbba9frFj0-OqFfea0dXdd9vqaq-JfrVkFHe9pgea0dXdar-Jb9hs% 0dXdbPYxe9vr0-vr0-vqpWqaaeaabiGaciaacaqabeaadaqaaqGaaO% qaaGqaciaa-1gacqGHiiIZtCvAUfKttLearyqr1ngBPrgaiuaacqGF% OaakcaWGHbGaaiilaiaadkgacqGFPaqkcqGF9bqFaaa!4936!\[m \in (a,b)\} \]. Let two integervalued sequences {a _n}_n0and {b _n}_n0be given, such that the limit lim_n a _nexists and lim _n b _n=+. In this paper, it is shown that the probability of % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXafv3ySLgzGmvETj2BSbqefm0B1jxALjhiov2D% aebbfv3ySLgzGueE0jxyaibaiGc9yrFr0xXdbba91rFfpec8Eeeu0x% Xdbba9frFj0-OqFfea0dXdd9vqaq-JfrVkFHe9pgea0dXdar-Jb9hs% 0dXdbPYxe9vr0-vr0-vqpWqaaeaabiGaciaacaqabeaadaqaaqGaaO% qaaiabfc6aqnaaBaaaleaacaaIXaaabeaatCvAUfKttLearyqr1ngB% Prgaiuaakiab-HcaOiab-bdaWiab-XcaSiabg6HiLkab-LcaPiabgM% Iihlabfc6aqnaaBaaaleaacaaIYaaabeaakiab-HcaOiaadggadaWg% aaWcbaGaamOBaiaacYcaaeqaaOGaamyyamaaBaaaleaacaWGUbaabe% aakiabgUcaRiaadkgadaWgaaWcbaGaamOBaaqabaGccqWFPaqkcqGH% GjsUieaacaGFydaaaa!5904!\[\Pi _1 (0,\infty ) \cap \Pi _2 (a_{n,} a_n + b_n ) \ne \O \] is asymptotic to % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXafv3ySLgzGmvETj2BSbqefm0B1jxALjhiov2D% aebbfv3ySLgzGueE0jxyaibaiGc9yrFr0xXdbba91rFfpec8Eeeu0x% Xdbba9frFj0-OqFfea0dXdd9vqaq-JfrVkFHe9pgea0dXdar-Jb9hs% 0dXdbPYxe9vr0-vr0-vqpWqaaeaabiGaciaacaqabeaadaqaaqGaaO% qaamaalaaabaGaaGymaaqaaiaaikdaaaGaciiBaiaac+gacaGGNbWe% xLMBb50ujbqeguuDJXwAKbacfaGae8hkaGIae8xmaeJae83kaSIaam% OyamaaBaaaleaacaWGUbaabeaakiaac+cacaWGHbWaaSbaaSqaaiaa% d6gaaeqaaOGae8xkaKIae83la8IaciiBaiaac+gacaGGNbGaamOyam% aaBaaaleaacaWGUbaabeaaaaa!5364!\[\frac{1}{2}\log (1 + b_n /a_n )/\log b_n \] if it tends to zero as n, and the probability of % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXafv3ySLgzGmvETj2BSbqefm0B1jxALjhiov2D% aebbfv3ySLgzGueE0jxyaibaiGc9yrFr0xXdbba91rFfpec8Eeeu0x% Xdbba9frFj0-OqFfea0dXdd9vqaq-JfrVkFHe9pgea0dXdar-Jb9hs% 0dXdbPYxe9vr0-vr0-vqpWqaaeaabiGaciaacaqabeaadaqaaqGaaO% qaaiabfc6aqnaaBaaaleaacaaIXaaabeaatCvAUfKttLearyqr1ngB% Prgaiuaakiab-HcaOiab-bdaWiab-XcaSiabg6HiLkab-LcaPiabgM% Iihlabfc6aqnaaBaaaleaacaaIYaaabeaakiab-HcaOiaadggadaWg% aaWcbaGaamOBaaqabaGccaGGSaGaamyyamaaBaaaleaacaWGUbaabe% aakiabgUcaRiaadkgadaWgaaWcbaGaamOBaaqabaGccqWFPaqkcqWF% 9aqpieaacaGFydaaaa!583C!\[\Pi _1 (0,\infty ) \cap \Pi _2 (a_n ,a_n + b_n ) = \O \]is asymptotic to % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXafv3ySLgzGmvETj2BSbqefm0B1jxALjhiov2D% aebbfv3ySLgzGueE0jxyaibaiGc9yrFr0xXdbba91rFfpec8Eeeu0x% Xdbba9frFj0-OqFfea0dXdd9vqaq-JfrVkFHe9pgea0dXdar-Jb9hs% 0dXdbPYxe9vr0-vr0-vqpWqaaeaabiGaciaacaqabeaadaqaaqGaaO% abaeqabaaabaGaam4yaiaacUfaciGGSbGaai4BaiaacEgatCvAUfKt% tLearyqr1ngBPrgaiuaacqWFOaakcaWGHbWaaSbaaSqaaiaad6gaae% qaaOGaey4kaSIaamOyamaaBaaaleaacaWGUbaabeaakiab-LcaPiab% -9caViab-XgaSjab-9gaVjab-DgaNjab-HcaOiaadggadaWgaaWcba% GaamOBaaqabaGccqGHRaWkcaaIYaGae8xkaKIae8xxa01aaWbaaSqa% beaacqWFTaqlcqWFXaqmcqWFVaWlcqWFYaGmaaaaaaa!5BAC!\[\begin{array}{l} \Pi _1 (0,\infty ) \cap \Pi _2 (a_n ,a_n + b_n ) = \O \\ c[\log (a_n + b_n )/log(a_n + 2)]^{ - 1/2} \\ \end{array}\], for some constant c, if it tends to a finite constant (1) as n. These results extend some results obtained by G. F. Lawler about the intersection properties of simple random walks in Z ⁴. By using similar arguments, we also get corresponding results for the intersections of Wiener sausages in four dimensions. In particular, a conjecture suggested by M. Aizenman, which describes nonintersection of independent Wiener sausages in R ⁴, is proven.Partly supported by AvH Foundation.     

Exceptional times and invariance for dynamical random walks

Consider a sequence of i.i.d. random variables. Associate to each X _i (0) an independent mean-one Poisson clock. Every time a clock rings replace that X-variable by an independent copy and restart the clock. In this way, we obtain i.i.d. stationary processes {X _i (t)} _{t ≥0} (i=1,2,···) whose invariant distribution is the law ν of X ₁(0). Benjamini et al. (2003) introduced the dynamical walk S _n (t)=X ₁(t)+···+X _n (t), and proved among other things that the LIL holds for n↦S _n (t) for all t. In other words, the LIL is dynamically stable. Subsequently (2004b), we showed that in the case that the X _i (0)'s are standard normal, the classical integral test is not dynamically stable. Presently, we study the set of times t when n↦S _n (t) exceeds a given envelope infinitely often. Our analysis is made possible thanks to a connection to the Kolmogorov ɛ-entropy. When used in conjunction with the invariance principle of this paper, this connection has other interesting by-products some of which we relate. We prove also that the infinite-dimensional process converges weakly in to the Ornstein–Uhlenbeck process in For this we assume only that the increments have mean zero and variance one. In addition, we extend a result of Benjamini et al. (2003) by proving that if the X _i (0)'s are lattice, mean-zero variance-one, and possess (2+ɛ) finite absolute moments for some ɛ>0, then the recurrence of the origin is dynamically stable. To prove this we derive a gambler's ruin estimate that is valid for all lattice random walks that have mean zero and finite variance. We believe the latter may be of independent interest. The research of D. Kh. is partially supported by a grant from the NSF.     

Combinatorial parameters in bargraphs

Bargraphs are non-intersecting lattice paths in with 3 allowed types of steps; up (0, 1), down (0, ?1) and horizontal (1, 0). They start at the origin with an up step and terminate immediately upon return to the x-axis. We unify the study of integer compositions (ordered partitions) with that of bargraph lattice paths by obtaining a single generating function for both these structures. We also obtain the asymptotic expected size of the underlying composition associated with an arbitrary bargraph as the semiperimeter tends to infinity (equivalently the expected value for the total area under the bargraph). In addition, the number of descents, the number of up steps and the number of level steps are found together with their asymptotic expressions for large semiperimeter.     

Biased random walks

How much can an imperfect source of randomness affect an algorithm? We examine several simple questions of this type concerning the long-term behavior of a random walk on a finite graph. In our setup, at each step of the random walk a “controller” can, with a certain small probability, fix the next step, thus introducing a bias. We analyze the extent to which the bias can affect the limit behavior of the walk. The controller is assumed to associate a real, nonnegative, “benefit” with each state, and to strive to maximize the long-term expected benefit. We derive tight bounds on the maximum of this objective function over all controller's strategies, and present polynomial time algorithms for computing the optimal controller strategy.     

Maxima of branching random walks vs. independent random walks

In recent years several authors have obtained limit theorems for the location of the right most particle in a supercritical branching random walk. In this paper we will consider analogous problems for an exponentially growing number of independent random walks. A comparison of our results with the known results of branching random walk then identifies the limit behaviors which are due to the number of particles and those which are determined by the branching structure.     

On massive sets for subordinated random walks

We study massive (reccurent) sets with respect to a certain random walk defined on the integer lattice , . Our random walk is obtained from the simple random walk S on by the procedure of discrete subordination. can be regarded as a discrete space and time counterpart of the symmetric α‐stable Lévy process in . In the case we show that some remarkable proper subsets of , e.g. the set of primes, are massive whereas some proper subsets of such as the Leitmann primes are massive/non‐massive depending on the function h. Our results can be regarded as an extension of the results of McKean (1961) about massiveness of the set of primes for the simple random walk in . In the case we study massiveness of thorns and their proper subsets. The case is presented in the recent paper Bendikov and Cygan 2 .     

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     

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     

Anomalous behaviour for the random corrections to the cumulants of random walks in fluctuating random media

The Central Limit Theorem for a model of discrete-time random walks on the lattice ℤ^ν in a fluctuating random environment was proved for almost-all realizations of the space-time nvironment, for all ν > 1 in [BMP1] and for all ν≥ 1 in [BBMP]. In [BMP1] it was proved that the random correction to the average of the random walk for ν≥ 3 is finite. In the present paper we consider the cases ν = 1,2 and prove the Central Limit Theorem as T→∞ for the random correction to the first two cumulants. The rescaling factor for theaverage is for ν = 1 and (ln T), for ν=2; for the covariance it is , ν = 1,2. Received: 25 November 1999 / Revised version: 7 June 2000 / Published online: 15 February 2001     

On the distributions of the lengths of the longest monotone subsequences in random words

We consider the distributions of the lengths of the longest weakly increasing and strongly decreasing subsequences in words of length N from an alphabet of k letters. (In the limit as k→∞ these become the corresponding distributions for permutations on N letters.) We find Toeplitz determinant representations for the exponential generating functions (on N) of these distribution functions and show that they are expressible in terms of solutions of Painlevé V equations. We show further that in the weakly increasing case the generating unction gives the distribution of the smallest eigenvalue in the k×k Laguerre random matrix ensemble and that the distribution itself has, after centering and normalizing, an N→∞ limit which is equal to the distribution function for the largest eigenvalue in the Gaussian Unitary Ensemble of k×k hermitian matrices of trace zero. Received: 9 September 1999 / Revised version: 24 May 2000 / Published online: 24 January 2001     

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     

Quadrature rule-based bounds for functions of adjacency matrices

Bounds for entries of matrix functions based on Gauss-type quadrature rules are applied to adjacency matrices associated with graphs. This technique allows to develop inexpensive and accurate upper and lower bounds for certain quantities (Estrada index, subgraph centrality, communicability) that describe properties of networks.     

Random walks and local cuts in graphs

For a specified subset S of vertices in a graph G we consider local cuts that separate a subset of S. We consider the local Cheeger constant which is the minimum Cheeger ratio over all subsets of S, and we examine the relationship between the local Cheeger constant and the Dirichlet eigenvalue of the induced subgraph on S. These relationships are summarized in a local Cheeger inequality. The proofs are based on the methods of establishing isoperimetric inequalities using random walks and the spectral methods for eigenvalues with Dirichlet boundary conditions.