Three Messages Are Not Optimal in Worst Case Interactive Communication

Let X and Y be two jointly distributed random variables. Suppose person PX, the informant, knows X, and person Py, the recipient, knows Y, and both know the joint probability distribution of the pair (X, Y). Using a predetermined protocol, they communicate over a binary error-free channel in order for Py to learn X, whereas PXmay or may not learn Y. Cm(X| Y) is the minimum number of bits required to be transmitted (by both persons) in the worst case when only m message exchanges are allowed. Coo(X| Y) is the number of bits required when PXand Py can communicate back and forth an arbitrary number of times. Orlitsky proved that for all (X, Y) pairs, c2(x \\\\\\\\ y) < 4cĈ⧜(x \\\\\\\\ y) + 3, and that for every positive c and ∊ with ∊ < 1, there exist (X, Y) pairs with C2(X| Y) > (2 - ∊)C3 (X | Y) > (2 - ∊)C-∞(X | Y) > c. These results show that two messages are almost optimal, but not optimal. A natural question, then, is whether three messages are asymptotically optimal. In this work, we prove that for any c and ∊ with 0 < ∊ < 1 and c > 0, there exist some (X,Y) pairs for which C3(X \\\\\\\\ Y) > (2 — ∊ )C4(X | Y) > c. That is, three messages are not optimal either.