Mathematics – Combinatorics
Scientific paper
2009-03-27
Mathematics
Combinatorics
26 pages
Scientific paper
We consider an extension of the 2-person R\'enyi-Ulam liar game in which lies are governed by a channel $C$, a set of allowable lie strings of maximum length $k$. Carole selects $x\in[n]$, and Paul makes $t$-ary queries to uniquely determine $x$. In each of $q$ rounds, Paul weakly partitions $[n]=A_0\cup >... \cup A_{t-1}$ and asks for $a$ such that $x\in A_a$. Carole responds with some $b$, and if $a\neq b$, then $x$ accumulates a lie $(a,b)$. Carole's string of lies for $x$ must be in the channel $C$. Paul wins if he determines $x$ within $q$ rounds. We further restrict Paul to ask his questions in two off-line batches. We show that for a range of sizes of the second batch, the maximum size of the search space $[n]$ for which Paul can guarantee finding the distinguished element is $\sim t^{q+k}/(E_k(C)\binom{q}{k})$ as $q\to\infty$, where $E_k(C)$ is the number of lie strings in $C$ of maximum length $k$. This generalizes previous work of Dumitriu and Spencer, and of Ahlswede, Cicalese, and Deppe. We extend Paul's strategy to solve also the pathological liar variant, in a unified manner which gives the existence of asymptotically perfect two-batch adaptive codes for the channel $C$.
Ellis Robert B.
Nyman Kathryn L.
No associations
LandOfFree
Two-batch liar games on a general bounded channel does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Two-batch liar games on a general bounded channel, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two-batch liar games on a general bounded channel will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-21934