3 MESSAGES ARE NOT OPTIMAL IN WORST-CASE INTERACTIVE COMMUNICATION

Let X and Y be two jointly distributed random variables. Suppose perso n P(x), the informant, knows X, and person P(y), 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 P(y) to learn X, whereas P(x) may or may no t learn Y. C(m) (X \ Y) is the minimum number of bits required to be t ransmitted (by both persons) in the worst case when only m message exc hanges are allowed. C(infinity)(X \ Y) is the number of bits required when P(x) and P(y) can communicate back and forth an arbitrary number of times. Orlitsky proved that for all (X, Y) pairs, C2(X \ Y) less-th an-or-equal-to 4C(infinity) (X \ Y) + 3, and that for every positive c and epsilon with epsilon < 1, there exist (X, Y) pairs with C2(X \ Y) greater-than-or-equal-to (2 - epsilon)C3 (X \ Y) greater-than-or-equa l-to (2 - epsilon)C-infinity(X \ Y) greater-than-or-equal-to c. These results show that two messages are almost optimal, but not optimal. A natural question, then, is whether three messages are asymptotically o ptimal. In this work, we prove that for any c and epsilon with 0 < eps ilon < 1 and c > 0, there exist some (X, Y) pairs for which C3(X \ Y) greater-than-or-equal-to (2 - epsilon)C4 (X \ Y) greater-than-or-equal -to c. That is, three messages are not optimal either.