Suppose that we are given a set of n elements which are to be arranged in some order. At each unit of time a request is made to retrieve one of these elements — the ith being requested with probability Pi. We show that the rule which always moves the requested element one closer to the front of the line minimizes the average position of the element requested among a wide class of rules for all probability vectors of the form P1 = p, P2= · ·· = Pn = (1 – p)/(n − 1). We also consider the above problem when the decision-maker is allowed to utilize such rules as ‘only make a change if the same element has been requested k times in a row', and show that as k approaches infinity we can do as well as if we knew the values of the Pi.

An explicit formula for an invariant measure of a time-reversible Markov chain is presented. It is based on a characterization of time reversibility in terms of the transition probabilities alone.

Symmetric diffusions on manifolds with boundary are studied. Symmetric diffusions are nicer to work with than non-symmetric diffusions because (1) it is easier to tell if an equilibrium density exists, and (2) it is easier to find the equilibrium density when it does exist. If an equilibrium density exists, a symmetric diffusion is time reversible. On the line essentially all diffusions are symmetric.

Using symmetric diffusions, it is shown that a large family of densities can be realized as equilibrium densities of time-reversible diffusions. Some examples are given.