(Algorithmic efficiency). The simplex method minimizes linear functions by moving between extreme points of a polyhedral region so that each transition decreases the objective function. Suppose there are n extreme points and they are numbered in increasing order of their values. Consider the Markov chain in which p.1; 1/ D 1 and p.i; j / D 1=i [1] 1 for j < i. In words, when we leave j we are equally likely to go to any of the extreme points with better value.

(a) Use (1.25) to show that for i > 1 EiT1 D 1 C 1=2C C1=.i [1] 1/

(b) Let Ij D 1 if the chain visits j on the way from n to 1. Show that forj < n P.Ij D 1jIjC1; : : : In/ D 1=j to get another proof of the result and conclude that I1; : : : In[1]1 are independent.