Search

We consider the class of two-person ordinal potential games where each player has the same number of actions $K$. Each game in this class admits at least one pure Nash equilibrium and the best-response dynamics converges to one of these pure Nash equilibria; which one depends on the starting point. So, each pure Nash equilibrium has a basin of attraction. We pick uniformly at random one game from this class and we study the joint distribution of the sizes of the basins of attraction. We provide an asymptotic exact value for the expected basin of attraction of each pure Nash equilibrium, when the number of actions $K$ goes to infinity., Comment: 24 pages, 2 figures

Best Response Dynamics (BRD) is a class of strategy updating rules to find Pure Nash Equilibria (PNE) in a game. At each step, a player is randomly picked, and the player switches to a "best response" strategy based on the strategies chosen by others, so that the new strategy profile maximises their payoff. If no such strategy exists, a different player will be chosen randomly. When no player wants to change their strategy anymore, the process reaches a PNE and will not deviate from it. On the other hand, either PNE may not exist, or BRD could be "trapped" within a subgame that has no PNE. We consider a random game with $N$ players, each with two actions available, and i.i.d. payoffs, in which the payoff distribution may have an atom, i.e. ties are allowed. We study a class of random walks in a random medium on the $N$-dimensional hypercube induced by the random game. The medium contains two types of obstacles corresponding to PNE and traps. The class of processes we analyze includes BRD, simple random walks on the hypercube, and many other nearest neighbour processes. We prove that, with high probability, these processes reach a PNE before hitting any trap., Comment: 20 pages, 4 figures, 1 table

We study asymptotic behaviours of a non-linear vertex-reinforced jump process defined on an arbitrary infinite graph with bounded degree. We prove that if the reinforcement function $w$ is reciprocally integrable and non-decreasing, then the process visits only a finite number of vertices. In the case where $w$ is approximately equal to a super-linear polynomial, we show that the process eventually gets stuck on a star-shaped subgraph and there is exactly one vertex with unbounded local time., Comment: 43 pages

We study a large class of long-range random walks which take values on the vertices of an N dimensional hypercube. These processes are connected with multivariate Bernoulli autoregression., Comment: 25 pages, 1 figure

We study one-dimensional excited random walks with non-nearest neighbor jumps. When the process is at a vertex that has not been visited before, its next transition has a positive drift to the right, possibly with long jumps. Whenever the process visits a vertex that has already been visited in the past, its next transition is the one of a simple symmetric random walk. We give a sufficient condition for the process to have positive speed., Comment: latest version, 18 pages, 2 figures

We consider two-player normal form games where each player has the same finite strategy set. The payoffs of each player are assumed to be i.i.d. random variables with a continuous distribution. We show that, with high probability, the better-response dynamics converge to pure Nash equilibrium whenever there is one, whereas best-response dynamics fails to converge, as it is trapped., Comment: 8 pages, 1 figure

Given the increments of a simple symmetric random walk $(X_n)_{n\ge0}$, we characterize all possible ways of recycling these increments into a simple symmetric random walk $(Y_n)_{n\ge0}$ adapted to the filtration of $(X_n)_{n\ge0}$. We study the long term behavior of a suitably normalized two-dimensional process $((X_n,Y_n))_{n\ge0}$. In particular, we provide necessary and sufficient conditions for the process to converge to a two-dimensional Brownian motion (possibly degenerate). We also discuss cases in which the limit is not Gaussian. Finally, we provide a simple necessary and sufficient condition for the ergodicity of the recycling transformation, thus generalizing results from Dubins and Smorodinsky (1992) and Fujita (2008), and solving the discrete version of the open problem of the ergodicity of the general L\'evy transformation (see Mansuy and Yor, 2006)., Comment: 22 pages, 2 figures

We consider a non-linear vertex-reinforced jump process (VRJP($w$)) on $\mathbb{Z}$ with an increasing measurable weight function $w:[1,\infty)\to [1,\infty)$ and initial weights equal to one. Our main goal is to study the asymptotic behaviour of VRJP($w$) depending on the integrability of the reciprocal of $w$. In particular, we prove that if $\int_1^{\infty} \frac{\text{d}u}{w(u)} =\infty$ then the process is recurrent, i.e. it visits each vertex infinitely often and all local times are unbounded. On the other hand, if $\int_1^{\infty} \frac{\text{d} u}{w(u)} <\infty$ and there exists a $\rho>0$ such that $t \mapsto w(t)^{\rho}\int_t^{\infty}\frac{\text{d}u}{w(u)}$ is non-increasing then the process will eventually get stuck on exactly three vertices, and there is only one vertex with unbounded local time. We also show that if the initial weights are all the same, VRJP on $\mathbb{Z}$ cannot be transient, i.e. there exists at least one vertex that is visited infinitely often. Our results extend the ones previously obtained by Davis and Volkov [Probab. Theory Relat. Fields (2002)] who showed that VRJP with linear reinforcement on $\mathbb{Z}$ is recurrent., Comment: latest version, 41 pages. To appear in Annals of Applied Probability

