Renewal theory for iterated perturbed random walks on a general branching process tree: intermediate generations

An iterated perturbed random walk is a sequence of point processes defined by the birth times of individuals in subsequent generations of a general branching process provided that the birth times of the first generation individuals are given by a perturbed random walk. We prove counterparts of the classical renewal-theoretic results (the elementary renewal theorem, Blackwell’s theorem, and the key renewal theorem) for the number of jth-generation individuals with birth times $\leq t$ , when $j,t\to\infty$ and $j(t)={\textrm{o}}\big(t^{2/3}\big)$ . According to our terminology, such generations form a subset of the set of intermediate generations.

Arcsine laws for random walks generated from random permutations with applications to genomics

A classical result for the simple symmetric random walk with 2n steps is that the number of steps above the origin, the time of the last visit to the origin, and the time of the maximum height all have exactly the same distribution and converge when scaled to the arcsine law. Motivated by applications in genomics, we study the distributions of these statistics for the non-Markovian random walk generated from the ascents and descents of a uniform random permutation and a Mallows(q) permutation and show that they have the same asymptotic distributions as for the simple random walk. We also give an unexpected conjecture, along with numerical evidence and a partial proof in special cases, for the result that the number of steps above the origin by step 2n for the uniform permutation generated walk has exactly the same discrete arcsine distribution as for the simple random walk, even though the other statistics for these walks have very different laws. We also give explicit error bounds to the limit theorems using Stein’s method for the arcsine distribution, as well as functional central limit theorems and a strong embedding of the Mallows(q) permutation which is of independent interest.

Finite automata, probabilistic method, and occurrence enumeration of a pattern in words and permutations

The main theme of this paper is the enumeration of the order-isomorphic occurrence of a pattern in words and permutations. We mainly focus on asymptotic properties of the sequence f r v ( k , n ) , the number of n-array k-ary words that contain a given pattern v exactly r times. In addition, we study the asymptotic behavior of the random variable X_n , the number of pattern occurrences in a random n-array word. The two topics are closely related through the identity P ( X n = r ) = 1 k n f r v ( k , n ) . In particular, we show that for any r ≥ 0, the Stanley-Wilf sequence ( f r v ( k , n ) ) 1 ∕ n converges to a limit independent of r, and determine the value of the limit. We then obtain several limit theorems for the distribution of X_n , including a central limit theorem, large deviation estimates, and the exact growth rate of the entropy of X_n . Furthermore, we introduce a concept of weak avoidance and link it to a certain family of non-product measures on words that penalize pattern occurrences but do not forbid them entirely. We analyze this family of probability measures in a small parameter regime, where the distributions can be understood as a perturbation of a uniform measure. Finally, we extend some of our results for words, including the one regarding the equivalence of the limits of the Stanley-Wilf sequences, to pattern occurrences in permutations.

On nested infinite occupancy scheme in random environment

We consider an infinite balls-in-boxes occupancy scheme with boxes organised in nested hierarchy, and random probabilities of boxes defined in terms of iterated fragmentation of a unit mass. We obtain a multivariate functional limit theorem for the cumulative occupancy counts as the number of balls approaches infinity. In the case of fragmentation driven by a homogeneous residual allocation model our result generalises the functional central limit theorem for the block counts in Ewens’ and more general regenerative partitions.