gulak@eecg.toronto.edu (Glenn Gulak) (05/25/89)
SEMINAR
Monday, May 29, 1989
2:00 - 3:00 pm
Room 202, Galbraith Bldg
Who should speak when I want to talk:
feedback in discrete communication
Alon Orlitsky
AT&T Bell Laboratories
S_X and S_Y are finite sets. (X,Y) is a random variable distributed over
S_X \times S_Y according to some probability distribution p(x,y). Person
P_X knows X, Person P_Y knows Y, and both know p. They communicate in order
for P_Y to learn X. P_X may or may not learn Y. How many information bits
must be transmitted (by both persons) in the worst case?
C_1(p) is the number of bits required when only one message is allowed,
necessarily from P_X to P_Y. C_2(p) is the number of bits required when
only two messages are permitted: P_Y transmits a message to P_X then P_X
responds with a message to P_Y. C_\infty(p) is the number of bits required
when P_X and P_Y can communicate back and forth. Messages from P_Y to P_X
are called feedback.
The maximal reduction in communication achievable via feedback is one bit
away from logarithmic: C_\infty(p) >= log C_1(p) + 1 for all probability
distributions p, while there are distributions for which equality holds.
Therefore C_1(p) can be exponentially larger than C_\infty(p). Yet C_2(p)
cannot. With just one feedback message the number of bits required is at
most four times larger than the minimal: C_2(p) <= 4*C_\infty(p)+2.
Surprisingly, for almost all sparse probability distributions, P_Y who
wants to say nothing must transmit almost all the bits in order to achieve
the minimal number: C_\infty(p). The number of bits transmitted by P_Y can
be appreciably reduced only if P_X transmits exponentially more than
C_\infty(p) bits.
__________________________________________________________________________rackoff@ai.toronto.edu (Charles Rackoff) (05/25/89)
Don't forget Silvio Micali's seminar tomorrow at 11:00. Charlie