Feedback in discrete communication.

01 January 1988

New Image

X and Y are finite sets. (X,Y) is a random variable distributed over X x Y according to some probability distribution p(x,y). Person Px knows X, Person Py knows Y, and both know p. They communicate in order for Py to know X. Px may or may not know Y. How many information bits must be transmitted (by both persons) in the worst case? C sub 1 (p) is the number of bits required when only one message is allowed, necessarily from Px to Py. C sub 2 (p) is the number of bits required when only two messages are permitted.