{"id":"arxiv/2609.18833","url":"https://arxiv.org/abs/2609.18833","tags":["cs.DS","cs.CC","cs.DM","math.PR"],"score":0,"title":"Optimizing Both Checking and Update Costs in Random Walk Search","domain":"cs.DS","source":"arxiv","authors":["Simon Apers","Marin Costes"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-16","reactions":{}}