An area (e.g. a stiffy disc) is partitioned into n segments S 1 , S 2 , ..., S n , and a collection of n objects O 1 , O 2 , ..., O n (e.g. pieces of information) are stored in these segments so that...

An area (e.g. a stiffy disc) is partitioned into n segments S₁, S₂, ..., S_n, and a collection of n objects O₁, O₂, ..., O_n
(e.g. pieces of information) are stored in these segments so that each segment contains exactly one object. At time points t = 1, 2, ... one of the objects is needed. Since its location is assumed to be unknown, it has to be searched for. This is done in the following way: The segments are checked in increasing order of their indices. When the desired object O is found at segment S_k, then O will be moved to segment S₁
and the objects originally located at S₁, S₂, ..., S_k−1
will be moved in this order to S₂, S₃, ..., S_k.

Let p_i
be the probability that at a time point t object O_i
is needed; i = 1, 2, ..., n. It is assumed that these probabilities do not depend on t.

(1) Describe the successive location of object O₁
by a homogeneous discrete-time Markov chain, i.e. determine the transition probabilities

p_ij
= P(O₁
at segment S_j
at time t + 1|O₁
at segment Si at time t).

(2) What is the stationary distribution of O₁
the location of given that