PREPRINTS
-
Abstract
We introduce and develop the concept of Maximal Entropy Random Walks (MERWs) on Weighted Bratteli Diagrams (WBDs), maximizing entropy production along paths as a natural criterion for choosing random walks on networks. Initially defined for irreducible finite graphs, MERWs were recently extended to the infinite setting in [1]. Bratteli Diagrams model various growth processes, such as the Young Lattice, where the Plancherel growth process emerges as a MERW. We show that MERWs are special cases of central Markov chains, which, in general, provide a powerful framework for deriving combinatorial identities. Regarding growing trees, in particular, we retrieve and extend Han's hook-length formula for binary trees and demonstrate that the Binary Search Tree (BST) process is a MERW, recovering its asymptotic behavior. We also introduce preferential attachment to generalize BSTs. For comb models, significant central measures appear, including the Chinese restaurant process, providing an alternative proof of the Poisson-Dirichlet limit distribution. Finally, we propose a Monte Carlo method, based on Knuth's algorithm, to approximate MERWs. We apply it to a pyramidal growth model, drawing connections with the limit shape of Young diagrams under the Plancherel measure. -
Abstract
In this article, we establish solid foundations for the study of Maximal Entropy Random Walks (MERWs) on infinite graphs. We introduce a generalized definition that extends the original concept, along with rigorous tools for handling this generalization. Unlike conventional simple random walks, which maximize entropy locally, MERWs maximize entropy globally along their paths, marking a significant paradigm shift and presenting substantial computational challenges. Originally introduced by physicists and computer scientists, MERWs have connections to concepts such as Parry measures and Doob h-transforms. Our approach addresses the challenges of existence, uniqueness, and approximation, illustrated through examples and counterexamples. Even in the infinite setting, MERWs continue to maximize the entropy rate, albeit in a less direct manner. Additionally, we conduct an in-depth analysis of weighted spider networks, including scaling limits, revealing various phenomena characteristic of the infinite framework, notably a phase transition. A unified proof of scaling limits based on submartingale problems is presented. Furthermore, we consider some extended models, where the spider lattice provides valuable insights, highlighting the complexity of studying these walks for general infinite weighted graphs. -
Abstract
The Maximal Entropy Random Walk (MERW) is a natural process on a finite graph, introduced a few years ago with motivations from theoretical physics. The construction of this process relies on Perron-Frobenius theory for adjacency matrices. Generalizing to infinite graphs is rather delicate, and in this article, we treat in a fairly exhaustive manner the case of the MERW on $\mathbb{Z}$ with loops, for both random and nonrandom loops. Thanks to an explicit combinatorial representation of the corresponding Perron-Frobenius eigenvectors, we are able to precisely determine the asymptotic behavior of these walks. We show, in particular, that essentially all MERWs on $\mathbb{Z}$ with loops have positive speed.
PUBLISHED OR ACCEPTED
-
Abstract
The recurrence and transience of persistent random walks built from variable length Markov chains are investigated. It turns out that these stochastic processes can be seen as Lévy walks for which the persistence times depend on some internal Markov chain: they admit Markov random walk skeletons. A recurrence versus transience dichotomy is highlighted. Assuming the positive recurrence of the driving chain, a sufficient Fourier criterion for the recurrence, close to the usual Chung–Fuchs one, is given and a series criterion is derived. The key tool is the Nagaev–Guivarc’h method. Finally, we focus on particular two-dimensional persistent random walks, including directionally reinforced random walks, for which necessary and sufficient Fourier and series criteria are obtained. Inspired by (Adv. Math. 208 (2007) 680–698), we produce a genuine counterexample to the conjecture of (Adv. Math. 117 (1996) 239–252). As for the one-dimensional case studied in (J. Theoret. Probab. 31 (2018) 232–243), it is easier for a persistent random walk than its skeleton to be recurrent. However, such examples are much more difficult to exhibit in the higher dimensional context. These results are based on a surprisingly novel – to our knowledge – upper bound for the Lévy concentration function associated with symmetric distributions. -
Abstract
We describe the scaling limits of the persistent random walks (PRWs) for which the recurrence has been characterized in Cénac et al. (J. Theor. Probab. 31(1):232–243, 2018). We highlight a phase transition phenomenon with respect to the memory: depending on the tails of the persistent time distributions, the limiting process is either Markovian or non-Markovian. In the memoryless situation, the limits are classical strictly stable Lévy processes of infinite variations, but the critical Cauchy case and the asymmetric situation we investigate fill some lacunae of the literature, in particular regarding directionally reinforced random walks (DRRWs). In the non-Markovian case, we extend the results of Magdziarz et al. (Stoch. Process. Appl. 125(11):4021–4038, 2015) on Lévy walks (LWs) to a wider class of PRWs without renewal patterns. Finally, we clarify some misunderstanding regarding the marginal densities in the framework of DRRWs and LWs and compute them explicitly in connection with the occupation times of Lamperti’s stochastic processes. -
Abstract
We consider a walker on the line that at each step keeps the same direction with a probability which depends on the time already spent in the direction the walker is currently moving. These walks with memories of variable length can be seen as generalizations of directionally reinforced random walks introduced in Mauldin et al. (Adv Math 117(2):239–252, 1996). We give a complete and usable characterization of the recurrence or transience in terms of the probabilities to switch the direction and we formulate some laws of large numbers. The most fruitful situation emerges when the running times both have an infinite mean. In that case, these properties are related to the behaviour of some embedded random walk with an undefined drift so that these features depend on the asymptotics of the distribution tails related to the persistence times. In the other case, the criterion reduces to a null-drift condition. Finally, we deduce some criteria for a wider class of persistent random walks whose increments are encoded by a variable length Markov chain having—in full generality—no renewal pattern in such a way that their study does not reduce to a skeleton RW as for the original model. -
Invariant distributions and scaling limits for some diffusions in time-varying random environmentsPTRF Abstract
We consider a family of one-dimensional diffusions, in dynamical Wiener mediums, which are random perturbations of the Ornstein–Uhlenbeck diffusion process. We prove quenched and annealed convergences in distribution and under weigh-ted total variation norms. We find two kind of stationary probability measures, which are either the standard normal distribution or a quasi-invariant measure, depending on the environment, and which is naturally connected to a random dynamical system. We apply these results to the study of a model of time-inhomogeneous Brox’s diffusions, which generalizes the diffusion studied by Brox (Ann Probab 14(4):1206–1218, 1986) and those investigated by Gradinaru and Offret (Ann Inst Henri Poincaré Probab Stat, 2011). We point out two distinct diffusive behaviours and we give the speed of convergences in the quenched situations. -
Abstract
Let us consider a solution of a one-dimensional stochastic differential equation driven by a standard Brownian motion with time-inhomogeneous drift coefficient $\rho\,\mathrm{sgn}(x)\,|x|^\alpha/t^\beta$. This process can be viewed as a Brownian motion evolving in a potential, possibly singular, depending on time. We prove results on the existence and uniqueness of solution, study its asymptotic behaviour and made a precise description, in terms of parameters $\rho$, $\alpha$ and $\beta$, of the recurrence, transience and convergence. More precisely, asymptotic distributions, iterated logarithm type laws and rates of transience and explosion are proved for such processes.
THESIS
Abstract
We study the asymptotic behaviour of some stochastic processes whose dynamics depends not only on position, but also time, and such that the diffusion term and the potential satisfy some scaling properties. We point out a general phase transition phenomenon, entirely determined by the self-similar parameters. The main idea is to consider an appropriate scaling transformation, taking full advantage of the scaling properties. In the first part, we investigate a family of one-dimensional diffusion processes, driven by a Brownian motion, whose drift is polynomial in time and space. These diffusions are continuous counterparts of the random walks studied by Menshikov and Volkov (2008) and related to the Friedman's urn model. We give, in terms of all scaling parameters, the iterated logarithm type laws, the scaling limits and the explosion times of these processes. The second part dealt with a family of diffusion processes in random environment, directed by a one dimensional Brownian motion, whose potential is Brownian in space and polynomial in time. This situation is a generalization of the time-homogeneous Brox's diffusion (1986) studied in an extensive body of the literature. We obtain in the critical case a quasi-invariant and quasi stationary random measure for the time-inhomogeneous semi-group, deduced from the study of an underlying random dynamical system.