Identifying a Truth-Teller With One Question
Two people answer yes/no questions. Person $A$ always tells the truth. Person $B$ answers randomly -- independently saying "yes" or "no" with probability $1/2$ each, regardless of the question asked. You do not know which person is $A$ and which is $B$.
You may ask exactly one yes/no question to exactly one person.
- Construct a question that lets you identify the truthful person with probability strictly greater than $1/2$.
- Compute that probability of correct identification.
- Prove that your strategy is optimal -- no single yes/no question to one person can do better.
Hints
- Think about what happens when you ask someone a question whose truthful answer you already know -- the truth-teller's response is deterministic, while the random person's is a coin flip.
- Consider asking a self-referential question like "Are you the truth-teller?" and think about how each person's answer distribution differs.
- If the truth-teller always says "Yes" to your question, then a "No" answer is a sure signal you are talking to the random person. Use that asymmetry in your decision rule to get $P(\text{correct}) = 3/4$.
Worked Solution
How to Think About It: The key structural constraint is that the truth-teller's answer to any yes/no question is deterministic (it is pinned to the truth), while the random answerer's response is a fair coin flip independent of everything. So you are really trying to design a question where the deterministic answer from the truth-teller gives you useful information, and then exploit the fact that the random answerer only matches that answer half the time. The best you can hope for is to separate the two people's answer distributions as much as possible -- and since one distribution is a point mass and the other is a fair coin, the maximum separation is already baked in.
Quick Estimate: Pick one person at random and ask them something where the truthful answer is "Yes" with certainty. If they say "Yes", guess they are the truth-teller; if "No", guess the other. You are right when (a) you picked the truth-teller (prob $1/2$) and they say "Yes" (prob $1$), or (b) you picked the random answerer (prob $1/2$) and they say "No" (prob $1/2$). That gives $1/2 + 1/4 = 3/4$. So the answer is $3/4$ -- and we should verify this is optimal.
Approach: We construct the explicit question, compute the success probability, and then prove no strategy beats $3/4$.
Formal Solution:
*Step 1 -- The question.* Pick one of the two people (call them Person $X$). Ask Person $X$:
"Are you the person who always tells the truth?"
*Step 2 -- Analysis by cases.*
- Case 1: $X = A$ (truth-teller). The truthful answer is "Yes" (since $A$ is indeed the truth-teller). So $A$ answers "Yes" with probability $1$.
- Case 2: $X = B$ (random answerer). Regardless of the question, $B$ says "Yes" with probability $1/2$ and "No" with probability $1/2$.
*Step 3 -- Decision rule.* If Person $X$ says "Yes", guess that $X$ is the truth-teller. If Person $X$ says "No", guess that the other person is the truth-teller.
*Step 4 -- Success probability.* Since each person is equally likely to be the one you picked:
$$P(\text{correct}) = P(X = A) \cdot P(A \text{ says Yes}) + P(X = B) \cdot P(B \text{ says No})$$
$$= \frac{1}{2} \cdot 1 + \frac{1}{2} \cdot \frac{1}{2} = \frac{3}{4}$$
*Step 5 -- Why $3/4$ is optimal (and you can't do better).*
Design any self-referential question you like so that "Yes" maps to person $A$ and "No" maps to person $B$ (or vice versa). The truth-teller's answer will always reliably encode the correct identity. The problem is the random answerer.
There is a $1/2$ chance the person you happen to ask is person $B$. And there is a $1/2$ chance that $B$ gives the exact same answer $A$ would have given. So with probability $1/2 \times 1/2 = 1/4$, you are in a world where $B$'s response is indistinguishable from $A$'s — and no question design can fix this, because $B$'s answer is an independent coin flip.
That $1/4$ penalty is unavoidable. The best any strategy can achieve is $1 - 1/4 = 3/4$.
Answer: Ask one person "Are you the truth-teller?" If they say "Yes", guess they are the truth-teller; if "No", guess the other person. The probability of correct identification is $3/4$, and this is optimal.
Intuition
The reason $3/4$ is both achievable and optimal comes down to information theory: you are trying to distinguish a deterministic source from a random one using a single binary observation. The truth-teller's answer is fixed (say, always "Yes" to the right question), so it carries zero entropy. The random answerer's response is a fair coin flip with one bit of entropy. When you observe the answer, you are running a hypothesis test between a point mass and a Bernoulli(1/2). Half the time the random answerer happens to match the truth-teller's answer, and you cannot distinguish them. The other half, the random answerer gives the opposite answer, and you know for certain you are talking to the random person. This gives you a $1/4$ information bonus on top of the $1/2$ baseline of pure guessing.
This structure appears constantly in quant interviews and trading: you have one informative signal mixed with noise, and you want to extract as much as possible from a single observation. The lesson is that even one question can be surprisingly powerful ($3/4$ beats $1/2$ by a lot), but there is a hard ceiling set by the noise source's randomness. No amount of cleverness in question design can overcome the fact that a fair coin agrees with any fixed answer exactly half the time.