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.