TY - JOUR
TI - A generalised Pólya?s urn with graph-based interactions
LA - en
AU - Benaim, M.
AU - Benjamini, I.
AU - Chen, J.
AU - Lima, Y.
PY - 2015
DA - .
T2 - Random Structures and Algorithms (to appear)
ER -
TY - BOOK
TI - Stochastic Dynamics for Systems Biology
AU - Mazza, C. .
AU - Benaim, M.
PY - 2014
AB - Stochastic Dynamics for Systems Biology is one of the first books to provide a systematic study of the many stochastic models used in systems biology. The book shows how the mathematical models are used as technical tools for simulating biological processes and how the models lead to conceptual insights on the functioning of the cellular processing system. Most of the text should be accessible to scientists with basic knowledge in calculus and probability theory.
The authors illustrate the relevant Markov chain theory using realistic models from systems biology, including signaling and metabolic pathways, phosphorylation processes, genetic switches, and transcription. A central part of the book presents an original and up-to-date treatment of cooperativity. The book defines classical indexes, such as the Hill coefficient, using notions from statistical mechanics. It explains why binding curves often have S-shapes and why cooperative behaviors can lead to ultrasensitive genetic switches. These notions are then used to model transcription rates. Examples cover the phage lambda genetic switch and eukaryotic gene expression.
The book then presents a short course on dynamical systems and describes stochastic aspects of linear noise approximation. This mathematical framework enables the simplification of complex stochastic dynamics using Gaussian processes and nonlinear ODEs. Simple examples illustrate the technique in noise propagation in gene networks and the effects of network structures on multistability and gene expression noise levels. The last chapter provides up-to-date results on stochastic and deterministic mass action kinetics with applications to enzymatic biochemical reactions and metabolic pathways.
T2 - Mathematical and Computational Biology Series
PB - Chapman and Hall/CRC
CY - Bocca Raton
LA - en
SP - 274
ER -
TY - JOUR
TI - Consistency of vanishingly smooth fictitious play
LA - en
AU - Benaim, M.
AU - Mathieu, F.
PY - 2013
DA - .
T2 - Mathematics of Operations Research
IS - 3
VL - 38
SP - 437
EP - 450
ER -
TY - JOUR
TI - Strongly reinforced vertex-reinforced-random-walk on the complete graph
LA - en
AU - Benaim, M.
AU - Raimond, O.
AU - Schapira, B.
PY - 2012
DA - .
T2 - arXiv preprint arXiv:1208.6375
ER -
TY - JOUR
TI - Quantitative ergodicity for some switched dynamical systems
LA - en
AU - Benaim, M.
AU - Le Borgne, S.
AU - Malrieu, F.
AU - Zitt, P. A.
PY - 2012
DA - .
T2 - Electronic Communications in Probability
IS - 56
VL - 17
SP - 1
EP - 14
ER -
TY - JOUR
TI - Stochastic approximation, cooperative dynamics and supermodular games
LA - en
AU - Benaim, M.
AU - Mathieu, F.
PY - 2012
DA - .
T2 - The Annals of Applied Probability
IS - 5
VL - 22
SP - 2133
EP - 2164
ER -
TY - JOUR
TI - On the stability of planar randomly switched systems
LA - en
AU - Benaim, M.
AU - Le Borgne, S.
AU - Malrieu, F.
AU - Zitt, P. A.
PY - 2012
DA - .
T2 - ArXiv e-prints, to appear to the Annals of Applied Probability
ER -
TY - JOUR
TI - Perturbations of Set-Valued Dynamical Systems, with Applications to Game Theory
LA - en
AU - Benaim, M.
AU - Hofbauer, J.
AU - Sorin, S.
PY - 2012
DA - .
T2 - Dynamic Games and Applications
IS - 2
VL - 2
SP - 195
EP - 205
ER -
TY - JOUR
TI - Qualitative properties of certain piecewise deterministic Markov processes
LA - en
AU - Benaim, M.
AU - Borgne, S. L.
AU - Malrieu, F.
AU - Zitt, P. A.
PY - 2012
DA - .
T2 - arXiv preprint arXiv:1204.4143
ER -
TY - JOUR
TI - Self-interacting diffusions IV: Rate of convergence
LA - en
AU - Benaim, M.
AU - Raimond, O.
PY - 2011
DA - .
T2 - Electronic Journal of Probability
VL - 16
SP - 1815
EP - 1843
ER -
TY - JOUR
TI - A class of self-interacting processes with applications to games and reinforced random walks
LA - en
AU - Benaim, M.
AU - Raimond, O.
PY - 2010
DA - .
T2 - SIAM Journal on Control and Optimization
IS - 7
VL - 48
SP - 4707
EP - 4730
ER -
TY - JOUR
TI - Learning in games with unstable equilibria
LA - en
AU - Benaim, M.
AU - Hofbauer, J.
AU - Hopkins, E.
PY - 2009
DA - .
T2 - Journal of Economic Theory
IS - 4
VL - 144
SP - 1694
EP - 1709
ER -
TY - JOUR
TI - Persistence of structured populations in random environments
KW - Random environment, Structured populations, Persistence, Metapopulation, Source-sink, STOCHASTIC ENVIRONMENTS, NOISE COLOR, MODELS, SPACE, VARIABILITY, DYNAMICS, SYSTEMS, TIME, SINK, COEXISTENCE
LA - fr
AU - Benaim, M.
AU - Schreiber, S. J.
PY - 2009
DA - .
AB - Environmental fluctuations often have different impacts on individuals that differ in size, age, or spatial location. To understand how population structure, environmental fluctuations, and density-dependent interactions influence population dynamics, we provide a general theory for persistence for density-dependent matrix models in random environments. For populations with compensating density dependence, exhibiting "bounded" dynamics, and living in a stationary environment, we show that persistence is determined by the stochastic growth rate (alternatively, dominant Lyapunov exponent) when the population is rare. If this stochastic growth rate is negative, then the total population abundance goes to zero with probability one. If this stochastic growth rate is positive, there is a unique positive stationary distribution. Provided there are initially some individuals in the population, the population converges in distribution to this stationary distribution and the empirical measures almost surely converge to the distribution of the stationary distribution. For models with overcompensating density-dependence, weaker results are proven. Methods to estimate stochastic growth rates are presented. To illustrate the utility of these results, applications to unstructured, spatially structured, and stage-structured population models are given. For instance, we show that diffusively coupled sink populations can persist provided that within patch fitness is sufficiently variable in time but not strongly correlated across space. (C) 2009 Elsevier Inc. All rights reserved.
T2 - Theoretical Population Biology
IS - 1
VL - 76
SP - 19
EP - 34
ER -
TY - JOUR
TI - Robust permanence and impermanence for stochastic replicator dynamics
LA - en
AU - Benaim, M.
AU - Hofbauer, J.
AU - Sandholm, W. H.
PY - 2008
DA - .
T2 - Journal of biological dynamics
IS - 2
VL - 2
SP - 180
EP - 195
ER -
TY - CONF
TI - A Bakry-Emery Criterion for self-interacting diffusions
AU - Benaim, M.
AU - Raimond, O.
LA - en
PY - 2008
DA - .
T2 - Seminar on Stochastic Analysis, Random Fields and Applications V
PB - Springer
SP - 19
ER -
TY - JOUR
TI - Dynamics of Vertex-Reinforced Random Walks
LA - fr
AU - Benaim, M.
AU - Tarres, P.
PY - 2008
DA - .
T2 - Preprint. http://arxiv. org/abs/0809.2739
ER -
TY - JOUR
TI - Exponential concentration for first passage percolation through modified Poincare inequalities
KW - modified Poincare inequality, concentration inequality, hypercontractivity, first passage percolation, FLUCTUATIONS
LA - fr
AU - Benaim, M.
AU - Rossignol, R.
PY - 2008
DA - .
AB - We provide a new exponential concentration inequality for first passage percolation valid for a wide class of edge times distributions. This improves and extends a result by Benjamini, Kalai and Schramm (Ann. Probab. 31 (2003)) which gave a variance bound for Bernoulli edge times. Our approach is based on some functional inequalities extending the work of Rossignol (Ann. Probab. 35 (2006)), Falik and Samorodnitsky (Combin. Probab. Comput. 16 (2007)).
T2 - Annales De L Institut Henri Poincare-Probabilites Et Statistiques
IS - 3
VL - 44
SP - 544
EP - 573
ER -
TY - JOUR
TI - A class of mean field interaction models for computer and communication systems
KW - Mean field interaction model, Markov chain, Dynamical system, MAC, protocol, Reputation systems, Game theory, Decoupling assumption, Fixed, point, Bianchi's formula, APPROXIMATION, ALGORITHMS
LA - fr
AU - Benaim, M.
AU - Le Boudec, J. Y.
PY - 2008
DA - .
AB - We consider models of N interacting objects, where the interaction is via a common resource and the distribution of states of all objects. We introduce the key scaling concept of intensity; informally, the expected number of transitions per object per time slot is of the order of the intensity. We consider the case of vanishing intensity, i.e. the expected number of object transitions per time slot is o(N). We show that, under mild assumptions and for large N, the occupancy measure converges, in mean square (and thus in probability) over any finite horizon, to a deterministic dynamical system. The mild assumption is essentially that the coefficient of variation of the number of object transitions per time slot remains bounded with N. No independence assumption is needed anywhere. The convergence results allow us to derive properties valid in the stationary regime. We discuss when one can assure that a stationary point of the ODE is the large N limit of the stationary probability distribution of the state of one object for the system with N objects. We use this to develop a critique of the fixed point method sometimes used in conjunction with the decoupling assumption. (C) 2008 Elsevier B.V. All rights reserved.
T2 - Performance Evaluation
IS - 11-12
VL - 65
SP - 823
EP - 838
ER -
TY - JOUR
TI - A modified Poincare inequality and its application to first passage percolation
LA - fr
AU - Benaim, M.
AU - Rossignol, R.
PY - 2006
DA - .
T2 - Arxiv preprint math/0602496
ER -
TY - JOUR
TI - Stochastic approximations and differential inclusions, part II: Applications
KW - stochastic approximation, differential inclusions, set-valued dynamical, systems, approachability, no regret, consistency, smooth fictitious play, FICTITIOUS PLAY, CORRELATED EQUILIBRIUM, DYNAMICS, GAMES, CONSISTENCY, REGRET
LA - fr
AU - Benaim, M.
AU - Hofbauer, J.
AU - Sorin, S.
PY - 2006
DA - .
AB - We apply the theoretical results on "stochastic approximations and differential inclusions" developed in Benaim et al. [M. Benaim, J. Hofbauer, S. Sorin. 2005. Stochastic approximations and differential inclusions. SIAM J. Control Optim. 44 328-348] to several adaptive processes used in game theory, including classical and generalized approachability, no-regret potential procedures (Hart and Mas-Colell [S. Hart, A. Mas-Colell. 2003. Regret-based continuous time dynamics. Games Econom. Behav. 45 375-394]), and smooth fictitious play [D. Fudenberg, D. K. Levine. 1995. Consistency and cautious fictitious play. J. Econom. Dynam. Control 19 1065-1089].
T2 - Mathematics of Operations Research
IS - 4
VL - 31
SP - 673
EP - 695
ER -
TY - JOUR
TI - Un joli problème d'Erdös
LA - fr
AU - Benaim, M.
PY - 2006
DA - .
T2 - Images du CNRS
ER -
TY - CONF
TI - A Bakry-Emery criterion for self-interacting diffusions
AU - Benaim, M.
AU - Raimond, O.
A2 - M. Dalang
A2 - M. Dozzi
A2 - F. Russo
LA - fr
PY - 2005
DA - .
AB - We give a Bakry-Emery type criterion for self-interacting diffusions on a compact manifold.
KW - processes with reinforcement, self-interacting diffusion, Bakry-Emery, criterion, mass-transportation, Ricci curvature
T2 - 5th Seminar on Stochastic Analysis, Random Fields and Applications
CY - Ascona, SWITZERLAND
PB - Birkhauser Boston
SP - 19
ER -
TY - JOUR
TI - Self-interacting diffusions. III. Symmetric interactions
KW - self-interacting random processes, reinforced processes, THEOREM
LA - fr
AU - Benaim, M.
AU - Raimond, O.
PY - 2005
DA - .
AB - Let M be a compact Riemannian manifold. A self-interacting diffusion on M is a stochastic process solution to where {W-t} is a Brownian vector field on M and V-x(y) = V(x, y) a smooth function. Let mu(t) = 1/t integral(0)(t) delta X-s ds denote the normalized occupation measure of X-t. We prove that, when V is symmetric, mu(t) converges almost surely to the critical set of a certain nonlinear free energy functional J. Furthermore, J has generically finitely many critical points and mu(t) converges almost surely toward a local minimum of J. Each local minimum has a positive probability to be selected.
T2 - Annals of Probability
IS - 5
VL - 33
SP - 1716
EP - 1759
ER -
TY - JOUR
TI - Stochastic approximations and differential inclusions
KW - stochastic approximation, differential inclusions, set-valued dynamical, systems, chain recurrence, approachability, game theory, learning, fictitious play, FICTITIOUS PLAY, DYNAMICAL-SYSTEMS, GAMES, CONVERGENCE, ALGORITHMS
LA - fr
AU - Benaim, M.
AU - Hofbauer, J.
AU - Sorin, S.
PY - 2005
DA - .
AB - The dynamical systems approach to stochastic approximation is generalized to the case where the mean differential equation is replaced by a differential inclusion. The limit set theorem of Benaim and Hirsch is extended to this situation. Internally chain transitive sets and attractors are studied in detail for set-valued dynamical systems. Applications to game theory are given, in particular to Blackwell's approachability theorem and the convergence of fictitious play.
T2 - Siam Journal on Control and Optimization
IS - 1
VL - 44
SP - 328
EP - 348
ER -
TY - JOUR
TI - Generalized urn models of evolutionary processes
KW - Markov chains, random genetic drift, urn models, replicator equations, STOCHASTIC APPROXIMATIONS, DYNAMICS
LA - fr
AU - Benaim, M.
AU - Schreiber, S.
AU - Tarres, P.
PY - 2004
DA - .
AB - Generalized Polya urn models can describe the dynamics of finite populations of interacting genotypes. Three basic questions these models can address are: Under what conditions does a population exhibit growth? On the event of growth, at what rate does the population increase? What is the long-term behavior of the distribution of genotypes? To address these questions, we associate a mean limit ordinary differential equation (ODE) with the urn model. Previously, it has been shown that on the event of population growth, the limiting distribution of genotypes is a connected internally chain recurrent set for the mean limit ODE. To determine when growth and convergence occurs with positive probability, we prove two results. First, if the mean limit ODE has an "attainable" attractor at which growth is expected, then growth and convergence toward this attractor occurs with positive probability. Second, the population distribution almost surely does not converge to sets where growth is not expected and almost surely does not converge to "nondegenerate" unstable equilibria or periodic orbits of the mean limit ODE. Applications to stochastic analogs of the replicator equations and fertility-selection equations of population genetics are given.
T2 - Annals of Applied Probability
IS - 3
VL - 14
SP - 1455
EP - 1478
ER -
TY - BOOK
TI - Promenade aléatoire
AU - Benaim, M.
AU - El Karoui, N.
PY - 2004
PB - Editions de l'école polytechnique
LA - fr
ER -
TY - JOUR
TI - Deterministic approximation of stochastic evolution in games
KW - game theory, evolution, approximation, large deviations, Markov chains, DYNAMICAL-SYSTEMS, STABLE STRATEGIES, MIXED EQUILIBRIA, SELECTION, ALGORITHMS, STABILITY, PLAY
LA - fr
AU - Benaim, M.
AU - Weibull, J. W.
PY - 2003
DA - .
AB - This paper provides deterministic approximation results for stochastic processes that arise when finite populations recurrently play finite games. The processes are Markov chains, and the approximation is defined in continuous time as a system of ordinary differential equations of the type studied in evolutionary game theory. We establish precise connections between the long-run behavior of the discrete stochastic process, for large populations, and its deterministic flow approximation. In particular, we provide probabilistic bounds on exit times from and visitation rates to neighborhoods of attractors; to the deterministic flow. We sharpen these results in the special case of ergodic processes.
T2 - Econometrica
IS - 3
VL - 71
SP - 873
EP - 903
ER -
TY - JOUR
TI - Self-interacting diffusions II: Convergence in law
LA - fr
AU - Benaim, M.
AU - Raimond, O.
PY - 2003
DA - .
AB - This paper concerns convergence in law properties of self-interacting diffusions on a compact Riemannian manifold. (C) 2003 Editions scientifiques et medicales Elsevier SAS.
T2 - Annales De L Institut Henri Poincare-Probabilites Et Statistiques
IS - 6
VL - 39
SP - 1043
EP - 1055
ER -
TY - JOUR
TI - A two armed bandit type problem
KW - MIXED EQUILIBRIA, GAMES
LA - fr
AU - Benaim, M.
AU - Ben Arous, G.
PY - 2003
DA - .
T2 - International Journal of Game Theory
IS - 1
VL - 32
SP - 3
EP - 16
ER -
TY - JOUR
TI - Self-interacting diffusions
KW - REINFORCED RANDOM-WALK, STOCHASTIC-APPROXIMATION ALGORITHMS, ASYMPTOTIC-BEHAVIOR
LA - fr
AU - Benaim, M.
AU - Ledoux, M.
AU - Raimond, O.
PY - 2002
DA - .
AB - This paper is concerned with a general class of self-interacting diffusions [X-t}(tgreater than or equal to0) living oil a compact Riemannian manifold M. These are solutions to stochastic differential equations of the form : dX(t) = Brownian increments + drift term depending on X-t and mu(t), the normalized occupation measure of the process. It is proved that the asymptotic behavior of {mu(t)} can be precisely related to the asymptotic behavior of a deterministic dynamical semi-flow Phi = {Phi(t)}(tgreater than or equal to0) defined on the space of the Borel probability measures on M. In particular, the limit sets of {mu(t)} are proved to be almost surely attractor free sets for Phi. These results are applied to several examples of self-attracting/repelling diffusions on the n-sphere. For instance, in the case of self-attracting diffusions, our results apply to prove that {mu(t)} can either converge toward the normalized Riemannian measure, or to a gaussian measure, depending on the value of a parameter measuring the strength of the attraction.
T2 - Probability Theory and Related Fields
IS - 1
VL - 122
SP - 1
EP - 41
ER -
TY - JOUR
TI - Diffusions auto attractives/repulsives
LA - fr
AU - Benaim, M.
AU - Raimond, O.
PY - 2002
DA - .
AB - We present an almost sure ergodic theorem for a class of self-interacting diffusions on a compact Riemannian manifold. (C) 2002 Academie des sciences/Editions scientifiques et medicales Elsevier SAS.
T2 - Comptes Rendus Mathematique
IS - 6
VL - 335
SP - 541
EP - 544
ER -
TY - JOUR
TI - Convergence and oscillation in standardization games
LA - fr
AU - Auriol, E.
AU - Benaim, M.
PY - 2001
DA - .
T2 - European Journal of Economic and Social Systems
IS - 1
VL - 15
SP - 39
EP - 55
ER -
TY - JOUR
TI - Metric properties of the group of area preserving diffeomorphisms
KW - area preserving diffeomorphisms, braids, free groups, quasi-isometry
LA - fr
AU - Benaim, M.
AU - Gambaudo, J. M.
PY - 2001
DA - .
AB - Area preserving diffeomorphisms of the 2-disk which are identity near the boundary form a group D-2 which can be equipped, using the L-2-norm on its Lie algebra, with a right invariant metric. With this metric the diameter of D-2 is infinite. In this paper we show that D-2 contains quasi-isometric embeddings of any finitely generated free group and any finitely generated abelian free group.
T2 - Transactions of the American Mathematical Society
IS - 11
VL - 353
SP - 4661
EP - 4672
ER -
TY - JOUR
TI - Weak asymptotic pseudotrajectories for semiflows: ergodic properties
LA - fr
AU - Benaim, M.
AU - Schreiber, S. J.
PY - 2000
DA - .
T2 - Journal of Dynamics and Differential Equations
IS - 3
VL - 12
ER -
TY - JOUR
TI - Standardization in decentralized economies
KW - LOCK-IN, COMPATIBILITY, COMPETITION, EQUILIBRIA
LA - fr
AU - Auriol, E.
AU - Benaim, M.
PY - 2000
DA - .
AB - This paper presents a dynamic model, inspired by evolutionary game theory, of how standards and norms emerge in decentralized economies. It shows that standardization outcomes depend on adopters' attitudes to problems caused by incompatibility. If individuals display aversion to incompatibility, standardization never fails to happen eventually, but societies sometimes end up picking inferior standards. In this case, official action can be useful to quickly achieve sensible standardization. On the other hand, when individuals display tolerance or neutrality to incompatibility, there is neither path-dependency nor a lock-in problem, and regulation seems a poor alternative to laissez-faire. (JEL C73, D62, L1).
T2 - American Economic Review
IS - 3
VL - 90
SP - 550
EP - 570
ER -
TY - JOUR
TI - Convergence with probability one of stochastic approximation algorithms whose average is cooperative
KW - DYNAMICAL-SYSTEMS, MAPS
LA - fr
AU - Benaim, M.
PY - 2000
DA - .
AB - We consider a stochastic approximation process Xn+1 - x(n) = Yn+1 (F(x(n)) + Un+1) where F : R-m --> R-m is a C-2 irreducible cooperative dissipative vector field, {y(n)}(n greater than or equal to 0) is a sequence of positive numbers decreasing to 0 and {U-n}(n greater than or equal to 0) a sequence of uniformly bounded R-m martingale differences. We show that under certain conditions on {y(n)} and {U-n} the sequence {x(n)}(n greater than or equal to 0) converges with probability one toward the equilibria set of the vector field F.
T2 - Nonlinearity
IS - 3
VL - 13
SP - 601
EP - 616
ER -
TY - JOUR
TI - Stochastic approximation algorithms with constant step size whose average is cooperative
KW - stochastic approximation, ordinary differential equation method, cooperative vector fields, large deviations, weak convergence, theory, of learning in games, DIFFERENTIAL-EQUATIONS, URN PROCESSES, CONVERGENCE, SYSTEMS, SETS
LA - fr
AU - Benaim, M.
AU - Hirsch, M. W.
PY - 1999
DA - .
AB - We consider stochastic approximation algorithms with constant step size whose average ordinary differential equation (ODE) is cooperative and irreducible. We show that, under mild conditions on the noise process, invariant measures and empirical occupations measures of the process weakly converge (as the time goes to infinity and the step size goes to zero) toward measures which are supported by stable equilibria of the ODE. These results are applied to analyzing the long-term behavior of a class of learning processes arising in game theory.
T2 - Annals of Applied Probability
IS - 1
VL - 9
SP - 216
EP - 241
ER -
TY - JOUR
TI - Differential and Stochastic Epidemic Models
LA - fr
AU - Benaim, M.
AU - Hirsch, M. W.
PY - 1999
DA - .
T2 - The Fields Institute Communications
VL - 21
ER -
TY - JOUR
TI - Learning Processes, Mixed Equilibria and Dynamical Systems Arising from Fictitious Play in Perturbed Games
LA - fr
AU - Benaim, M.
AU - Hirsch, M. W.
PY - 1999
DA - .
T2 - Games and Economic Behaviour
VL - 29
SP - 36
EP - 72
ER -
TY - JOUR
TI - Dynamics of stochastic approximation algorithms
LA - fr
AU - Benaim, M.
PY - 1999
DA - 12.1
T2 - Seminaire de probabilites XXXIII. Berlin: Springer. Lect. Notes Math
VL - 1709
SP - 1
EP - 68
ER -
TY - JOUR
TI - Recursive algorithms, urn processes and chaining number of chain recurrent sets
KW - OMEGA-LIMIT SETS, STOCHASTIC APPROXIMATIONS
LA - fr
AU - Benaim, M.
PY - 1998
DA - .
AB - This paper investigates the dynamical properties of a class of urn processes and recursive stochastic algorithms with constant gain which arise frequently in control, pattern recognition, learning theory, and elsewhere. It is shown that, under suitable conditions, invariant measures of the process tend to concentrate on the Birkhoff center of irreducible (i.e. chain transitive) attractors of some vector field F : R-d --> R-d obtained by averaging. Applications are given to simple situations including the cases where F is Axiom A or Morse-Smale, F is gradient-like, F is a planar vector field, F has finitely many alpha and omega limit sets.
T2 - Ergodic Theory and Dynamical Systems
VL - 18
SP - 53
EP - 87
ER -
TY - JOUR
TI - Almost sure convergence of the one-dimensional Kohonen algorithm
LA - fr
AU - Benaim, M.
AU - Fort, J. C.
AU - Pages, G.
PY - 1998
DA - .
T2 - Advances in applied probability
VL - 30
SP - 850
EP - 869
ER -
TY - JOUR
TI - Vertex-reinforced random walks and a conjecture of pemantle
KW - reinforced random walks, random perturbations of dynamical systems, chain recurrence, attractors, STOCHASTIC APPROXIMATIONS, ALGORITHMS, DYNAMICS
LA - fr
AU - Benaim, M.
PY - 1997
DA - .
AB - We discuss and disprove a conjecture of Pemantle concerning vertex-reinforced random walks. The setting is a general theory of non-Markovian discrete-time random processes on a finite space E = {1,...,d}, for which the transition probabilities at each step are influenced by the proportion of times each state has been visited. It is shown that, under mild conditions, the asymptotic behavior of the empirical occupation measure of the process is precisely related to the asymptotic behavior of some deterministic dynamical system induced by a vector field on the d - 1 unit simplex. In particular, any minimal attractor of this vector field has a positive probability to be the Limit set of the sequence of empirical occupation measures. These properties are used to disprove a conjecture and to extend some results due to Pemantle. Some applications to edge-reinforced random walks are also considered.
T2 - Annals of Probability
IS - 1
VL - 25
SP - 361
EP - 392
ER -
TY - JOUR
TI - On invariant hypersurfaces of strongly monotone maps
KW - DISCRETE-TIME SEMIGROUPS, CONVERGENCE, SYSTEMS, MANIFOLDS
LA - fr
AU - Benaim, M.
PY - 1997
DA - .
AB - For C-k, k>1, strongly monotone discrete-time dynamical systems, we present simple criteria which ensure that nonmonotone invariant manifolds are C-k. (C) 1997 Academic Press.
T2 - Journal of Differential Equations
IS - 2
VL - 137
SP - 302
EP - 319
ER -
TY - JOUR
TI - Asymptotic Pseudo-Trajectories and Chain-recurrent flows, with Applications
LA - fr
AU - Benaim, M.
AU - Hirsch, M. W.
PY - 1996
DA - .
T2 - Journal of Dynamics and Differential Equations
IS - 1
VL - 8
SP - 141
EP - 174
ER -
TY - JOUR
TI - A dynamical system approach to stochastic approximations
KW - stochastic approximations, ordinary differential equations, chain-recurrence, neural networks, SURE CONVERGENCE, ALGORITHMS
LA - fr
AU - Benaim, M.
PY - 1996
DA - .
AB - It is known that some problems of almost sure convergence for stochastic approximation processes can be analyzed via an ordinary differential equation (ODE) obtained by suitable averaging. The goal of this paper is to show that the asymptotic behavior of such a process can be related to the asymptotic behavior of the ODE without any particular assumption concerning the dynamics of this ODE. The main results are as follows: a) The limit sets of trajectory solutions to the stochastic approximation recursion are, under classical assumptions, almost surely nonempty compact connected sets invariant under the how of the ODE and contained in its set of chain-recurrence. b) If the gain parameter goes to zero at a suitable rate depending on the expansion rate of the ODE, any trajectory solution to the recursion is almost surely asymptotic to a forward trajectory solution to the ODE.
T2 - Siam Journal on Control and Optimization
IS - 2
VL - 34
SP - 437
EP - 472
ER -
TY - JOUR
TI - Dynamics of Morse-Smale urn processes
LA - fr
AU - Benaim, M.
AU - Hirsch, M. W.
PY - 1995
DA - .
AB - We consider stochastic processes {x(n)}(n greater than or equal to 0) of the form x(n+1)-x(n)=gamma(n+1)(F(x(n))+U-n+1) where F : R(m) --> R(m) is C-2, {gamma(i)}(i greater than or equal to 1) is a Sequence of positive numbers decreasing to 0 and {U-i}(i greater than or equal to 1) is a sequence of uniformly bounded R(m)-valued random variables forming suitable martingale differences. We show that when the vector field F is Morse-Smale, almost surely every sample path approaches an asymptotically stable periodic orbit of the deterministic dynamical system dy/dt = F(y). In the case of certain generalized urn processes we show that for each such orbit Gamma, the probability of sample paths approaching Gamma is positive. This gives the generic behavior of three-color urn models.
T2 - Ergodic Theory and Dynamical Systems
VL - 15
SP - 1005
EP - 1030
ER -
TY - JOUR
TI - Chain recurrence in surface flows
LA - fr
AU - Benaim, M.
AU - Hirsch, M. W.
PY - 1995
DA - .
T2 - Discrete and Continuous Dynamic Systems
IS - 1
VL - 1
SP - 1
EP - 16
ER -
TY - JOUR
TI - Simulated Annealing, Vertex-Reinforced Random Walks and Learning in Games
LA - fr
AU - Benaim, M.
AU - Raimond, O.
PY -
DA - .
ER -