We introduce a general class of random walks on the $N$-hypercube, study cut-off for the mixing time, and provide several types of representation for the transition probabilities. We observe that for a sub-class of these processes with long range (i.e. non-local) there exists a critical value of the range that allows an "almost-perfect" mixing in at most three steps. In other words, the total variation distance between the three steps transition and the stationary distribution decreases geometrically in $N$, which is the dimension of the hypercube. In some cases, the walk mixes almost-perfectly in exactly two steps. Notice that a well-known result (Theorem 1 in Diaconis and Shahshahani (1986)) shows that there exist no random walk on Abelian groups (such as the hypercube) which mixes perfectly in exactly two steps., Comment: 27 pages, 1 figure

We study Random Walks in an i.i.d. Random Environment (RWRE) defined on $b$-regular trees. We prove a functional central limit theorem (FCLT) for transient processes, under a moment condition on the environment. We emphasize that we make no uniform ellipticity assumptions. Our approach relies on regenerative levels, i.e. levels that are visited exactly once. On the way, we prove that the distance between consecutive regenerative levels have a geometrically decaying tail. In the second part of this paper, we apply our results to Linearly Edge-Reinforced Random Walk (LERRW) to prove FCLT when the process is defined on $b$-regular trees, with $ b \ge 4$, substantially improving the results of the first author (see Theorem 3 of Collevecchio (2006))., Comment: 23 pages

In finite games mixed Nash equilibria always exist, but pure equilibria may fail to exist. To assess the relevance of this nonexistence, we consider games where the payoffs are drawn at random. In particular, we focus on games where a large number of players can each choose one of two possible strategies, and the payoffs are i.i.d. with the possibility of ties. We provide asymptotic results about the random number of pure Nash equilibria, such as fast growth and a central limit theorem, with bounds for the approximation error. Moreover, by using a new link between percolation models and game theory, we describe in detail the geometry of Nash equilibria and show that, when the probability of ties is small, a best-response dynamics reaches a Nash equilibrium with a probability that quickly approaches one as the number of players grows. We show that a multitude of phase transitions depend only on a single parameter of the model, that is, the probability of having ties., Comment: 29 pages, 7 figures

We study the behaviour of a class of edge-reinforced random walks {on $\mathbb{Z}_+$}, with heterogeneous initial weights, where each edge weight can be updated only when the edge is traversed from left to right. We provide a description for different behaviours of this process and describe phase transitions that arise as trade-offs between the strength of the reinforcement and that of the initial weights. Our result aims to complete the ones given by Davis~\cite{Davis89, Davis90}, Takeshima~\cite{Takeshima00, Takeshima01} and Vervoort~\cite{Vervoort00}., Comment: 16 pages, 1 figure

Consider a randomly-oriented two dimensional Manhattan lattice where each horizontal line and each vertical line is assigned, once and for all, a random direction by flipping independent and identically distributed coins. A deterministic walk is then started at the origin and at each step moves diagonally to the nearest vertex in the direction of the horizontal and vertical lines of the present location. This definition can be generalized, in a natural way, to larger dimensions, but we mainly focus on the two dimensional case. In this context the process localizes on two vertices at all large times, almost surely. We also provide estimates for the tail of the length of paths, when the walk is defined on the two dimensional lattice. In particular, the probability of the path to be larger than $n$ decays sub-exponentially in $n$. It is easy to show that higher dimensional paths may not localize on two vertices but will still eventually become periodic, and are therefore bounded., Comment: 18 pages, 12 figures

The branching-ruin number of a tree, which describes its asymptotic growth and geometry, can be seen as a polynomial version of the branching number. This quantity was defined by Collevecchio, Kious and Sidoravicius (2018) in order to understand the phase transitions of the once-reinforced random walk (ORRW) on trees. Strikingly, this number was proved to be equal to the critical parameter of ORRW on trees. In this paper, we continue the investigation of the link between the branching-ruin number and the criticality of random processes on trees. First, we study random walks on random conductances on trees, when the conductances have an heavy tail at $0$, parametrized by some $p>1$, where $1/p$ is the exponent of the tail. We prove a phase transition recurrence/transience with respect to $p$ and identify the critical parameter to be equal to the branching-ruin number of the tree. Second, we study a multi-excited random walk on trees where each vertex has $M$ cookies and each cookie has an infinite strength towards the root. Here again, we prove a phase transition recurrence/transience and identify the critical number of cookies to be equal to the branching-ruin number of the tree, minus 1. This result extends a conjecture of Volkov (2003). Besides, we study a generalized version of this process and generalize results of Basdevant and Singh (2009).

