arXiv preprint ·
Optimizing Both Checking and Update Costs in Random Walk Search
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Efficient Algorithms for Subdeterminant Maximization under Partition Matroids
Spectral Gap of Down-Up Walks via Trickle-Down: A Simplified and Sharpened Analysis
Routing Multiple Agents Below the Sum of Distances
Improved Algorithms for Beck--Fiala with Bounded Sets
Integrality gap preserving reductions
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.