UTA Department of Mathematics

Applied Mathematics Seminar

Date/Time/Room: Wednesday (11/10/2004) at 2:30pm in 304 Pickard Hall

Speaker: Professor Catherine Yan, Department of Mathematics, Texas A&M University

"The Renyi-Ulam liar Game with a Half-Liar"

Abstract: The $q$-round R\'enyi-Ulam liar game with $k$ lies on the set $[n]:=\{1,\ldots,n\}$ is a 2-player perfect information zero sum game. In the game the questioner Paul tries to find one of $n$ possibilities with $q$ Yes-No questions, while the responder Carole is allowed to lie a fixed number $k$ of times. We consider an asymmetric variant in which Carole must say yes when that is the correct answer (whence the \emph{half-liar}). We prove the existence of a winning strategy for Paul to the existence of a packing of the discrete hypercube with certain relaxed Hamming balls, and show that the maximal $A_k(q)$ for which Paul wins has the asymptotic form \[ A_k(q)=2^{q+k}k!q^{-k} + \Theta(2^qq^{-k-\frac{1}{2}}). \]

1. N. Alon and J. Spencer, The Probabilistic Method, 2nd ed., John Wiley, 2000.
2. A. Pelc, Solution to Ulam's problem on searching with a lie, J. Combinatorial Theory, Ser. A. 44 (1987), 129-142
3. A. R\'{e}nyi, {\em A Diary on Information Theory}, J. Wiley and Sons, 1984.
4. J. Spencer, Ulam's searching problem with a fixed number of lies, {\em Theoretical Computer Science} \textbf{95} (1992), 307-321
5. S. M. Ulam, \textit{Adventures of a Mathematician}, Charles Scribners's Sons, New York, 1976.