printable pdf
比利时vs摩洛哥足彩 ,
university of california san diego

****************************

math 269 - combinatorics

rob ellis

illinois institute of technology

two-batch liar games on a general bounded channel

abstract:

we consider a 2-person perfect information ``liar'' game, often called a r\'enyi-ulam game. the basic game is that of ``twenty questions'' played between questioner paul and responder carole; paul searches for a distinguished element $x$ in a search space $[n]$ by asking yes-no questions of the form ``is $x\in a$'', where $a\subseteq [n]$. carole responds `yes' or `no', lying in up to $k$ responses. the fully off-line game is equivalent to $k$-error-correcting codes. we extend this game to a general channel $\mathcal{c}$ which governs the manner in which carole may lie. specifically, given the alphabet $[t]:=\{1,\ldots,t\}$, paul searches for $x\in[n]$ by partitioning $[n]=a_1\cup \cdots \cup a_t$ and asking for $a$ such that $x\in a_a$. a lie is a tuple $(a,b)\in[t]\times [t]$ with $a\neq b$. the channel $c$ specifies an arbitrary set of lie strings of bounded length $\leq k$ from which carole may choose a string and intersperse its lies, in order, among her responses. for example, when $t=2$, carole lies with $(1,2)$ when she responds with 2 (``no'') when the correct response is 1 (``yes''). we further restrict paul to ask his questions in two off-line batches. we show that the maximum size of the search space $[n]$ for which paul can guarantee finding the distinguished element is $t^{q+k}/(e_k(c){q \choose k})$ as $q\rightarrow\infty$, where $e_k(c)$ is the number of lie strings in $\mathcal{c}$ of maximum length $k$, generalizing previous work of dumitriu and spencer, and of cicalese, deppe, and mundici. we similarly solve the pathological liar variant. this is joint work with kathryn nyman (loyola university-chicago).

host: jeff remmel

june 12, 2007

4:00 pm

ap&m 7321

****************************