In the universal relation $UR_n$ problem [1] of communication complexity, there are two players Alice and Bob. Alice gets a string $x \in \{0,1\}^n$, Bob gets a string $y \in \{0,1\}^n$ with the promise that $x \ne y$. The players exchange messages and the last player to receive a message must output an index $i \in [n]$ such that $x_i \ne y_i$. Moreover, the players have access to public randomness.
In a recent talk that I attended, the speaker mentioned that the following without giving a proof:
Any protocol for $UR_n$ can be transformed into an $UR_n$ protocol that has the additional property that each possible index $i$ where $x_i \ne y_i$ is output with the same probability, without changing the communication complexity.
I have been thinking about this for a while, but I could not come up with a proof. I would be thankful for any suggestions or pointers to literature.
[1] Mauricio Karchmer and Avi Wigderson. Monotone circuits for connectivity require super-logarithmic depth. In Proceedings of the twentieth annual ACM symposium on Theory of computing, STOC ’88, pages 539–550, New York, NY, USA, 1988. ACM.