Stochastic reversibility in self-organizing systems

Abstract

This paper considers a single-shelf library consisting of n books arranged from left to right on the shelf. Under a general self-organizing rule the book positions are rearranged when a borrowed book, originally in position i, is returned to the shelf. Consider the following swap rule involving function f: when the book in the ith position is borrowed, it is swapped with the book in position f(i), while the other book positions remain unchanged. Associated with this swap rule, there is a Markov chain on book arrangements. This paper gives necessary and sufficient conditions on f for the Markov chain to be reversible. Stationary probabilities of the associated Markov chain can hence be derived.