lower bound for Renyi–Ulam Game with lies

Question

Player $A$ thinks of number between 1 and $n$ and ask $B$ to guess the number with minimum number of decision queries (yes or no type ).

Game :

1. $A$ chooses an element in {1,2....,n}

2. $B$ tries to guess this number by asking Yes/No questions.

Binary search is a way to solve the problem, so with $\log n$ many queries will be sufficient to solve the problem when player $A$ does not lie. But if player $A$ lie exactly one time than we can problem with $2\log n$ many queries (by just asking the same query two times). There is an optimal way to solve this problem with $ \log n + \log \log n +c$ , where $c$ is a constant. We will first ask $\log n $ many queries to $B$ and going to get a $\log n $ bits long binary string and now apply binary search on this binary string. In general when A is allowed to lie say $l$ (constant) then also the number of queries need to solved the problem is $ \log n + \log\log n + c $

Questions : 1) How to prove that $ \log n + \log\log n + c$ is a lower bound ?

2) If only $\log n$ many queries are allowed in the general case Is there an approximation algorithm for this game ( original solution = $a$ * algorithm's solution, where $a$ is constant).

3) If $l$ is very large (say order of $n$) Is it possible in that case to correctly find out the guessed number ? I tried to use the Hamming distance but not able to come up with a precise answer.

Reference :http://ac.els-cdn.com/S0304397503005814/1-s2.0-S0304397503005814-main.pdf?_tid=a880fa14-f82d-11e6-81df-00000aacb35e&acdnat=1487678746_7307f01621c154d9f6e006fc8b992ad0

Answer 1

For the first question, suppose that you have an algorithm that supports one error, and uses $m$ questions. For each element $i \in \{1,\ldots,n\}$, let $x_{i0}$ be the vector containing the answers to all questions when A doesn't lie, and let $x_{ij}$ be the vector containing the answers to all questions when A lies in question $j$. In total, we have $n$ collections of $m+1$ vectors. All these vectors are distinct: the $m+1$ vectors in a collection are distinct by definition, and vectors belonging to different collections must be distinct since the correct answer is different. We deduce that $(m+1)n \leq 2^m$, and so $m \geq \log n + \log\log n + \Omega(1)$.

For the second question, here is something to try. Let $m$ be a number so that $\log n$ queries suffice to find an element in $\{1,\ldots,m\}$, even when A is allowed to lie at most once. Partition $\{1,\ldots,n\}$ into $m$ intervals $[x_1,x_2),[x_2,x_3),\ldots,[x_m,x_{m+1})$, where $[a,b) = \{a,\ldots,b-1\}$, $x_1 = 1$, and $x_{m+1} = n+1$. Then this gives an $\alpha$-approximation for $\alpha = \max \frac{x_{i+1}-1}{x_i}$. I leave the rest to you.

The third question is addressed in Three thresholds for a liar by Spencer and Winkler. The threshold is $n/3$ (a strategy exists if $\ell < n/3$).