We consider a recent model of random walk that recursively grows the network on which it evolves, namely the Tree Builder Random Walk (TBRW). We introduce a bias $\rho \in (0,\infty)$ towards the root, and exhibit a phase transition for transience/recurrence at a critical threshold $\rho_c =1+2\overline{\nu}$, where $\overline{\nu}$ is the (possibly infinite) expected number of new leaves attached to the walker's position at each step. This generalizes previously known results, which focused on the unbiased case $\rho=1$. The proofs rely on a recursive analysis of the local times of the walk at each vertex of the tree, after a given number of returns to the root. We moreover characterize the strength of the transience (law of large numbers and central limit theorem with positive speed) via standard arguments, establish recurrence at $\rho_c$, and show a condensation phenomenon in the non-critical recurrent case.
A fair coin is flipped $n$ times, and two finite sequences of heads and tails with the same length are given, say $A$ and $B$. Each time the word $A$ appears in the sequence of fair coin flips, Alice gets a point, and each time the word $B$ appears, Bob gets a point. Who is more likely to win? This puzzle is a slight extension of Litt's game that recently set Twitter abuzz. We show that Litt's game is fair for any value of $n$ and any two words that have the same auto-correlation structure by building up a bijection that exchanges Bob and Alice scores; the fact that the inter-correlations do not come into play in this case may come up as a surprise.
The infinite-bin model is a one-dimensional particle system on $\mathbb{Z}$ introduced by Foss and Konstantopoulos in relation with last passage percolation on complete directed acyclic graphs. In this model, at each integer time, a particle is selected at random according to its rank, and produces a child at the location immediately to its right. In this article, we consider the limiting distribution of particles after an infinite number of branching events have occurred. Under mild assumptions, we prove that the event (called freezing) that a location contains only a finite number of balls satisfies a $0-1$ law and we provide various criteria to determine whether freezing occurs.
We consider the local limit of finite uniformly distributed directed animals on the square lattice viewed from the root. Two constructions of the resulting uniform infinite directed animal are given: one as a heap of dominoes, constructed by letting gravity act on a right-continuous random walk and one as a Markov process, obtained by slicing the animal horizontally. We look at geometric properties of this local limit and prove, in particular, that it consists of a single vertex at infinitely many (random) levels. Several martingales are found in connection with the confinement of the infinite directed animal on the non-negative coordinates.
We study a model of random partitioning by nearest-neighbor coloring from Poisson rain, introduced independently by Aldous (2018) and Preater (2009). Given two initial points in $[0,1]^d$ respectively colored in red and blue, we let independent uniformly random points fall in $[0,1]^d$, and upon arrival, each point takes the color of the nearest point fallen so far. We prove that the colored regions converge in the Hausdorff sense towards two random closed subsets whose intersection, the frontier, has Hausdorff dimension strictly between $d−1$ and $d$, thus answering a conjecture raised by Aldous (2018). However, several topological properties of the frontier remain elusive
We define a general class of random systems of horizontal and vertical weighted broken lines on the quarter plane whose distribution are proved to be translation invariant. This invariance stems from a reversibility property of the model. This class of systems generalizes several classical processes of the same kind, such as Hammersley's broken line processes involved in Last Passage Percolation theory or such as the six-vertex model for some special sets of parameters. The novelty comes here from the introduction of a weight associated with each line. The lines are initially generated by spatially homogeneous weighted Poisson Point Process and their evolution (turn, split, crossing) are ruled by a Markovian dynamics which preserves Kirchhoff's node law for the line weights at each intersection. Among others, we derive some new explicit invariant measures for some bullet models as well as new reversible properties for some six-vertex models with an external electromagnetic field.
We revisit Vervoort's unpublished paper on the once reinforced random walk, and prove that this process is recurrent on any graph of the form ZxT, with T a finite graph, for sufficiently large reinforcement parameter. We also obtain a shape theorem for the set of visited sites, and show that the fluctuations around this shape are of polynomial order. The proof involves sharp general estimates on the time spent on subgraphs of the ambiant graph which might be of independent interest.
We study the minimum number of heaps required to sort a random sequence using a generalization of Istrate and Bonchis's algorithm (2015). In a previous paper, the authors proved that the expected number of heaps grows logarithmically. In this note, we improve on the previous result by establishing the almost-sure and $L^1$ convergence.
We consider a critical Bernoulli site percolation on the uniform infinite planar triangulation. We study the tail distributions of the peeling time, perimeter, and volume of the hull of a critical cluster. The exponents obtained here differs by a factor 2 from those computed previously by Angel and Curien (2015) in the case of critical site percolation on the uniform infinite half-plane triangulation.
We construct a stationary random tree, embedded in the upper half plane, with prescribed offspring distribution and whose vertices are the atoms of a unit Poisson point process. This process which we call Hammersley’s tree process extends the usual Hammersley’s line process. Just as Hammersley’s process is related to the problem of the longest increasing subsequence, this model also has a combinatorial interpretation: it counts the number of heaps (i.e. increasing trees) required to store a random permutation. This problem was initially considered by Byers et al. (2011) and Istrate and Bonchis (2015) in the case of regular trees. We show, in particular, that the number of heaps grows logarithmically with the size of the permutation.
Given a weighted graph, we introduce a partition of its vertex set such that the distance between any two clusters is bounded from below by a power of the minimum weight of both clusters. This partition is obtained by recursively merging smaller clusters and cumulating their weights. For several classical random weighted graphs, we show that there exists a phase transition regarding the existence of an infinite cluster.
The motivation for introducing this partition arises from a connection with the contact process as it roughly describes the geometry of the sets where the process survives for a long time. We give a sufficient condition on a graph to ensure that the contact process has a non trivial phase transition in terms of the existence of an infinite cluster. As an application, we prove that the contact process admits a sub-critical phase on d-dimensional random geometric graphs and on random Delaunay triangulations. To the best of our knowledge, these are the first examples of graphs with unbounded degrees where the critical parameter is shown to be strictly positive.
We prove that any vertex-reinforced random walk on the integer lattice with non-decreasing reinforcement sequence $w$ satisfying $w(k)=o(k^α)$ for some $α < 1/2$ is recurrent. This improves on previous results of Volkov (2006) and Schapira (2012).
We consider a vertex reinforced random walk on the integer lattice with sub-linear reinforcement. Under some assumptions on the regular variation of the weight function, we characterize whether the walk gets stuck on a finite interval. When this happens, we estimate the size of the localization set. In particular, we show that, for any odd number $N$ larger than or equal to $5$, there exists a vertex reinforced random walk which localizes with positive probability on exactly $N$ consecutive sites.
We characterize non-decreasing weight functions for which the associated one-dimensional vertex reinforced random walk (VRRW) localizes on $4$ sites. A phase transition appears for weights of order $ n\log\log n$: for weights growing faster than this rate, the VRRW localizes almost surely on at most $4$ sites whereas for weights growing slower, the VRRW cannot localize on less than $5$ sites. When w is of order $n \log\log n$, the VRRW localizes almost surely on either $4$ or $5$ sites, both events happening with positive probability.
We consider a continuous-time vertex reinforced jump process on a supercritical Galton-Watson tree. This process takes values in the set of vertices of the tree and jumps to a neighboring vertex with rate proportional to the local time at that vertex plus a constant $c$. The walk is either transient or recurrent depending on this parameter $c$. In this paper, we complete results previously obtained by Davis and Volkov (2002) and Collevecchio (2006) by proving that there is a unique (explicit) positive $c_{\scriptstyle{crit}}$ such that the walk is recurrent for $c \leq c_{\scriptstyle{crit}}$ and transient for $ c> c_{\scriptstyle{crit}}$.
We study a model of multi-excited random walk on a regular tree which generalizes the models of the once excited random walk and the digging random walk introduced by Volkov (2003). We show the existence of a phase transition of the recurrence/transience property of the walk. In particular, we prove that the asymptotic behavior of the walk depends on the order of the excitations, which contrasts with the one dimensional setting studied by Zerner (2005). We also consider the limiting speed of the walk in the transient regime and conjecture that it is not a monotonic function of the environment.
We consider a one-dimensional transient cookie random walk. It is known from a previous paper that a cookie random walk $(X_n)$ has positive or zero speed according to some positive parameter $\alpha > 1$ or $\leq 1$. In this article, we give the exact rate of growth of $(X_n)$ in the zero speed regime, namely: for $0 < \alpha < 1$, $X_n/n^{\frac{\alpha+1}{2}}$ converges in law to a Mittag-Leffler distribution whereas for $\alpha=1$, $X_n(\log n)/n$ converges in probability to some positive constant.
We consider the model of the one-dimensional cookie random walk when the initial cookie distribution is spatially uniform and the number of cookies per site is finite. We give a criterion to decide whether the limiting speed of the walk is non-zero. In particular, we show that a positive speed may be obtained for just 3 cookies per site. We also prove a result on the continuity of the speed with respect to the initial cookie distribution.
We consider a diffusion process $X$ in a random L\'evy potential $\mathbb{V}$ which is a solution of the informal stochastic differential equation \begin{equation*} \left\{ \begin{array}{l} dX_t = d\beta_t - \frac{1}{2}\mathbb{V}'(X_t)dt\\ X_0 = 0, \end{array} \right. \end{equation*} ($\beta$ B.M. independent of $\mathbb{V}$). We study the rate of convergence when the diffusion is transient under the assumption that the L\'evy process $\mathbb{V}$ does not possess positive jumps. We generalize the previous results of Hu-Shi-Yor for drifted Brownian potentials. In particular, we prove a conjecture of Carmona: provided that there exists $0 < \kappa < 1$ such that $\mathbb{E}[e^{\kappa\mathbb{V}_1}]=1$, then $X_t/t^\kappa$ converges to some non-degenerate distribution. These results are in a way analogous to those obtained by Kesten-Kozlov-Spitzer for the transient random walk in a random environment.
We consider a diffusion process $X$ in a random potential $\mathbb{V}$ of the form $\mathbb{V}_x = \mathbb{S}_x -\delta x$, where $\delta$ is a positive drift and $\mathbb{S}$ is a strictly stable process of index $\alpha\in (1,2)$ with positive jumps. Then, the diffusion is transient and $X_t / \log^\alpha t$ converges in law towards an exponential distribution. This behaviour contrasts with the case where $\mathbb{V}$ is a drifted Brownian motion and provides an example of a transient diffusion in a random potential which is as "slow" as in the recurrent setting.
Let $\mathbb{V}$ be a two sided random walk and let $X$ denote a real valued diffusion process with generator $\frac{1}{2}e^{\mathbb{V}_{[x]}}\frac{d}{dx}\Big(e^{-\mathbb{V}_{[x]}}\frac{d}{dx}\Big)$. This process is the continuous equivalent of the one dimensional random walk in random environment with potential $\mathbb{V}$. Hu and Shi (1997) described the L\'evy classes of $X$ in the case where $\mathbb{V}$ behaves approximately like a Brownian motion. In this paper, based on some fine results on the fluctuations of random walks and stable processes, we obtain an accurate image of the almost sure limiting behavior of $X$ when $\mathbb{V}$ behaves asymptotically like a stable process. These results also apply for the corresponding random walk in random environment.