We consider finite-state time-nonhomogeneous Markov chains whose transition matrix at time n is I+G/n^z where G is a ``generator'' matrix, that is G(i,j)>0 for i,j distinct, and G(i,i)= -∑ _k≠i G(i,k), and z>0 is a strength parameter. In these chains, as time grows, the positions are less and less likely to change, and so form simple models of age-dependent time-reinforcing schemes. These chains, however, exhibit a trichotomy of occupation behaviors depending on parameters.

We show that the average occupation or empirical distribution vector up to time n, when variously 0<z<1, z>1 or z=1, converges in probability to a unique ``stationary'' vector n<sub>G</sub>, converges in law to a nontrivial mixture of point measures, or converges in law to a distribution m<sub>G</sub> with no atoms and full support on a simplex respectively, as n tends to infinity. This last type of limit can be interpreted as a sort of ``spreading'' between the cases 0<z<1 and z>1.

In particular, when G is appropriately chosen, m_G is a Dirichlet distribution, reminiscent of results in Polya urns.

1. Arratia, Richard. On the central role of scale invariant Poisson processes on (0,¥). Microsurveys in discrete probability (Princeton, NJ, 1997), 21--41, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 41, Amer. Math. Soc., Providence, RI (1998). MR1630407 (99i:60098)
2. Arratia, Richard; Barbour, A. D.; Tavare, Simon. On Poisson-Dirichlet limits for random decomposable combinatorial structures. Combin. Probab. Comput. 8 (1999), no. 3, 193--208. MR1702562 (2001b:60029)
3. Arratia, Richard; Barbour, A. D.; Tavare, Simon. Logarithmic combinatorial structures: a probabilistic approach. EMS Monographs in Mathematics. European Mathematical Society (EMS), Zürich, (2003). MR2032426 (2004m:60004)
4. Athreya, Krishna B. On a characteristic property of Polya's urn. Studia Sci. Math. Hungar. 4 (1969) 31--35. MR0247643 (40 #907)
5. Bremaud, Pierre. Markov chains. Gibbs fields, Monte Carlo simulation, and queues. Texts in Applied Mathematics, 31. Springer-Verlag, New York, (1999). MR1689633 (2000k:60137)
6. Dobrushin, R. Limit theorems for Markov chains with two states. (Russian) Izv. Adad. Nauk SSSR 17:4 (1953), 291-330. Math. Review number not available.
7. Gantert, Nina. Laws of large numbers for the annealing algorithm. Stochastic Process. Appl. 35 (1990), no. 2, 309--313. MR1067115 (91i:60086)
8. Gouet, Raul. Strong convergence of proportions in a multicolor Polya urn. J. Appl. Probab. 34 (1997), no. 2, 426--435. MR1447347 (98f:60065)
9. Hanen, Albert. Theoremes limites pour une suite de chaines de Markov. (French) Ann. Inst. H. Poincare 18 (1963) 197--301. MR0168017 (29 #5282)
10. Hannig, Jan; Chong, Edwin K. P.; Kulkarni, Sanjeev R. Relative frequencies of generalized simulated annealing. Math. Oper. Res. 31 (2006), no. 1, 199--216. MR2205528 (2006i:90124)
11. Hartfiel, D. J. Dense sets of diagonalizable matrices. Proc. Amer. Math. Soc. 123 (1995), no. 6, 1669--1672. MR1264813 (95k:15011)
12. Horn, Roger A.; Johnson, Charles R. Matrix analysis. Corrected reprint of the 1985 original. Cambridge University Press, Cambridge, (1990). MR1084815 (91i:15001)
13. Isaacson, Dean L.; Madsen, Richard W. Markov chains. Theory and Applications. Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons, New York-London-Sydney, (1976). MR0407991 (53 #11758)
14. Iosifescu, Marius. Finite Markov processes and their applications. Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons, Ltd., Chichester; Editura Tehnicu a, Bucharest, (1980). MR0587116 (82c:60123)
15. Iosifescu, M.; Theodorescu, R. Random processes and learning. Die Grundlehren der mathematischen Wissenschaften, Band 150. Springer-Verlag, New York, (1969). MR0293704 (45 #2781)
16. Kotz, Samuel; Balakrishnan, N. Advances in urn models during the past two decades. Advances in combinatorial methods and applications to probability and statistics, 203--257, Stat. Ind. Technol., Birkhauser Boston, Boston, MA, (1997). MR1456736 (98f:60012)
17. Kotz, Samuel; Balakrishnan, N.; Johnson, Norman L. Continuous multivariate distributions. Vol. 1. Models and applications. Second edition. Wiley Series in Probability and Statistics: Applied Probability and Statistics. Wiley-Interscience, New York, (20000. MR1788152 (2001h:62001)
18. Liu, Wen; Liu, Guo Xin. A class of strong laws for functionals of countable nonhomogeneous Markov chains. Statist. Probab. Lett. 22 (1995), no. 2, 87--96. MR1327733 (96e:60121)
19. Miclo, Laurent. Sur les temps d'occupations des processus de Markov finis inhomogènes a basse temperature. (French) [Occupation times of low-temperature nonhomogeneous finite Markov processes] Stochastics Stochastics Rep. 63 (1998), no. 1-2, 65--137. MR1639780 (99e:60162)
20. Del Moral, P.; Miclo, L. Self-interacting Markov chains. Stoch. Anal. Appl. 24 (2006), no. 3, 615--660. MR2220075
21. Pemantle, Robin. A survey of random processes with reinforcement. Probab. Surv. 4 (2007), 1--79 (electronic). MR2282181
22. Pitman, Jim. Some developments of the Blackwell-MacQueen urn scheme. Statistics, probability and game theory, 245--267, IMS Lecture Notes Monogr. Ser., 30, Inst. Math. Statist., Hayward, CA, (1996). MR1481784 (99c:60017)
23. Pitman, J. Combinatorial stochastic processes. Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7--24, 2002. With a foreword by Jean Picard. Lecture Notes in Mathematics, 1875. Springer-Verlag, Berlin, (2006). MR2245368
24. Sethuraman, Jayaram. A constructive definition of Dirichlet priors. Statist. Sinica 4 (1994), no. 2, 639--650. MR1309433 (95m:62058)
25. Vervaat, W. Success epochs in Bernoulli trials (with applications in number theory). Mathematical Centre Tracts, 42. Mathematisch Centrum, Amsterdam, (1972). MR0328989 (48 #7331)
26. Wen, Liu; Weiguo, Yang. An extension of Shannon-McMillan theorem and some limit properties for nonhomogeneous Markov chains. Stochastic Process. Appl. 61 (1996), no. 1, 129--145. MR1378852 (97a:60052)
27. Winkler, Gerhard. Image analysis, random fields and Markov chain Monte Carlo methods. A mathematical introduction. Second edition. Applications of Mathematics 27. Stochastic Modelling and Applied Probability. Springer-Verlag, Berlin, (2003). MR1950762 (2004c:94028)