Search ResultsShowing 1-20 of 42
-
arXiv:2208.12955 (Published 2022-08-27)
Strong transience for one-dimensional Markov chains with asymptotically zero drifts
Comments: 21 pagesCategories: math.PRFor near-critical, transient Markov chains on the non-negative integers in the Lamperti regime, where the mean drift at $x$ decays as $1/x$ as $x \to \infty$, we quantify degree of transience via existence of moments for conditional return times and for last exit times, assuming increments are uniformly bounded. Our proof uses a Doob $h$-transform, for the transient process conditioned to return, and we show that the conditioned process is also of Lamperti type with appropriately transformed parameters. To do so, we obtain an asymptotic expansion for the ratio of two return probabilities, evaluated at two nearby starting points; a consequence of this is that the return probability for the transient Lamperti process is a regularly-varying function of the starting point.
-
arXiv:2203.00966 (Published 2022-03-02)
Reflecting Brownian motion in generalized parabolic domains: explosion and superdiffusivity
Comments: 39 pages, 2 figuresCategories: math.PRFor a multidimensional driftless diffusion in an unbounded, smooth, sub-linear generalized parabolic domain, with oblique reflection from the boundary, we give natural conditions under which either explosion occurs, if the domain narrows sufficiently fast at infinity, or else there is superdiffusive transience, which we quantify with a strong law of large numbers. For example, in the case of a planar domain, explosion occurs if and only if the area of the domain is finite. We develop and apply novel semimartingale criteria for studying explosions and establishing strong laws, which are of independent interest.
-
Stochastic billiards with Markovian reflections in generalized parabolic domains
Comments: 42 pages, 4 figures; v2: some clarifications, corrections, and strengthened results on passage-time momentsCategories: math.PRWe study recurrence and transience for a particle that moves at constant velocity in the interior of an unbounded planar domain, with random reflections at the boundary governed by a Markov kernel producing outgoing angles from incoming angles. Our domains have a single unbounded direction and sublinear growth. We characterize recurrence in terms of the reflection kernel and growth rate of the domain. The results are obtained by transforming the stochastic billiards model to a Markov chain on a half-strip $\mathbb{R}_+ \!\times S$ where $S$ is a compact set. We develop the recurrence classification for such processes in the near-critical regime in which drifts of the $\mathbb{R}_+$ component are of generalized Lamperti type, and the $S$ component is asymptotically Markov; this extends earlier work that dealt with finite $S$.
-
arXiv:2010.00671 (Published 2020-10-01)
Deposition, diffusion, and nucleation on an interval
Comments: 47 pages, 3 figuresCategories: math.PRMotivated by nanoscale growth of ultra-thin films, we study a model of deposition, on an interval substrate, of particles that perform Brownian motions until any two meet, when they nucleate to form a static island, which acts as an absorbing barrier to subsequent particles. This is a continuum version of a lattice model popular in the applied literature. We show that the associated interval-splitting process converges in the sparse deposition limit to a Markovian process (in the vein of Brennan and Durrett) governed by a splitting density with a compact Fourier series expansion but, apparently, no simple closed form. We show that the same splitting density governs the fixed deposition rate, large time asymptotics of the normalized gap distribution, so these asymptotics are independent of deposition rate. The splitting density is derived by solving an exit problem for planar Brownian motion from a right-angled triangle, extending work of Smith and Watson.
-
arXiv:2003.08108 (Published 2020-03-18)
Angular asymptotics for random walks
Comments: 23 pagesCategories: math.PRWe study the set of directions asymptotically explored by a spatially homogeneous random walk in $d$-dimensional Euclidean space. We survey some pertinent results of Kesten and Erickson, make some further observations, and present some examples. We also explore links to the asymptotics of one-dimensional projections, and to the growth of the convex hull of the random walk.
-
arXiv:2003.01684 (Published 2020-03-03)
Cutpoints of non-homogeneous random walks
Comments: 20 pagesCategories: math.PRWe give conditions under which near-critical stochastic processes on the half-line have infinitely many or finitely many cutpoints, generalizing existing results on nearest-neighbour random walks to adapted processes with bounded increments satisfying appropriate conditional increment moments conditions. We apply one of these results to deduce that a class of transient zero-drift Markov chains in $\mathbb{R}^d$, $d \geq 2$, possess infinitely many separating annuli, generalizing previous results on spatially homogeneous random walks.
-
arXiv:2001.06685 (Published 2020-01-18)
Reflecting random walks in curvilinear wedges
Comments: 30 pages, 3 figuresCategories: math.PRWe study a random walk (Markov chain) in an unbounded planar domain whose boundary is described by two curves of the form $x_2 = a^+ x_1^{\beta^+}$ and $x_2 = -a^- x_1^{\beta^-}$, with $x_1 \geq 0$. In the interior of the domain, the random walk has zero drift and a given increment covariance matrix. From the vicinity of the upper and lower sections of the boundary, the walk drifts back into the interior at a given angle $\alpha^+$ or $\alpha^-$ to the relevant inwards-pointing normal vector. Here we focus on the case where $\alpha^+$ and $\alpha^-$ are equal but opposite, which includes the case of normal reflection. For $0 \leq \beta^+, \beta^- < 1$, we identify the phase transition between recurrence and transience, depending on the model parameters, and quantify recurrence via moments of passage times.
-
arXiv:1902.09812 (Published 2019-02-26)
Random walks avoiding their convex hull with a finite memory
Comments: 29 pages, 2 figuresCategories: math.PRFix integers $d \geq 2$ and $k\geq d-1$. Consider a random walk $X_0, X_1, \ldots$ in $\mathbb{R}^d$ in which, given $X_0, X_1, \ldots, X_n$ ($n \geq k$), the next step $X_{n+1}$ is uniformly distributed on the unit ball centred at $X_n$, but conditioned that the line segment from $X_n$ to $X_{n+1}$ intersects the convex hull of $\{0, X_{n-k}, \ldots, X_n\}$ only at $X_n$. For $k = \infty$ this is a version of the model introduced by Angel et al., which is conjectured to be ballistic, i.e., to have a limiting speed and a limiting direction. We establish ballisticity for the finite-$k$ model, and comment on some open problems. In the case where $d=2$ and $k=1$, we obtain the limiting speed explicitly: it is $8/(9\pi^2)$.
-
arXiv:1806.07166 (Published 2018-06-19)
Markov chains with heavy-tailed increments and asymptotically zero drift
Categories: math.PRWe study the recurrence/transience phase transition for Markov chains on $\mathbb{R}_+$, $\mathbb{R}$, and $\mathbb{R}^2$ whose increments have heavy tails with exponent in $(1,2)$ and asymptotically zero mean. This is the infinite-variance analogue of the classical Lamperti problem. On $\mathbb{R}_+$, for example, we show that if the tail of the positive increments is about $c y^{-\alpha}$ for an exponent $\alpha \in (1,2)$ and if the drift at $x$ is about $b x^{-\gamma}$, then the critical regime has $\gamma = \alpha -1$ and recurrence/transience is determined by the sign of $b + c\pi \textrm{cosec} (\pi \alpha)$. On $\mathbb{R}$ we classify whether transience is directional or oscillatory, and extend an example of Rogozin \& Foss to a class of transient martingales which oscillate between $\pm \infty$. In addition to our recurrence/transience results, we also give sharp results on the existence/non-existence of moments of passage times.
-
arXiv:1803.08293 (Published 2018-03-22)
The convex hull of a planar random walk: perimeter, diameter, and shape
Comments: 25 pagesJournal: Electronic Journal of Probability, Vol. 23 (2018), article 131DOI: 10.1214/18-EJP257Categories: math.PRKeywords: planar random walk, convex hull, unit-diameter compact convex set containing, distributional limit theorems, non-zero mean driftTags: journal articleWe study the convex hull of the first $n$ steps of a planar random walk, and present large-$n$ asymptotic results on its perimeter length $L_n$, diameter $D_n$, and shape. In the case where the walk has a non-zero mean drift, we show that $L_n / D_n \to 2$ a.s., and give distributional limit theorems and variance asymptotics for $D_n$, and in the zero-drift case we show that the convex hull is infinitely often arbitrarily well-approximated in shape by any unit-diameter compact convex set containing the origin, and then $\liminf_{n \to \infty} L_n/D_n =2$ and $\limsup_{n \to \infty} L_n /D_n = \pi$, a.s. Among the tools that we use is a zero-one law for convex hulls of random walks.
-
arXiv:1801.07882 (Published 2018-01-24)
Invariance principle for non-homogeneous random walks
Comments: 36 pagesCategories: math.PRWe prove an invariance principle for a class of zero-drift spatially non-homogeneous random walks in $\mathbb{R}^d$, which may be recurrent in any dimension. The limit $\mathcal{X}$ is an elliptic martingale diffusion, which may be point-recurrent at the origin for any $d\geq2$. To characterise $\mathcal{X}$, we introduce a (non-Euclidean) Riemannian metric on the unit sphere in $\mathbb{R}^d$ and use it to express a related spherical diffusion as a Brownian motion with drift. This representation allows us to establish the skew-product decomposition of the excursions of $\mathcal{X}$ and thus develop the excursion theory of $\mathcal{X}$ without appealing to the strong Markov property. This leads to the uniqueness in law of the stochastic differential equation for $\mathcal{X}$ in $\mathbb{R}^d$, whose coefficients are discontinuous at the origin. Using the Riemannian metric we can also detect whether the angular component of the excursions of $\mathcal{X}$ is time-reversible. If so, the excursions of $\mathcal{X}$ in $\mathbb{R}^d$ generalise the classical Pitman-Yor splitting-at-the-maximum property of Bessel excursions.
-
arXiv:1712.03026 (Published 2017-12-08)
The critical greedy server on the integers is recurrent
Comments: 25 pagesCategories: math.PREach site of $\mathbb{Z}$ hosts a queue with arrival rate $\lambda$. A single server, starting at the origin, serves its current queue at rate $\mu$ until that queue is empty, and then moves to the longest neighbouring queue. In the critical case $\lambda = \mu$, we show that the server returns to every site infinitely often. We also give a sharp iterated logarithm result for the server's position. Important ingredients in the proofs are that the times between successive queues being emptied exhibit doubly exponential growth, and that the probability that the server changes its direction is asymptotically equal to $1/4$.
-
arXiv:1708.07683 (Published 2017-08-25)
A radial invariance principle for non-homogeneous random walks
Comments: 10 pagesCategories: math.PRConsider non-homogeneous zero-drift random walks in $\mathbb{R}^d$, $d \geq 2$, with the asymptotic increment covariance matrix $\sigma^2 (\mathbf{u})$ satisfying $\mathbf{u}^\top \sigma^2 (\mathbf{u}) \mathbf{u} = U$ and $\mathrm{tr}\ \sigma^2 (\mathbf{u}) = V$ in all in directions $\mathbf{u}\in\mathbb{S}^{d-1}$ for some positive constants $U<V$. In this paper we establish weak convergence of the radial component of the walk to a Bessel process with dimension $V/U$. This can be viewed as an extension of an invariance principle of Lamperti.
-
arXiv:1708.04470 (Published 2017-08-15)
On the centre of mass of a random walk
Comments: 25 pages, 1 colour figureCategories: math.PRFor a random walk $S_n$ on $\mathbb{R}^d$ we study the asymptotic behaviour of the associated centre of mass process $G_n = n^{-1} \sum_{i=1}^n S_i$. For lattice distributions we give conditions for a local limit theorem to hold. We prove that if the increments of the walk have zero mean and finite second moment, $G_n$ is recurrent if $d=1$ and transient if $d \geq 2$. In the transient case we show that $G_n$ has diffusive rate of escape. These results extend work of Grill, who considered simple symmetric random walk. We also give a class of random walks with symmetric heavy-tailed increments for which $G_n$ is transient in $d=1$.
-
arXiv:1610.00881 (Published 2016-10-04)
Heavy-tailed random walks on complexes of half-lines
Comments: 35 pages, 2 figuresCategories: math.PRWe study a random walk on a complex of finitely many half-lines joined at a common origin; jumps are heavy-tailed and of two types, either one-sided (towards the origin) or two-sided (symmetric). Transmission between half-lines via the origin is governed by an irreducible Markov transition matrix, with associated stationary distribution $\mu_k$. If $\chi_k$ is $1$ for one-sided half-lines $k$ and $1/2$ for two-sided half-lines, and $\alpha_k$ is the tail exponent of the jumps on half-line $k$, we show that the recurrence classification for the case where all $\alpha_k \chi_k \in (0,1)$ is determined by the sign of $\sum_k \mu_k \cot ( \chi_k \pi \alpha_k )$. In the case of two half-lines, the model fits naturally on $\mathbb{R}$ and is a version of the oscillating random walk of Kemperman. In that case, the cotangent criterion for recurrence becomes linear in $\alpha_1$ and $\alpha_2$; our general setting exhibits the essential non-linearity in the cotangent criterion. For the general model, we also show existence and non-existence of polynomial moments of return times. Our moments results are sharp (and new) for several cases of the oscillating random walk; they are apparently even new for the case of a homogeneous random walk on $\mathbb{R}$ with symmetric increments of tail exponent $\alpha \in (1,2)$.
-
arXiv:1512.04242 (Published 2015-12-14)
Non-homogeneous random walks on a half strip with generalized Lamperti drifts
We study a Markov chain on $\mathbb{R}_+ \times S$, where $\mathbb{R}_+$ is the non-negative real numbers and $S$ is a finite set, in which when the $\mathbb{R}_+$-coordinate is large, the $S$-coordinate of the process is approximately Markov with stationary distribution $\pi_i$ on $S$. If $\mu_i(x)$ is the mean drift of the $\mathbb{R}_+$-coordinate of the process at $(x,i) \in \mathbb{R}_+ \times S$, we study the case where $\sum_{i} \pi_i \mu_i (x) \to 0$, which is the critical regime for the recurrence-transience phase transition. If $\mu_i(x) \to 0$ for all $i$, it is natural to study the \emph{Lamperti} case where $\mu_i(x) = O(1/x)$; in that case the recurrence classification is known, but we prove new results on existence and non-existence of moments of return times. If $\mu_i (x) \to d_i$ for $d_i \neq 0$ for at least some $i$, then it is natural to study the \emph{generalized Lamperti} case where $\mu_i (x) = d_i + O (1/x)$. By exploiting a transformation which maps the generalized Lamperti case to the Lamperti case, we obtain a recurrence classification and existence of moments results for the former. The generalized Lamperti case is seen to be more subtle, as the recurrence classification depends on correlation terms between the two coordinates of the process.
-
arXiv:1506.08541 (Published 2015-06-29)
Anomalous recurrence properties of many-dimensional zero-drift random walks
Comments: 22 pages, 4 figuresCategories: math.PRFamously, a $d$-dimensional, spatially homogeneous random walk whose increments are non-degenerate, have finite second moments, and have zero mean is recurrent if $d \in \{1,2\}$ but transient if $d \geq 3$. Once spatial homogeneity is relaxed, this is no longer true. We study a family of zero-drift spatially non-homogeneous random walks (Markov processes) whose increment covariance matrix is asymptotically constant along rays from the origin, and which, in any ambient dimension $d \geq 2$, can be adjusted so that the walk is either transient or recurrent. Natural examples are provided by random walks whose increments are supported on ellipsoids that are symmetric about the ray from the origin through the walk's current position; these \emph{elliptic random walks} generalize the classical homogeneous Pearson--Rayleigh walk (the spherical case). Our proof of the recurrence classification is based on fundamental work of Lamperti.
-
arXiv:1408.4560 (Published 2014-08-20)
Convex hulls of random walks and their scaling limits
Comments: 19 pages, 1 colour figureCategories: math.PRFor the perimeter length and the area of the convex hull of the first $n$ steps of a planar random walk, we study $n \to \infty$ mean and variance asymptotics and establish non-Gaussian distributional limits. Our results apply to random walks with drift (for the area) and walks with no drift (for both area and perimeter length) under mild moments assumptions on the increments. These results complement and contrast with previous work which showed that the perimeter length in the case with drift satisfies a central limit theorem. We deduce these results from weak convergence statements for the convex hulls of random walks to scaling limits defined in terms of convex hulls of certain Brownian motions. We give bounds that confirm that the limiting variances in our results are non-zero.
-
arXiv:1402.2558 (Published 2014-02-11)
Non-homogeneous random walks on a semi-infinite strip
Comments: 27 pagesJournal: Stochastic Processes and their Applications, Vol. 124 (2014), no. 10, p. 3179-3205Categories: math.PRKeywords: non-homogeneous random walks, semi-infinite strip, markov chain, recurrence phase transitions, increment moment parametersTags: journal articleWe study the asymptotic behaviour of Markov chains $(X_n,\eta_n)$ on $\mathbb{Z}_+ \times S$, where $\mathbb{Z}_+$ is the non-negative integers and $S$ is a finite set. Neither coordinate is assumed to be Markov. We assume a moments bound on the jumps of $X_n$, and that, roughly speaking, $\eta_n$ is close to being Markov when $X_n$ is large. This departure from much of the literature, which assumes that $\eta_n$ is itself a Markov chain, enables us to probe precisely the recurrence phase transitions by assuming asymptotically zero drift for $X_n$ given $\eta_n$. We give a recurrence classification in terms of increment moment parameters for $X_n$ and the stationary distribution for the large-$X$ limit of $\eta_n$. In the null case we also provide a weak convergence result, which demonstrates a form of asymptotic independence between $X_n$ (rescaled) and $\eta_n$. Our results can be seen as generalizations of Lamperti's results for non-homogeneous random walks on $\mathbb{Z}_+$ (the case where $S$ is a singleton). Motivation arises from modulated queues or processes with hidden variables where $\eta_n$ tracks an internal state of the system.
-
arXiv:1311.3776 (Published 2013-11-15)
Phase transitions for random geometric preferential attachment graphs
Comments: 28 pagesCategories: math.PRWe study an evolving spatial network in which sequentially arriving vertices are joined to existing vertices at random according to a rule that combines preference according to degree with preference according to spatial proximity. We investigate phase transitions in graph structure as the relative weighting of these two components of the attachment rule is varied. Previous work of one of the authors showed that when the geometric component is weak, the limiting degree sequence of the resulting graph coincides with that of the standard Barab\'asi--Albert preferential attachment model. We show that at the other extreme, in the case of a sufficiently strong geometric component, the limiting degree sequence coincides with that of a purely geometric model, the on-line nearest-neighbour graph, which is of interest in its own right and for which we prove some extensions of known results. We also show the presence of an intermediate regime, in which the behaviour differs significantly from both the on-line nearest-neighbour graph and the Barab\'asi--Albert model; in this regime, we obtain a stretched exponential upper bound on the degree sequence. Our results lend some mathematical support to simulation studies of Manna and Sen, while proving that the power law to stretched exponential phase transition occurs at a different point from the one conjectured by those authors.