The simplex method minimizes linear functions by moving between extreme points of a polyhedral region so that each transition de
creases 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) = 1 and p(i,j) = l/i - 1 for j lessthan 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 grater than 1 E_iT_1 = 1 + 1/2 + + 1/(i-1) Let I_j = 1 if the chain visits j on the way from n to 1. Show that for j lessthan n P(I_j = l|I_j+1,...I_n)= l/j to get another proof of the result and conclude that I_1,... I_n-1 are independent.
1 answer:
You might be interested in