Three results on interactive communication

X and Y are random variables. Person P/sub x/ knows X, Person P/sub y/ knows Y, and both know the underlying probability distribution of the random pair (X, Y). Using a predetermined protocol, they exchange messages over a binary, error-free, channel in order for P/sub y/ to learn X. P/sub x/ may or may not learn Y. C/sub m/ is the number of information bits that must be transmitted (by both persons) in the worst case if only m messages are allowed. C/sub infinity / is the corresponding number of bits when there is no restriction on the number of messages exchanged. We consider three aspects of this problem. C/sub 4/. It is known that one-message communication may require exponentially more bits than the minimum possible: for some random pairs, C/sub 1/=2/sup C infinity -1/. Yet just two messages suffice to reduce communication to almost the minimum: for all random pairs, C/sub 2/or=(2- in )C/sub infinity />or=c. Asymptotically, this is the largest possible discrepancy. Amortized complexity. The amortized complexity of (X,Y) is the limit, as k grows, of the number of bits required in the worst case for L independent repetitions of (X, Y), normalized by k. We show that the four-message amortized complexity of all random pairs is exactly log mu . Hence, when a random pair is repeated many times, no bits can be saved if P/sub x/ knows Y in advance.>