比利时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
****************************