A new class of libraries
Tóm tắt
In this paper we give the stationary measure and a sufficient condition of positive recurrence for a new class of linear libraries. These libraries are built by juxtaposing McCabe's libraries and Tsetlins libraries in an appropriate way: Their policy τ is not classical, by the fact that instead of a circular permutation, τ1 can be the product of several disjoint circular permutations.
Tài liệu tham khảo
Arnaud, J. P. (1977).Sur quelques propriétés des librairies. Thèse de spécialité, Université Paul Sabatier, Toulouse.
Bentley, J. L., and McGeoch, C. (1985). Amortized analyses of self-organizing sequential search heuristics.Commun. ACM 28(4), 404–411.
Dies, J. E. (1981).Chaînes de Markov sur les permutations. Lecture Notes in Mathematics, Vol. 1010, Springer-Verlag, Berlin.
Dies, J. E. (1981). Récurrence positive des libraries mixtes.Z. Wahrsch. verw. Gebiete 58, 509–528.
Dies, J. E. (1982). Sur la transience de certaines chaines de Markov sur les permutations.Adv. Appl. Prob. 14, 526–542.
Hendricks, W. J. (1972) The stationary distribution of an interesting Markov chain.J. Appl. Prob. 9, 231–233.
Hendricks, W. J. (1973). An extension of a theorem concerning an interesting Markov chain.J. Appl. Prob. 10, 886–890.
Letac, G. (1975).Librairies. Rapport technique du C.R.M., No. 569. Montréal, Quebec: Université de Montréal.
Letac, G. (1978).Chaines de Markov sur les permutations. S.M.S. Presses de l'Université de Montréal.
McCabe, J. (1965). On serial files with relocatable records.Operations Res. 13(4), 607–618.
Rivest, R. (1976). On self-organizing sequential search heuristics.Commun. ACM 19(2), 63–67.
Sleator, D., and Tarjan, R. (1985). Amortized efficiency of list update and paging rules.Commun. ACM 28(2), 202–208.
Tsetlin, M. L. (1963). Finite automata and models of simple forms of behaviour.Russian Mathematical Surveys (London Math. Soc.)18(4), 1–28.