Linearly bounded liars, adaptive covering codes, and deterministic random walks
Joshua Cooper · Journal of Combinatorics · 2010
We analyze a deterministic form of the random walk on the integer line called the 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 bestknown 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 ≤ fn for f ∈ (0, 1/2), and cardinality O( √ log log n/(1 -2f )) times the sphere bound 2 n / n ≤ fn .