Optimizing Both Checking and Update Costs in Random Walk Search
Abstract
Random walks are a standard tool for search problems in which a state can be updated locally and tested for being marked. When updating the state and checking whether it is marked have different costs, two classical strategies optimize different parts of the cost: checking after every step is optimal in the number of updates, while repeatedly checking only after mixing is optimal in the number of checks. For a single marked state m and a walk started from its stationary distribution π, Dohotaru and Høyer stated that both guarantees can be matched simultaneously, for a walk that checks after blocks of a fixed length; their argument is sketched through quantum walks, and they observe that they know of no classical proof. We give a short and self-contained classical proof of such a tradeoff, for arbitrary irreducible Markov chains. The algorithm replaces the original transition matrix P by the averaged walk $ \overline P_τ= \frac{1}τ\sum_{k=1}^τ P^k, $ where τ is of order $π(m)HT(m)$. Using a coupling with the original walk and Kac's lemma, we prove directly that the averaged walk hits the marked state in $O(1/π(m))$ checks in expectation. The resulting search cost is S + O(HT(m))U + O(1/π(m))C in expectation, where S, U, and C denote setup, update, and checking costs.
Related
- Optimizing Encoder Circuits of Entanglement-Assisted Quantum LDPC Codes via Beam Search
- Optimizing Proof-Search via Linearization for Gödel-Löb Logic with Tree-Hypersequents
- A General Variable Neighborhood Search for Logistic Network Flow Design with Nonlinear Edge Costs and Transshipment Capacities
- Blind Random Search with Noisy Loss Measurements: Averaging, Thresholding, and Almost Sure Convergence
- Blind Random Search with Noisy Measurements: Almost Sure Convergence and Convergence Rates
BibTeX
@misc{apers2026optimizing,
title = {{Optimizing Both Checking and Update Costs in Random Walk Search}},
author = {Simon Apers and Marin Costes},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.18833},
eprint = {2609.18833},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.18833},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Optimizing Both Checking and Update Costs in Random Walk Search
AU - Simon Apers
AU - Marin Costes
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2609.18833
UR - https://arxiv.org/abs/2609.18833
AB - Random walks are a standard tool for search problems in which a state can be updated locally and tested for being marked. When updating the state and checking whether it is marked have different costs, two classical strategies optimize different parts of the cost: checking after every step is optimal in the number of updates, while repeatedly checking only after mixing is optimal in the number of checks. For a single marked state m and a walk started from its stationary distribution π, Dohotaru and Høyer stated that both guarantees can be matched simultaneously, for a walk that checks after blocks of a fixed length; their argument is sketched through quantum walks, and they observe that they know of no classical proof. We give a short and self-contained classical proof of such a tradeoff, for arbitrary irreducible Markov chains. The algorithm replaces the original transition matrix P by the averaged walk $ \overline P_τ= \frac{1}τ\sum_{k=1}^τ P^k, $ where τ is of order $π(m)HT(m)$. Using a coupling with the original walk and Kac's lemma, we prove directly that the averaged walk hits the marked state in $O(1/π(m))$ checks in expectation. The resulting search cost is S + O(HT(m))U + O(1/π(m))C in expectation, where S, U, and C denote setup, update, and checking costs.
ER -