Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-28T20:37:56.343Z Has data issue: false hasContentIssue false
  • English
  • Français

Transience des chaines de Markov lineaires sur les permutations

Published online by Cambridge University Press:  14 July 2016

Jacques-Edouard Dies
Jacques-Edouard Dies*
Affiliation:
Université Paul Sabatier, Toulouse
*
∗Postal address: Université Paul Sabatier, Laboratoire de Statistique et Probabilités, 118, route de Narbonne, 31062 Toulouse Cedex, France.
Get access Rights & Permissions [Opens in a new window]

Abstract

Computer scientists have introduced ‘paging algorithms' which are a special class of Markov chains on permutations known, in probability theory, as ‘libraries': books being placed on a shelf T (T is an infinite interval of the set Z of the integers) and a policy ρ : T → T such that ρ (t) < t being chosen, a book b placed at t ∊ T is selected with probability pb, it is removed and replaced at ρ (t) prior to next removal. The different arrangements of books on the shelf are the states of the Markov chain. In this paper we prove that, if the shelf is not bounded on the left, any library (i.e. for any policy ρ and any probability ρ on the books) is transient.

Keywords

DENUMERABLE MARKOV CHAINSLIBRARIESHARMONIC FUNCTIONS
Type
Research Papers
Information
Journal of Applied Probability , Volume 24 , Issue 4 , December 1987 , pp. 899 - 907
Copyright
Copyright © Applied Probability Trust 1987 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Chassaing, Ph. (1984) Quelques résultats nouveaux sur les produits de matrices aléatoires et sur les chaînes de Markov sur les permutations. Thèse de spécialité. Université Paul Sabatier, Toulouse.Google Scholar
[2] Dies, J.-E. (1983) Chaînes de Markov sur les permutations. Lecture Notes in Mathematics 1010. Springer-Verlag, Berlin.Google Scholar
[3] Dudley, R. M. (1962) Random walks on abelian groups. Proc. Amer. Math. Soc. 13, 447–450.Google Scholar
[4] Karlin, S. (1969) Initiation aux processus stochastiques. Dunod, Paris.Google Scholar
[5] Letac, G. (1978) Chaînes de Markov sur les permutations. S.M.S. Presses de l'Université de Montréal.Google Scholar
[6] Mccabe, J. (1965) On serial files with relocatable records. Operat. Res. 13, 607–618.Google Scholar
[7] Rivest, R. L. (1976) On self organizing sequential search heuristics. Comm. Assoc. Comput. Mach. 19, 63–67.Google Scholar
[8] Tsetlin, M. L. (1963) Finite automata and models of simple form of behavior. Russian Math. Surveys. 18, 1–28.Google Scholar