So Papadimitriou's algorithm is going to choose either xi or xj,

that choice is uniform at random.

And it's going to flip the value currently assigned to that variable.

Now the situation at which this is guaranteed to be good for us, is where we

gave the opposite assignment to both xi and xj, relative to the assignment a*.

If both of our value assignments of these variables was the opposite of a*,

whichever one we flip we are going to share one more variable in agreement

with a* than we did before.

That is, in our previous notation, x sub t + 1, the number of variables in which we

agree next time step will be guaranteed to be one more than it is right now.

The situation is more subtle when the current assignment a sub

t agrees with the reference satisfying assignment a* on

exactly one of the two variables xi and xj.

So for example, maybe the current assignment agrees with a* at xi, but

it disagrees with the reference assignment a* on xj.

Now of course, the algorithm has no idea what a* is, this arbitrary satisfying

assignment, so it has no idea which of the two variables xi or xj it should flip.

It just picked one of the two at random.

Now if we get lucky and we flip the value of the variable on which a sub t and

a* disagree then this is just like case one.

The flip causes the two assignments to agree on

one more variable than they did previously.

As a consequence, x sub t + 1 is going to be one more than x sub t.