Local Search with Correlated Randomness

arXiv:2607.17469v3 Announce Type: replace-cross Abstract: The running-time distribution of a randomized algorithm is computed under independent randomness, but independence is rarely what a source guarantees. We study sources $\nu$ satisfying $\nu[w]\le DP[w]^s$ for every finite prefix $w$ of the random tape, where $P$ is an independent reference law, $0<s\le1$, and $D\ge1$; individual choices may be predictable, even determined by the past. The worst-case probability of any closed tape event $E$ is exactly $\min\{1,DC_s(E)\}$, where $C_s(E)$ is the infimum cost of covering $E$ by prefixes of varying depth, a tree max-flow/min-cut identity that makes worst-case survival probabilities exact and optimizable over the algorithm's choices. Three applications follow. For $n$ tasks on one machine, each retried until the next random symbol lies in its success set, every schedule has the same makespan distribution under independent randomness, yet under our constraint two fixed orders miss a linear deadline with worst-case probabilities $1$ and $\exp[-\Theta(n)]$; a static priority rule is optimal at every deadline. For the standard local walk on a $k$-CNF with an assignment that satisfies a majority of each clause, we determine the sharp source threshold $s_*$. Below $s_*$, on some instances a single admissible source forces nontermination however clauses are selected; at $s_*$, with fixed $D$, the expected number of flips is at most cubic in the initial Hamming distance, against linear under independence, with matching worst-case instances; and any fixed margin above $s_*$ restores linear dependence on the distance. Third, verified backtracking for noisy predecessor search remains correct under a sufficiently strong bound on the comparison errors. In every setting the algorithm may also restart, which supplies no fresh randomness; restarting restores exponential tails exactly when the nontermination event has a prefix cover of cost below one.