Consider a collection of N books arranged in a line along a bookshelf. At successive

units of time, a book is selected randomly from the collection. After the book has

been consulted, it is replaced on the shelf one position to the left of its original

position, with the book in that position moved to the right by one. (So the selected

book and its neighbour to the left swap positions.) If the selected book is already

in the leftmost position it is returned there.

All but one of the books have plain covers and are equally likely to be selected.

The other book has a red cover. At each time unit, the red book will be selected

with probability p, 0 < p < 1. Each other book will be selected with probability

(1 − p)/(N − 1). Successive choices of book are independent.

Number the positions on the shelf from 1 (at the left) to N at the right. Write Xn

for the position of the red book after n units of time.

8

Show that X is a Markov chain, with non-zero transition probabilities given by:

pi,i−1 = p i = 2, 3, . . . ,N,

pi,i+1 = (1 − p)/(N − 1) i = 1, 2, . . . ,N − 1,

pi,i = 1 − p − (1 − p)/(N − 1) i = 2, 3, . . . ,N − 1,

p1,1 = 1 − (1 − p)/(N − 1)

pN,N = 1 − p.

My working so far:

I figured the best way was to show the definition of a Markov chain holds, i.e.

I expand the LHS out using the usual definition of conditional probability, but i'm not sure how to show it equates to the RHS. Could someone give me the first few lines of this? Much appreciated.