On Drift Induced by Local Transition Asymmetry in Combinatorial State Spaces

Fumio Ishizaki

We study stochastic processes on combinatorial state spaces with local transition constraints, as arise in local search algorithms. We show that asymmetry in local transitions indu…