A converse theorem for the multiple description problem

Consider a sequence of discrete i.i.d random variables x/sub 1/,...,x/sub n/ and a distortion measure d(x,x/spl circ/) on the estimate x/spl circ/ of x. Two descriptions i(x)/spl isin/{1,2,...,2/sup nR1/} and j(r)/spl isin/{1,2,...,2/sup nR2/} are given of the sequences x=(x/sub 1/,...,x/sub n/). From these two descriptions, three estimates x/spl circ//sub 1/(i),x/spl circ//sub 2/(j) and x/spl circ//sub 0/(i,j) are formed, with resulting expected distortions: E{1/n/spl Sigma//sub k=1//sup n/d(x/sub k/,x/spl circ//sub mk/)}/spl les//spl Delta//sub m/, m=0,1,2. We find that the set (R/sub 1/,R/sub 2/,/spl Delta//sub 0/,/spl Delta//sub 1/,/spl Delta//sub 2/) is achievable only if there exists a probability mass distribution p(x)p(x/spl circ//sub 0/,x/spl circ//sub 1/,x/spl circ//sub 2/|x) with E1/n/spl Sigma//sub k=1//sup n/d(x/sub k/,x/spl circ//sub mk/)/spl les/m=0,1,2 such that: R/sub 1//spl ges/I(x;x/spl circ//sub 1/); R/sub 2//spl ges/I(x;x/spl circ//sub 2/); R/sub 1/+R/sub 2//spl ges/I(x;x/spl circ//sub 0/|x/spl circ//sub 1/,x/spl circ//sub 2/)+I(x;x/spl circ//sub 1/)+I(x;x/spl circ//sub 2/); where I(/spl middot/) denotes the Shannon mutual information. I(x;x/spl circ//sub 1/) and I(x;x/spl circ//sub 2/) are the necessary rates for achieving the expected distortions /spl Delta//sub 1/ and /spl Delta//sub 2/ respectively. The excess rate I(x;x/spl circ//sub 0/|x/spl circ//sub 1/,x/spl circ//sub 2/) should be added to I(x;x/spl circ//sub 1/) and I(x;x/spl circ//sub 2/) for ensuring that x/spl circ//sub 0/ has distortion less or equal to /spl Delta//sub 0/. This result has an interesting intuitive interpretation.