Local Search with Correlated Randomness

How much does an algorithm's running-time distribution under independent randomness reveal about its behavior when independence is no longer guaranteed? We study sources satisfying nu[w]≤ DP[w]s for every finite prefix w, where P is an independent reference law, 0<s≤1, and D≥1. The constraint controls complete-prefix probabilities while allowing individual choices to be predictable, even fully determined by the past. For retry tasks, all deterministic history-dependent selectors have the same independent-source running-time law. Yet two orders have worst-case failure probabilities 1 and exp[-Theta(n)] at the same linear deadline under the same source constraint. We identify a static priority rule that is optimal at every deadline and every D. For the standard local walk on a k-CNF with at least r true literals per clause under some assignment, k/2<r<k, we determine the sharp source threshold s_*. At and above it, the expected flip count is Ok,r(minL3,L/(s-s_*)), where L=h+log D+1, h is the initial Hamming distance to that assignment, and L/0=∞. The bound allows arbitrary clause overlap and history-dependent clause selection. Matching instances admit one source forcing this delay with probability one for every selector. At criticality and fixed D, the delay is cubic despite a linear independent-source expectation. Variable-depth prefix covers, together with classical tree max-flow/min-cut, yield an exact criterion for restoring exponential tails by restarting on the same tape. We synthesize updates and restarts for explicit finite-state processes. Under a sufficient prefix guarantee, we also obtain noisy predecessor search with error at most η and expected query count polynomial in the correct leaf's depth and log(D/η), without knowing the depth or tree height.