Average-Case Interactive Communication of Uniform Pairs.

Two random variables, X and Y, are distributed uniformly over some support set. Person P sub X knows X and Person P sub Y knows Y. Both want P sub Y to learn X whereas P sub X may or may not learn Y. To that end, P sub X and P sub Y alternate in transmitting messages - sequences of binary bits - over an error-free channel. How many bits must be transmitted on the average if only m messages are permitted? Let C bar inf (X|Y) be the number of bits required when there is no restriction on the number of messages. If only one message is permitted (necessarily from P sub X to P sub Y), the number of bits required may be arbitrarily high.