We give a simple proof for recurrence of vertex reinforced jump process on \(\mathbb{Z}^d\), under strong reinforcement. Moreover, we show how the previous result implies that linearly edge-reinforced random walk on \ \(\mathbb{Z}^d\) is {recurrent} for strong reinforcement. Finally, we prove that the \(H^{(2|2)}\) model on \(\mathbb{Z}^d\) localizes at strong disorder. Even though these results are well-known, we propose a unified approach, {which also has the advantage to provide shorter proofs}, and relies on estimating fractional moments, introduced by Aizenman and Molchanov., Comment: We added details in the proofs

Our main goal is to study a class of processes whose increments are generated via a cellular automata rule. Given the increments of a simple biased random walk, a new sequence of (dependent) Bernoulli random variables is produced. It is built, from the original sequence, according to a cellular automata rule. Equipped with these two sequences, we construct two more according to the same cellular automata rule. The construction is repeated a fixed number of times yielding an infinite array ($\{-K,\ldots,K\}\times\N$) of (dependent) Bernoulli random variables. %In turn, using this new sequence as input, we reiterate a construction of a new sequence. %This process is repeated a finite number of times resulting in an infinite array, herein called the "downward process", of highly dependent Bernoulli random variables. The process of taking partial products can be reversed allowing to construct new sequences, herein called the "upward process", the characteristics of which are different from the downward process. Taking partial sums of these sequences, we obtain a $(2K+1)$-dimensional process whose increments belong to the state space $\{-1,1\}^{2K+1}$. The aim of the paper is to study the long term behaviour of this process. In particular, we establish transience/recurrence properties and prove an invariance principle. The limiting behaviour of these processes depends strongly on the direction of the iteration, and exhibits few surprising features. This work is motivated by an earlier investigation in which the starting sequence is symmetric.

The motivation for this paper is the study of the phase transition for recurrence/transience of a class of self-interacting random walks on trees, which includes the once-reinforced random walk. For this purpose, we define a quantity, that we call the branching-ruin number of a tree, which provides (in the spirit of Furstenberg, 1970, and Lyons, 1990) a natural way to measure trees with polynomial growth. We prove that the branching-ruin number of a tree is equal to the critical parameter for the recurrence/transience of the once-reinforced random walk. We define a sharp and effective (i.e. computable) criterion characterizing the recurrence/transience of a larger class of self-interacting walks on trees, providing the complete picture for their phase transition.

We consider the coupling from the past implementation of the random-cluster heat-bath process, and study its random running time, or coupling time. We focus on hypercubic lattices embedded on tori, in dimensions one to three, with cluster fugacity at least one. We make a number of conjectures regarding the asymptotic behaviour of the coupling time, motivated by rigorous results in one dimension and Monte Carlo simulations in dimensions two and three. Amongst our findings, we observe that, for generic parameter values, the distribution of the appropriately standardized coupling time converges to a Gumbel distribution, and that the standard deviation of the coupling time is asymptotic to an explicit universal constant multiple of the relaxation time. Perhaps surprisingly, we observe these results to hold both off criticality, where the coupling time closely mimics the coupon collector's problem, and also at the critical point, provided the cluster fugacity is below the value at which the transition becomes discontinuous. Finally, we consider analogous questions for the single-spin Ising heat-bath process.

We study random walk among random conductance (RWRC) on complete graphs with N vertices. The conductances are i.i.d. and the sum of conductances emanating from a single vertex asymptotically has an infinitely divisible distribution corresponding to a L\'evy subordinator with infinite mass at 0. We show that, under suitable conditions, the empirical spectral distribution of the random transition matrix associated to the RWRC converges weakly, as N goes to infinity, to a symmetric deterministic measure on [-1,1], in probability with respect to the randomness of the conductances. In short time scales, the limiting underlying graph of the RWRC is a Poisson Weighted Infinite Tree, and we analyze the RWRC on this limiting tree. In particular, we show that the transient RWRC exhibits a phase transition in that it has positive or weakly zero speed when the mean of the largest conductance is finite or infinite, respectively., Comment: 21 pages, 2 figures, fixed an error concerning existence of the speed (Proposition 4.4), author information updated

We study the asymptotic behaviour of once-reinforced biased random walk (ORbRW) on Galton-Watson trees. Here the underlying (unreinforced) random walk has a bias towards or away from the root. We prove that in the setting of multiplicative once-reinforcement the ORbRW can be recurrent even when the underlying biased random walk is ballistic. We also prove that, on Galton-Watson trees without leaves, the speed is positive in the transient regime. Finally, we prove that, on regular trees, the speed of the ORbRW is monotone decreasing in the reinforcement parameter when the underlying random walk has high speed, and the reinforcement parameter is small.

