Linearly bounded liars, adaptive covering codes, and deterministic random walks

DOI10.4310/JOC.2010.V1.N3.A3MaRDI QIDQ547866zbMATH OpenOpenAlexFDO

Authors Joshua Cooper, Robert B. Ellis

Publication date 27 June 2011

Published in Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0909.0029

zbMATH Keywords

binary symmetric pathological liar gameblock covering codesliar machinerandom walk

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Random walks on graphs (05C81) Combinatorial probability (60C05) Linear codes (general theory) (94B05)

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 $leqfn$ for $fin(0,1/2)$, and cardinality $O(sqrtloglogn/(1-2f))$ times the sphere bound $$.

Recommendations

• Two-batch liar games on a general bounded channel
• The liar game over an arbitrary channel
• Ulam's pathological liar game with one half-lie
• The Rényi-Ulam pathological liar game with a fixed number of lies

Cited in

(1)

• Deterministic walks with choice

This page was built for publication: Linearly bounded liars, adaptive covering codes, and deterministic random walks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q547866)