On Drift Induced by Local Transition Asymmetry in Combinatorial State Spaces
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 induces a systematic drift in a distance process relative to a reference configuration. This drift results from the imbalance between inward and outward transitions, translating combinatorial multiplicities into directional bias. Analyzing the random walk on the Johnson graph, we derive explicit expressions for the drift and expected hitting times. We also show that locality constraints lead to trajectory-level…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.17332
curl -X POST /api/v1/records/arxiv/2604.17332/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.17332/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'