We study a system of interacting reinforced random walks defined on polygons. At each stage, each particle chooses an edge to traverse which is incident to its position. We allow the probability of choosing a given edge to depend on the sum of, the number of times that particle traversed that edge, a quantity which depends on the behaviour of the other particles, and possibly external factors. We study localization properties of this system and our main tool is a new result we establish for a very general class of urn models. More specifically, we study attraction properties of urns composed of balls with two distinct colors which evolve as follows. At each stage a ball is extracted. The probability of picking a ball of a certain color evolves in time. This evolution may depend not only on the composition of the urn but also on external factors or internal ones depending on the history of the urn. A particular example of the latter is when the reinforcement is a function of the composition of the urn and the biggest run of consecutive picks with the same color. The model that we introduce and study is very general, and we prove that under mild conditions, one of the colors in the urn is picked only finitely often., Comment: 35 pages, 1 fig

We prove rapid mixing of the worm process for the zero-field ferromagnetic Ising model, on all finite connected graphs, and at all temperatures. As a corollary, we obtain a fully-polynomial randomized approximation scheme for the Ising susceptibility, and for a certain restriction of the two-point correlation function

Consider a one dimensional simple random walk $X=(X_n)_{n\geq0}$. We form a new simple symmetric random walk $Y=(Y_n)_{n\geq0}$ by taking sums of products of the increments of $X$ and study the two-dimensional walk $(X,Y)=((X_n,Y_n))_{n\geq0}$. We show that it is recurrent and when suitably normalised converges to a two-dimensional Brownian motion with independent components; this independence occurs despite the functional dependence between the pre-limit processes. The process of recycling increments in this way is repeated and a multi-dimensional analog of this limit theorem together with a transience result are obtained. The construction and results are extended to include the case where the increments take values in a finite set (not necessarily $\{-1,+1\}$).

The asynchronous push&pull protocol, a randomized distributed algorithm for spreading a rumour in a graph $G$, works as follows. Independent Poisson clocks of rate 1 are associated with the vertices of $G$. Initially, one vertex of $G$ knows the rumour. Whenever the clock of a vertex $x$ rings, it calls a random neighbour $y$: if $x$ knows the rumour and $y$ does not, then $x$ tells $y$ the rumour (a push operation), and if $x$ does not know the rumour and $y$ knows it, $y$ tells $x$ the rumour (a pull operation). The average spread time of $G$ is the expected time it takes for all vertices to know the rumour, and the guaranteed spread time of $G$ is the smallest time $t$ such that with probability at least $1-1/n$, after time $t$ all vertices know the rumour. The synchronous variant of this protocol, in which each clock rings precisely at times $1,2,\dots$, has been studied extensively. We prove the following results for any $n$-vertex graph: In either version, the average spread time is at most linear even if only the pull operation is used, and the guaranteed spread time is within a logarithmic factor of the average spread time, so it is $O(n\log n)$. In the asynchronous version, both the average and guaranteed spread times are $\Omega(\log n)$. We give examples of graphs illustrating that these bounds are best possible up to constant factors. We also prove theoretical relationships between the guaranteed spread times in the two versions. Firstly, in all graphs the guaranteed spread time in the asynchronous version is within an $O(\log n)$ factor of that in the synchronous version, and this is tight. Next, we find examples of graphs whose asynchronous spread times are logarithmic, but the synchronous versions are polynomially large. Finally, we show for any graph that the ratio of the synchronous spread time to the asynchronous spread time is $O(n^{2/3})$., Comment: 25 pages

We prove rapid mixing of the Prokofiev-Svistunov (or worm) algorithm for the zero-field ferromagnetic Ising model, on all finite graphs and at all temperatures. As a corollary, we show how to rigorously construct simple and efficient approximation schemes for the Ising susceptibility and two-point correlation function., Comment: 5 pages, 1 figure

Let $r$ and $d$ be positive integers with $r

We consider the motion of a particle on a Galton Watson tree, when the probabilities of jumping from a vertex to any one of its neighbours is determined by a random process. Given the tree, positive weights are assigned to the edges in such a way that, viewed along any line of descent, they evolve as a random process. In order to introduce our method for proving transience or recurrence, we first suppose that the weights are i.i.d., reproving a result of Lyons and Pemantle. We then extend the argument to allow a Markovian environment, and finally to a random walk on a Markovian environment that changes the environment. Our approach involves studying the typical behaviour of processes on fixed lines of descent, which we then show determines the behaviour of the process on the whole tree., Comment: 22 Pages