Linearly Bounded Liars, Adaptive Covering Codes, and Deterministic Random Walks

Abstract

We analyze a deterministic form of the random walk on the integer line called the {\em liar machine}, similar to the rotor-router model, finding asymptotically tight pointwise and interval discrepancy bounds versus random walk. This provides an improvement in the best-known winning strategies in the binary symmetric pathological liar game with a linear fraction of responses allowed to be lies. Equivalently, this proves the existence of adaptive binary block covering codes with block length $n$, covering radius $\le fn$ for $f\in (0,1/2)$, and cardinality $O(\sqrt{\log \log n}/(1-2f))$ times the sphere bound $2^n/\left(\genfrac{}{}{0ex}{}{n}{\le \lfloor fn\rfloor }\right)$.

23 pages