Understanding the flaw in a proof attempt of the Communication Complexity of Equality

Question

I'm new to communication theory and I've been wondering where the following simple argument fails:

Equality Problem We have two players, player 1 Alice who gets an $n$-bit vector $X$ and player 2 Bob who gets an $n$-bit vector $Y$. We want one of them to output $1$ if and only if for all indices $i:$ $X[i] = Y[i]$.
Suppose that I choose the inputs $X$ and $Y$ uniformly at random from the set $\{0,1\}^n$. Initially, Alice knows nothing about Bob's input $Y$. Consider a protocol $P$ for equality. Alice and Bob run $P$ and assume that $P$ outputs $1$. By the correctness of $P$, Alice knows that for each index $i$, $Y[i] = X[i]$. Thus Alice has learned $|Y|=n$ bits . Doesn't this immediately imply the $\Omega(n)$ lower bound for $P$?

Note: Of course, I know that the above argument must be flawed since we can solve equality with $O(\log n)$ bits when allowing randomization. I'm just trying to understand why my proof attempt is flawed.

Answer 1

This vague argument can be made to work for deterministic communication complexity. In the randomized setting, protocols are allowed to err. Consider the standard protocol in which both players exchange a random hash of their inputs to some set of size $2^m$. They only learn $m$ bits of each other's input. When both hashes agree, they aren't completely sure that $X=Y$, and in particular no party has learned the other party's input.