# A survey of random processes with reinforcement

@article{Pemantle2007ASO, title={A survey of random processes with reinforcement}, author={Robin Pemantle}, journal={Probability Surveys}, year={2007}, volume={4}, pages={1-79} }

The models surveyed include generalized Polya urns,
reinforced random walks, interacting urn models, and
continuous reinforced processes. Emphasis is on methods and
results, with sketches provided of some proofs. Applications
are discussed in statistics, biology, economics and a number
of other areas.

#### Paper Mentions

#### 449 Citations

PR ] 2 O ct 2 00 6 A survey of random processes with reinforcement

- 2006

The models surveyed include generalized Pólya urns, reinforced random walks, interacting urn models, and continuous reinforced processes. Emphasis is on methods and results, with sketches provided of… Expand

On some generalized reinforced random walk on integers

- Mathematics
- 2008

We consider Reinforced Random Walks where transitions probabilities are a function of the proportions of times the walk has traversed an edge. We give conditions for recurrence or transience. A phase… Expand

Simulated Annealing, Vertex-Reinforced Random Walks and Learning in Games

- Mathematics
- 2007

This paper studies a class of non Markovian and non homogeneous stochastic processes on a finite state space. It provides an unified approach to simulated annealing type processes, certain vertex… Expand

The speed of a general random walk reinforced by its recent history

- Mathematics
- 2017

We consider several variants of a class of random walks whose increment distributions depend on the average value of the process over its most recent $N$ steps. We investigate the speed of the… Expand

A class of non homogeneous self interacting random processes with applications to learning in games and vertex-reinforced random walks

- Mathematics
- 2008

Using an approximation by a set-valued dynamical system, this paper studies a class of non Markovian and non homogeneous stochastic processes on a finite state space. It provides an unified approach… Expand

Synchronization via Interacting Reinforcement

- Mathematics, Physics
- Journal of Applied Probability
- 2014

We consider a system of urns of Pólya type, containing balls of two colors; the reinforcement of each urn depends on both the content of the urn and the average content of all urns. We show that the… Expand

A Class of Self-Interacting Processes with Applications to Games and Reinforced Random Walks

- Mathematics, Computer Science
- SIAM J. Control. Optim.
- 2010

It is shown that, under certain assumptions, the asymptotic behavior of occupation measures can be described in terms of a certain set-valued deterministic dynamical system, which provides a unified approach to simulated annealing type processes and permits the study of new models of vertex reinforced random walks andnew models of learning in games such as Markovian fictitious play. Expand

The range of once-reinforced random walk in one dimension

- Mathematics, Computer Science
- Random Struct. Algorithms
- 2021

For this model, the limit results on all moments of its range on $\mathbb Z$ are derived using Tauberian theory. Expand

Synchronization via Interacting Reinforcement

- Mathematics, Computer Science
- J. Appl. Probab.
- 2014

It is shown that the urns synchronizealmost surely, in the sense that the fraction of balls of a given color converges almost surely, as the time goes to infinity, to the same limit for all urneds. Expand

Generalized Interacting Urn Models

- Mathematics
- 2012

Interacting urns with exponential reinforcement were introduced and studied in Launay (2011). As its parametertends to 1 , this reinforcement mechanism converges to the "generalized" reinforcement,… Expand

#### References

SHOWING 1-10 OF 240 REFERENCES

Urn schemes and reinforced random walks

- Mathematics
- 2000

We define a reinforced urn process (RUP) to be a reinforced random walk on a state space of urns and we show its partial exchangeability. When it is recurrent, a RUP is a mixture of Markov chains and… Expand

Polya-Type Urn Models with Multiple Drawings

- Mathematics
- 2004

We investigate the distribution, mean value, variance and some limiting properties of an urn model of white and red balls under random multiple drawing (either with or without replacement) when the… Expand

Limit theorems for reinforced random walks on certain trees

- Mathematics
- 2006

Consider a linearly edge-reinforced random walk defined on the b-ary tree, b≥70. We prove the strong law of large numbers for the distance of this process from the root. We give a sufficient… Expand

A time-dependent version of Pólya's urn

- Mathematics
- 1990

A process is defined that consists of drawing balls from an urn and replacing them along with extra balls. The process generalizes the well-knownPólya urn process. It is shown that the proportion of… Expand

Attracting edge property for a class of reinforced random walks

- Mathematics
- 2003

Using martingale techniques and comparison with the generalized Urn scheme, it is shown that the edge reinforced random walk on a graph of bounded degree, with the weight function W(k)=kρ,ρ>1,… Expand

A Once edge-reinforced random walk on a Galton–Watson tree is transient

- Mathematics
- 2005

A Once edge-reinforced random walk on a Galton-Watson tree is transient almost surely. This extends a result of Durrett, Kesten and Limic (2002, Probab. Theory Related Fields 122, p. 567) on regular… Expand

A System of Reaction Diffusion Equations Arising in the Theory of Reinforced Random Walks

- Mathematics, Computer Science
- SIAM J. Appl. Math.
- 1997

It is shown that under some circumstances, finite-time blow-up of solutions is possible and in other circumstances, the solutions will decay to a spatially constant solution (collapse). Expand

Continuous time vertex-reinforced jump processes

- Mathematics, Economics
- 2001

Abstract. We study the continuous time integer valued process , which jumps to each of its two nearest neighbors at the rate of one plus the total time the process has previously spent at that… Expand

A random environment for linearly edge-reinforced random walks on infinite graphs

- Mathematics
- 2005

We consider linearly edge-reinforced random walk on an arbitrary locally finite connected graph. It is shown that the process has the same distribution as a mixture of reversible Markov chains,… Expand

An urn model of Diaconis

- Mathematics
- 2004

SUMMARY An urn model of Diaconis and some generalizations are discussed. A convergence theorem is proved that implies for Diaconis’ model that the empirical distribution of balls in the urn converges… Expand