Search

A switching random walk, commonly known under the misnomer `oscillating random walk', is a real-valued Markov chain such that the distribution of its increments depends only on the sign of the current position. In this note we find invariant measures for such chains. In the particular case where the chain is an actual random walk, our proof naturally relates its stationarity relative to the Lebesgue measure to stationarity of the renewal processes of its ascending and descending ladder heights.

For a Markov chain $Y$ with values in a Polish space, consider the entrance chain obtained by sampling $Y$ at the moments when it enters a fixed set $A$ from its complement $A^c$. Similarly, consider the exit chain, obtained by sampling $Y$ at the exit times from $A^c$ to $A$. We use the method of inducing from ergodic theory to study invariant measures of these two types of Markov chains in the case when the initial chain $Y$ has a known invariant measure. We give explicit formulas for invariant measures of the entrance and exit chains under certain recurrence-type assumptions on $A$ and $A^c$, which apply even for transient chains. Then we study uniqueness and ergodicity of these invariant measures assuming that $Y$ is topologically recurrent, topologically irreducible, and weak Feller. We give applications to random walks in $R^d$, which we regard as "stationary" Markov chains started under the Lebesgue measure. We are mostly interested in dimension one, where we study the Markov chain of overshoots above the zero level of a random walk that oscillates between $-\infty$ and $+\infty$. We show that this chain is ergodic, and use this result to prove a central limit theorem for the number of level crossings for random walks with zero mean and finite variance of increments., Comment: There is an overlap with arXiv:1808.05010 but this version differs significantly. The exposition was streamlined and many non-new and non-essential results were removed

We study the asymptotic behaviour of the most likely trajectories of a planar random walk that result in large deviations of the area of their convex hull. If the Laplace transform of the increments is finite on $R^2$, such a scaled limit trajectory $h$ solves the inhomogeneous anisotropic isoperimetric problem for the convex hull, where the usual length of $h$ is replaced by the large deviations rate functional $\int_0^1 I(h'(t)) dt$ and $I$ is the rate function of the increments. Assuming that the distribution of increments is not supported on a half-plane, we show that the optimal trajectories are convex and satisfy the Euler-Lagrange equation, which we solve explicitly for every $I$. The shape of these trajectories resembles the optimizers in the isoperimetric inequality for the Minkowski plane, found by Busemann (1947).

We study the probability that an AR(1) Markov chain $X_{n+1}=aX_n+\xi_{n+1}$, where $a\in(0,1)$ is a constant, stays non-negative for a long time. We find the exact asymptotics of this probability and the weak limit of $X_n$ conditioned to stay non-negative, assuming that the i.i.d.\ innovations $\xi_n$ take only two values $\pm1$ and $a \le \frac23$. This limiting distribution is quasi-stationary. It has no atoms and is singular with respect to the Lebesgue measure when $\frac12< a \le \frac23$, except for the case $a=\frac23$ and $\mathbf{P}(\xi_n=1)=\frac12$, where this distribution is uniform on the interval $[0,3]$. This is similar to the properties of Bernoulli convolutions. It turns out that for the $\pm1 $ innovations there is a close connection between $X_n$ killed at exiting $[0, \infty)$ and the classical dynamical system defined by the piecewise linear mapping $x \mapsto \frac1a x + \frac12 \pmod 1$. Namely, the trajectory of this system started at $X_n$ deterministically recovers the values of the killed chain in reversed time! We use this property to construct a suitable Banach space, where the transition operator of the killed chain has the compactness properties that let us apply a conventional argument of Perron--Frobenius type. The difficulty in finding such space stems from discreteness of the innovations.

We give a necessary and sufficient condition for strict convexity of the rate function of a random vector in $R^d$. This condition is always satisfied when the random vector has finite Laplace transform. We also completely describe the effective domain of the rate function under a weaker condition., Comment: This is version to be published. Some minor changes were made and a few references were added. The main result from the previous version was split into two parts, Theorems 1 and 2 in this version

We consider the classical Skorokhod space $D[0,1]$ and the space of continuous functions $C[0,1]$ equipped with the standard Skorokhod distance $\rho$. It is well known that neither $(D[0,1],\rho)$ nor $(C[0,1],\rho)$ is complete. We provide an explicit description of the corresponding completions. The elements of these completions can be regarded as usual functions on $[0,1]$ except for a countable number of instants where their values vary "instantly"., Comment: This version will be published in Electronic Communications in Probability

We prove distributional limit theorems for the length of the largest convex minorant of a one-dimensional random walk with independent identically distributed increments. Depending on the increment law, there are several regimes with different limit distributions for this length. Among other tools, a representation of the convex minorant of a random walk in terms of uniform random permutations is utilized., Comment: 21 pages, 1 figure, to appear in the Electronic Journal of Probability

In 2013 A.A. Borovkov and A.A. Mogulskii proved a weaker-than-standard "metric" large deviations principle (LDP) for trajectories of random walks in $R^d$ whose increments have the Laplace transform finite in a neighbourhood of zero. We prove that general metric LDPs are preserved under uniformly continuous mappings. This allows us to transform the result of Borovkov and Mogulskii into standard LDPs. We also give an explicit integral representation of the rate function they found. As an application, we extend the classical Cram'er theorem by proving an LPD for kernel-weighted sums of i.i.d. random vectors in $R^d$., Comment: This is a version to be published. Proposition 2.1 added. Section 3 had a number of new results added. An error was fixed -- the M_1 topology and the space BV_0[0,1] were replaced throughout by M_1' and BV[0,1], respectively. Minor changes were made throughout

We prove that for a random walk on the real line whose increments have zero mean and are either integer-valued or spread out (i.e. the distributions of the steps of the walk are eventually non-singular), the Markov chain of overshoots above a fixed level converges in total variation to its stationary distribution. We find the explicit form of this distribution heuristically and then prove its invariance using a time-reversal argument. If, in addition, the increments of the walk are in the domain of attraction of a non-one-sided $\alpha$-stable law with index $\alpha\in(1,2)$ (resp. have finite variance), we establish geometric (resp. uniform) ergodicity for the Markov chain of overshoots. All the convergence results above are also valid for the Markov chain obtained by sampling the walk at the entrance times into an interval., Comment: arXiv admin note: text overlap with arXiv:1808.05010

It was shown by E. Gluskin and V.D. Milman in [GAFA Lecture Notes in Math. 1807, 2003] that the classical arithmetic-geometric mean inequality can be reversed (up to a multiplicative constant) with high probability, when applied to coordinates of a point chosen with respect to the surface unit measure on a high-dimensional Euclidean sphere. We present here two asymptotic refinements of this phenomenon in the more general setting of the surface probability measure on a high-dimensional $\ell_p$-sphere, and also show that sampling the point according to either the cone probability measure on $\ell_p$ or the uniform distribution on the ball enclosed by $\ell_p$ yields the same results. First, we prove a central limit theorem, which allows us to identify the precise constants in the reverse inequality. Second, we prove the large deviations counterpart to the central limit theorem, thereby describing the asymptotic behavior beyond the Gaussian scale, and identify the rate function., Comment: 15 pages, 1 figure

For a Markov chain $Y$ with values in a Polish space, consider the entrance Markov chain obtained by sampling $Y$ at the moments when it enters a fixed set $A$ from its complement $A^c$. Similarly, consider the exit Markov chain, obtained by sampling $Y$ at the exit times from $A^c$ to $A$. This paper provides a framework for analysing invariant measures of these two types of Markov chains in the case when the initial chain $Y$ has a known $\sigma$-finite invariant measure. Under certain recurrence-type assumptions ($Y$ can be transient), we give explicit formulas for invariant measures of these chains. Then we study their uniqueness and ergodicity assuming that $Y$ is topologically recurrent, irreducible, and weak Feller. Our approach is based on the technique of inducing from infinite ergodic theory. This also yields, in a natural way, the versions of the results above (provided in the paper) for the classical induced Markov chains. We give applications to random walks in $R^d$, which we regard as "stationary" Markov chains started under the Lebesgue measure. We are mostly interested in dimension one, where we study the Markov chain of overshoots above the zero level of a random walk that oscillates between $-\infty$ and $+\infty$. We show that this chain is ergodic, and use this result to prove a central limit theorem for the number of level crossings for random walks with zero mean and finite variance of increments., Comment: Structure of the paper revised; title updated; new results added to Section 2

We show how increasing returns to scale in urban scaling can artificially emerge, systematically and predictably, without any sorting or positive externalities. We employ a model where individual productivities are independent and identically distributed lognormal random variables across all cities. We use extreme value theory to demonstrate analytically the paradoxical emergence of increasing returns to scale when the variance of log-productivity is larger than twice the log-size of the population size of the smallest city in a cross-sectional regression. Our contributions are to derive an analytical prediction for the artificial scaling exponent arising from this mechanism and to develop a simple statistical test to try to tell whether a given estimate is real or an artifact. Our analytical results are validated analyzing simulations and real microdata of wages across municipalities in Colombia. We show how an artificial scaling exponent emerges in the Colombian data when the sizes of random samples of workers per municipality are $1\%$ or less of their total size., Comment: 29 pages, 9 figures, 2 tables. Environment and Planning B: Urban Analytics and City Science (2020)

Consider a sequence of partial sums $S_i= \xi_1+\dots+\xi_i$, $1\leq i\leq n$, starting at $S_0=0$, whose increments $\xi_1,\dots,\xi_n$ are random vectors in $\mathbb R^d$, $d\leq n$. We are interested in the properties of the convex hull $C_n:=\mathrm{Conv}(S_0,S_1,\dots,S_n)$. Assuming that the tuple $(\xi_1,\dots,\xi_n)$ is exchangeable and a certain general position condition holds, we prove that the expected number of $k$-dimensional faces of $C_n$ is given by the formula $$ \mathbb E [f_k(C_n)] = \frac{2\cdot k!}{n!} \sum_{l=0}^{\infty}\genfrac{[}{]}{0pt}{}{n+1}{d-2l} \genfrac{\{}{\}}{0pt}{}{d-2l}{k+1}, $$ for all $0\leq k \leq d-1$, where $\genfrac{[}{]}{0pt}{}{n}{m}$ and $\genfrac{\{}{\}}{0pt}{}{n}{m}$ are Stirling numbers of the first and second kind, respectively. Further, we compute explicitly the probability that for given indices $0\leq i_1<\dots

Consider a random walk $S_i= \xi_1+\ldots+\xi_i$, $i\in\mathbb N$, whose increments $\xi_1,\xi_2,\ldots$ are independent identically distributed random vectors in $\mathbb R^d$ such that $\xi_1$ has the same law as $-\xi_1$ and $\mathbb P[\xi_1\in H] = 0$ for every affine hyperplane $H\subset \mathbb R^d$. Our main result is the distribution-free formula $$ \mathbb E \left[\sum_{1\leq i_1 < \ldots < i_k\leq n} 1_{\{0\notin \text{conv}(S_{i_1},\ldots, S_{i_k})\}}\right] = 2 \binom n k \frac {B(k, d-1) + B(k, d-3) +\ldots} {2^k k!}, $$ where the $B(k,j)$'s are defined by their generating function $$ (t+1) (t+3) \ldots (t+2k-1) = \sum_{j=0}^{k} B(k,j) t^j. $$ The expected number of $k$-tuples above admits the following geometric interpretation: it is the expected number of $k$-dimensional faces of a randomly and uniformly sampled open Weyl chamber of type $B_n$ that are not intersected by a generic linear subspace $L\subset \mathbb R^n$ of codimension $d$. The case $d=1$ turns out to be equivalent to the classical discrete arcsine law for the number of positive terms in a one-dimensional random walk with continuous symmetric distribution of increments. We also prove similar results for random bridges with no central symmetry assumption required., Comment: 25 pages, no figures

We prove large deviations principles (LDPs) for the perimeter and the area of the convex hull of a planar random walk with finite Laplace transform of its increments. We give explicit upper and lower bounds for the rate function of the perimeter in terms of the rate function of the increments. These bounds coincide and thus give the rate function for a wide class of distributions which includes the Gaussians and the rotationally invariant ones. For random walks with such increments, large deviations of the perimeter are attained by the trajectories that asymptotically align into line segments. However, line segments may not be optimal in general. Furthermore, we find explicitly the rate function of the area of the convex hull for random walks with rotationally invariant distribution of increments. For such walks, which necessarily have zero mean, large deviations of the area are attained by the trajectories that asymptotically align into half-circles. For random walks with non-zero mean increments, we find the rate function of the area for Gaussian walks with drift. Here the optimal limit shapes are elliptic arcs if the covariance matrix of increments is non-degenerate and parabolic arcs if otherwise. The above results on convex hulls of Gaussian random walks remain valid for convex hulls of planar Brownian motions of all possible parameters. Moreover, we extend the LDPs for the perimeter and the area of convex hulls to general Levy processes with finite Laplace transform., Comment: This is a version to be published. Some minor changes were made throughout

We study the lengths of curves passing through a fixed number of points on the boundary of a convex shape in the plane. We show that for any convex shape $K$, there exist four points on the boundary of $K$ such that the length of any curve passing through these points is at least half of the perimeter of $K$. It is also shown that the same statement does not remain valid with the additional constraint that the points are extreme points of $K$. Moreover, the factor $\frac12$ cannot be achieved with any fixed number of extreme points. We conclude the paper with few other inequalities related to the perimeter of a convex shape., Comment: 7 pages, 8 figures

We give an explicit formula for the probability that the convex hull of an $n$-step random walk in $R^d$ does not contain the origin, under the assumption that the distribution of increments of the walk is centrally symmetric and puts no mass on affine hyperplanes. This extends the formula by Sparre Andersen (1949) for the probability that such random walk in dimension one stays positive. Our result is distribution-free, that is, the probability does not depend on the distribution of increments. This probabilistic problem is shown to be equivalent to either of the two geometric ones: 1) Find the number of Weyl chambers of type $B_n$ intersected by a generic linear subspace of $R^n$ of codimension $d$; 2) Find the conic intrinsic volumes of a Weyl chamber of type $B_n$. We solve the first geometric problem using the theory of hyperplane arrangements. A by-product of our method is a new simple proof of the general formula by Klivans and Swartz (2011) relating the coefficients of the characteristic polynomial of a linear hyperplane arrangement to the conic intrinsic volumes of the chambers constituting its complement. We obtain analogous distribution-free results for Weyl chambers of type $A_{n-1}$ (yielding the probability of absorption of the origin by the convex hull of a generic random walk bridge), type $D_n$, and direct products of Weyl chambers (yielding the absorption probability for the joint convex hull of several random walks or bridges). The simplest case of products of the form $B_1\times \dots \times B_1$ recovers the Wendel formula (1962) for the probability that the convex hull of an i.i.d. multidimensional sample chosen from a centrally symmetric distribution does not contain the origin. We also give an asymptotic analysis of the obtained absorption probabilities as $n \to \infty$, in both cases of fixed and increasing dimension $d$., Comment: Proof of Lemma 3.5 was corrected and fully rewritten; abstract shortened; minor changes added

This paper gives a simple proof of a limit theorem for the lenght of the largest interval straddling a fixed number of i.i.d. points uniformly disributed on a unit interval. The key step in our argument is a classical theorem of Watson (1954) on the maxima of m-dependent stationary stochastic sequences.

Let $S_k$ be a random walk in $R^d$ such that its distribution of increments does not assign mass to hyperplanes. We study the probability $p_n$ that the convex hull $conv (S_1, \ldots , S_n)$ of the first $n$ steps of the walk does not include the origin. By providing an explicit formula, we show that for planar symmetrically distributed random walks, $p_n$ does not depend on the distribution of increments. This extends the well known result by Sparre Andersen (1949) that a one-dimensional random walk satisfying the above continuity and symmetry assumptions stays positive with a distribution-free probability. We also find the asymptotics of $p_n$ as $n \to \infty$ for any planar random walk with zero mean square-integrable increments. We further developed our approach from the planar case to study a wide class of geometric characteristics of convex hulls of random walks in any dimension $d \ge 2$. In particular, we give formulas for the expected value of the number of faces, the volume, the surface area, and other intrinsic volumes, including the following multidimensional generalization of the Spitzer--Widom formula (1961) on the perimeter of planar walks: $$ E V_1 (conv(0, S_1, \dots, S_n)) = \sum_{k=1}^n \frac{E \|S_k\|}{k}, $$ where $V_1$ denotes the first intrinsic volume, which is proportional to the mean width. These results have applications to geometry, and in particular, imply the formula by Gao and Vitale (2001) for the intrinsic volumes of special path-simplexes, called canonical orthoschemes, which are finite-dimensional approximations of the closed convex hull of a Wiener spiral. Moreover, there is a direct connection between spherical intrinsic volumes of these simplexes and the probabilities $p_n$. We also prove similar results for convex hulls of random walk bridges, and more generally, for partial sums of exchangeable random vectors., Comment: Minor changes: Fig. 1 added; the proof of (13) revised; the proofs of Corollary 2 (to Theorem 4) and Lemma 5 clarified

Consider a centred random walk in dimension one with a positive finite variance $\sigma^2$, and let $\tau_B$ be the hitting time for a bounded Borel set $B$ with a non-empty interior. We prove the asymptotic $P_x(\tau_B > n) \sim \sqrt{2 / \pi} \sigma^{-1} V_B(x) n^{-1/2}$ and provide an explicit formula for the limit $V_B$ as a function of the initial position $x$ of the walk. We also give a functional limit theorem for the walk conditioned to avoid $B$ by the time $n$. As a main application, consider the case that $B$ is an interval and study the size of the largest gap $G_n$ (maximal spacing) within the range of the walk by the time $n$. We prove a limit theorem for $G_n$, which is shown to be of the constant order, and describe its limit distribution. In addition, we prove an analogous result for the number of non-visited sites within the range of an integer-valued random walk., Comment: The title changed and some minimal changes added

Take a centered random walk S_n and consider the sequence of its partial sums A_n = S_1 + ... + S_n. Suppose S_1 is in the domain of normal attraction of an \alpha-stable law with 1 < \alpha <= 2. Assuming that S_1 is either right-exponential (that is P(S > x | S > 0)=e^{-ax} for some a > 0 and all x > 0) or right-continuous (skip free), we prove that p_N = P(A_1 > 0, ..., A_N > 0) ~ C_\alpha N^{1/(2\alpha) - 1/2} as N tends to infinity, where C_\alpha > 0 depends on the distribution of the walk. We also consider a conditional version of this problem and study positivity of integrated discrete bridges.

Suppose you and your friend both do $n$ tosses of an unfair coin with probability of heads equal to $\alpha$. What is the behavior of the probability that you obtain at least $d$ more heads than your friend if you make $r$ additional tosses? We obtain asymptotic and monotonicity/convexity properties for this competing probability as a function of $n$, and demonstrate surprising phase transition phenomenons as parameters $ d, r$ and $\alpha$ vary. Our main tools are integral representations based on Fourier analysis., Comment: 11 figures

Let $S_n$ be a centered random walk with a finite variance, and define the new sequence $A_n:=\sum_{i=1}^n S_i$, which we call an integrated random walk. We are interested in the asymptotics of $$p_N:=P(\min_{1 \le k \le N} A_k \ge 0)$$ as $N \to \infty$. Sinai (1992) proved that $p_N \asymp N^{-1/4}$ if $S_n$ is a simple random walk. We show that $p_N \asymp N^{-1/4}$ for some other types of random walks that include double-sided exponential and double-sided geometric walks, both not necessarily symmetric. We also prove that $p_N \le c N^{-1/4}$ for lattice walks and for upper exponential walks, that are the walks such that $Law (S_1 | S_1>0)$ is an exponential distribution., Comment: Theorems 2 and 3 were restated and merged into one theorem; a new lemma (Lemma 1) added; Lemma 3 and Remark 1 were restated and merged into Proposition 1; the proof of Lemma 3 is reworked. The paper is accepted to SPA.

We give a quantitative analysis of clustering in a stochastic model of one-dimensional gas. At time zero, the gas consists of $n$ identical particles that are randomly distributed on the real line and have zero initial speeds. Particles begin to move under the forces of mutual attraction. When particles collide, they stick together forming a new particle, called cluster, whose mass and speed are defined by the laws of conservation. We are interested in the asymptotic behavior of $K_n(t)$ as $n\to \infty$, where $K_n(t)$ denotes the number of clusters at time $t$ in the system with $n$ initial particles. Our main result is a functional limit theorem for $K_n(t)$. Its proof is based on the discovered localization property of the aggregation process, which states that the behavior of each particle is essentially defined by the motion of neighbor particles., Comment: Published in at http://dx.doi.org/10.1214/07-AAP481 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Let S_i be a random walk with standard exponential increments. We call \sum_{i=1}^k S_i its k-step area. The random variable V = \inf_{k \ge 1} \frac{2}{k(k+1)} \sum_{i=1}^k S_i plays important role in the study of so-called one-dimensional sticky particles model. We find the distribution of V and prove that P(V > t) = \sqrt{1-t} exp(-t/2) for t in [0,1]. We also show that the variables \min_{1 \le k \le n} \frac{2n}{k(k+1)} \sum_{i=1}^k U_{i, n} converge in distribution to V. Here U_{i, n} are the order statistics of n i.i.d. random variables uniformly distributed on [0,1]., Comment: Added one reference; corrected few typos; added one sentence to Proposition 1

Consider a particle moving through a random medium, which consists of spherical obstacles, randomly distributed in R^d. The particle is accelerated by a constant external field; when colliding with an obstacle, the particle inelastically reflects. We study the asymptotics of X(t), which denotes the position of the particle at time t, as t tends to infinity. The result is a functional limit theorem for X(t)., Comment: 19 pages, uses texdraw.sty