Time to absorption in discounted reinforcement models. (English) Zbl 1075.60090
Reinforcement model is studied with the goal to establish the time to absorption when the discount \(x\) tends to zero. Consider population of at least four members where triples are formed to “play together”. These triples change in time and it is proved by the authors [Math.Soc.Sci.48, 315–327 (2004; Zbl 1091.91060)] that the process is trapped in a degenerate state such that the population is divided into subgroups of sizes 3-5 which members play within the subgroup only.
The main results of the paper (Theorems 2.2 and 3.1) concern with a model where the history influence is discounted using a discount rate \(1-x\). In Theorem 2.2 it is proved that with a positive probability each player will play with each other beyond time \(\exp \{c_N x^{-1}\}\), \(N\) is the population size. Consider more specific one-dimensional case with state space \([0,1]\) and its compact subintervals \(I_x\) increasing to \((0,1)\) as \(x\) tends to zero. Then it is proved in Theorem 3.1 that the expectation of the first leave time (from \(I_x\)) of the process tends to \(\exp \{Cx^{-1}\}\) as \(x\) tends to zero.
The main results of the paper (Theorems 2.2 and 3.1) concern with a model where the history influence is discounted using a discount rate \(1-x\). In Theorem 2.2 it is proved that with a positive probability each player will play with each other beyond time \(\exp \{c_N x^{-1}\}\), \(N\) is the population size. Consider more specific one-dimensional case with state space \([0,1]\) and its compact subintervals \(I_x\) increasing to \((0,1)\) as \(x\) tends to zero. Then it is proved in Theorem 3.1 that the expectation of the first leave time (from \(I_x\)) of the process tends to \(\exp \{Cx^{-1}\}\) as \(x\) tends to zero.
Reviewer: Daniel Hlubinka (Praha)
MSC:
| 60J20 | Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) |
Keywords:
network; social network; urn model; Friedman urn; stochastic approximation; meta-stable; trap; three-player game; potential well; exponential time; quasi-stationaryCitations:
Zbl 1091.91060References:
| [1] | Anderlini, L.; Ianni, A., Learning on a torus, (Bicchieri, C.; Jeffrey, R.; Skyrms, B., The Dynamics of Norms (1997), Cambridge University Press: Cambridge University Press Cambridge), 87-107 · Zbl 0904.90181 |
| [2] | Bannai, E.; Ito, T., Algebraic Combinatorics I: Association Schemes (1984), Benjamin/Cummings: Benjamin/Cummings Menlo Park, CA, USA · Zbl 0555.05019 |
| [3] | Barrat, A.; Weigt, M., On the properties of small-world network models, European Phys. J. B, 13, 547 (2000) |
| [4] | Benaı̈m, M., A dynamical system approach to stochastic approximations, SIAM J. Control Optim., 34, 437-472 (1996) · Zbl 0841.62072 |
| [5] | Benaı̈m, M.; Hirsch, M., Dynamics of Morse-Smale urn processes, Ergodic Theory Dynamical Systems, 15, 1005-1030 (1995) · Zbl 0846.60054 |
| [6] | Benjamini, I., Pemantle, R., 2003. Probabilities for cooled Brownian motion to linger near the top of a hill, and application to a market share model. Preprint.; Benjamini, I., Pemantle, R., 2003. Probabilities for cooled Brownian motion to linger near the top of a hill, and application to a market share model. Preprint. |
| [7] | Bonacich, P., Liggett, T., 2002. Asymptotics of a matrix-valued Markov chain arising in sociology. Preprint.; Bonacich, P., Liggett, T., 2002. Asymptotics of a matrix-valued Markov chain arising in sociology. Preprint. · Zbl 1075.60546 |
| [8] | Brouwer, A.; Cohen, A.; Neumaier, A., Distance-Regular Graphs (1989), Springer: Springer Berlin · Zbl 0747.05073 |
| [9] | Bush, R.; Mosteller, F., Stochastic Models for Learning (1955), Wiley: Wiley New York · Zbl 0064.39002 |
| [10] | Davis, B., Reinforced random walk, Probab. Theory Related Fields, 84, 203-229 (1990) · Zbl 0665.60077 |
| [11] | Dembo, A.; Zeitouni, O., Large Deviations Techniques and Applications (1993), Jones and Bartlett: Jones and Bartlett Boston · Zbl 0793.60030 |
| [12] | Eggenberger, F.; Pólya, G., Uber die Statistik verketter vorgäge, Zeit. Angew. Math. Mech., 1, 279-289 (1923) · JFM 49.0382.01 |
| [13] | Ellison, G., Learning, local interaction, and coordination, Econometrica, 61, 1047-1071 (1993) · Zbl 0802.90143 |
| [14] | Flache, A.; Macy, M., The weakness of strong tiescollective action failure in a highly cohesive group, J. Math. Sociol., 21, 3-28 (1996) · Zbl 0883.92035 |
| [15] | Freedman, B., A simple urn model, Comm. Pure Appl. Math., 2, 59-70 (1949) · Zbl 0033.07101 |
| [16] | Freedman, D., Bernard Friedman’s urn, Ann. Math. Statist., 36, 956-970 (1965) · Zbl 0138.12003 |
| [17] | Fudenberg, D.; Kreps, K., Learning mixed equilibria, Games and Econom. Behav., 5, 320-367 (1993) · Zbl 0790.90092 |
| [18] | Iosifescu, M.; Theodorescu, R., Random Processes and Learning (1969), Springer: Springer New York · Zbl 0194.51101 |
| [19] | Lakshmivarahan, S., Learning Algorithms: Theory and Applications (1981), Springer: Springer New York · Zbl 0471.68034 |
| [20] | Limic, V., 2001. Attracting edge property for a class of reinforced random walks. Preprint. http://www.math.cornell.edu/ limic/; Limic, V., 2001. Attracting edge property for a class of reinforced random walks. Preprint. http://www.math.cornell.edu/ limic/ · Zbl 1057.60048 |
| [21] | Maynard Smith, J., Evolution and the Theory of Games (1982), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0526.90102 |
| [22] | Norman, M., Markov Processes and Learning Models (1972), Academic Press: Academic Press New York · Zbl 0262.92003 |
| [23] | Pemantle, R., Nonconvergence to unstable points in urn models and stochastic approximations, Ann. Probab., 18, 698-712 (1990) · Zbl 0709.60054 |
| [24] | Pemantle, R., Skyrms, B., 2003a. Network formation by reinforcement learning: the long and medium run. Preprint.; Pemantle, R., Skyrms, B., 2003a. Network formation by reinforcement learning: the long and medium run. Preprint. · Zbl 1091.91060 |
| [25] | Pemantle, R., Skyrms, B., 2003b. Reinforcement schemes may take a long time to exhibit limiting behavior. in preparation.; Pemantle, R., Skyrms, B., 2003b. Reinforcement schemes may take a long time to exhibit limiting behavior. in preparation. |
| [26] | Robbins, H.; Monro, S., A stochastic approximation method, Ann. Math. Statist., 22, 400-407 (1951) · Zbl 0054.05901 |
| [27] | Roth, A.; Erev, I., Learning in extensive form gamesexperimental data and simple dynamic models in the intermediate term, Games and Econom. Behav., 8, 164-212 (1995) · Zbl 0833.90144 |
| [28] | Terwilliger, P., 1996. Algebraic Combinatorics. Unpublished lecture notes.; Terwilliger, P., 1996. Algebraic Combinatorics. Unpublished lecture notes. |
| [29] | Watts, D.; Strogatz, S., Collective dynamics of “small-world” networks, Nature, 393, 440-442 (1998) · Zbl 1368.05139 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
