PUB - Publikationen an der Universität Bielefeld

Witsenhausen's hyperbola bound for the multiple description problem without excess rate in case of a binary source is not tight for exact joint reproductions. However, this bound is tight for almost-exact joint reproductions (Theorem1, conjectured by Witsenhausen). The proof is based on an {em approximative} form of the team guessing lemma for {em sequences} of random variables. (This result may be of interest also for team guessing). The hyperbola bound is also tight for exact joint reproductions and arbitrarily small, but positive, excess rate (Theorem2). The proof of this result uses our covering lemma.