Testing for equality with zero error This question comes from what I asked in a comment here, although I realized that
I don't actually care about which input is less than the other, if they're different.

Alice and Bob have n-bit strings, and want to figure out if they're equal
while doing little communication. $\:$ They can use a randomized solution,
but there must be zero chance of getting the wrong answer.

Parametrized by $n$, how much communication is needed to for a protocol that:


outputs one of {NO,MAYBE,YES}
for all input pairs, the probability of the protocol outputting MAYBE on that pair is at most 1/2
the protocol never outputs YES on unequal inputs, and never outputs NO on equal inputs
?


Since this falls between the deterministic and the standard randomized cases,
the bounds for those are upper and lower bounds, respectively, for this question.
Let $D$ be the distribution on inputs that w.p. $p = 1/(1+\epsilon)$ picks $(x,x)$ for random $x$, and w.p. $1-p$ picks $(x,y)$ for random $x \neq y$. An appropriate choice of random coins leads to a deterministic protocol that never makes mistakes and outputs MAYBE w.p. at most $1/2$ with respect to $D$. In particular, it must answer YES on at least $1-(1/2)/p = 1/2 - \epsilon/2$ of the nodes $(x,x)$.

Suppose that the protocol uses $C$ bits of communications. It therefore has at most $2^C$ leaves. Each leaf is a monochromatic combinatorial rectangle, and so each of the at least $(1-\epsilon) 2^{n-1}$ YES answers must end up in a different leaf. We conclude that $C \geq n-1$.