Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-18T21:45:17.453Z Has data issue: false hasContentIssue false

Transience des chaines de Markov lineaires sur les permutations

Published online by Cambridge University Press:  14 July 2016

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.

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.

Information

Type
Research Papers
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.)

Article purchase

Temporarily unavailable