On Drift Induced by Local Transition Asymmetry in Combinatorial State Spaces
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914533224742912 |
|---|---|
| author | Ishizaki, Fumio |
| author_facet | Ishizaki, Fumio |
| contents | 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 differences that can hinder search trajectories from reaching the target, even under identical stationary distributions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_17332 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On Drift Induced by Local Transition Asymmetry in Combinatorial State Spaces Ishizaki, Fumio Computational Engineering, Finance, and Science Probability 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 differences that can hinder search trajectories from reaching the target, even under identical stationary distributions. |
| title | On Drift Induced by Local Transition Asymmetry in Combinatorial State Spaces |
| topic | Computational Engineering, Finance, and Science Probability |
| url | https://arxiv.org/abs/2604.17332 |