In channels with action dependent states, a message is conveyed using two encoders operating sequentially, viz. an action encoder and a channel encoder. The actions drive the output of a discrete-memoryless channel (DMC), which in turn forms the state process for the DMC between the channel encoder and receiver. Assuming non-causal knowledge of the state-process at the channel encoder, a single letter characterization of the capacity is known in the discrete memoryless case. We consider the action dependent state channel where an additional private message needs to be communicated by the channel encoder. In addition, we consider a common reconstruction (CR) of the state at the channel encoder and decoder. Capacity characterizations for the discrete memoryless and Gaussian versions are presented. As a consequence, we settle the capacity characterization of the Gaussian action dependent channel with only a common message and CR. We further show that the availability of strictly causal state feedback to the action encoder, even with randomization allowed, does not improve the capacity of the action dependent state channel. I. I NTRODUCTION The problem of coding for channels with state was introduced in the seminal paper by Shannon [1], wherein causal state information was assumed at the encoder. The capacity for the non-causal setting was established by Gelfand and Pinsker [2]. In these models, the state process is assumed to be given by nature. Motivated by applications involving multi-stage encoding (for instance, two-stage recording on a magnetic storage device), Weissman [3] introduced the notion of a channel with action dependent states (ADSC). In this setting, the transmitter can take actions that inﬂuence the formation of channel states in the ﬁrst stage, and the encoding in the second stage is based upon the channel state sequence so generated and the message. Notice that the actions play a dual role of message communication as well as controlling the channel states. The capacity of this model was derived in [3]. Following [3], the action-dependent framework has been extended in several directions. Permuter et al.[4] studied the source coding dual in which the decoder can take actions based on the observed compression index that inﬂuence the formation of side information. Asnani et al. [5] considered a setting in which the encoder as well as the decoder can take probing actions to learn the channel state, with a cost constraint associated with each. Choudhuri et al. [6] considered causal state communication over an action-dependent channel and characterized the trade-off between message communication and state estimation distortion. Ahmadi et al. [7] studied action-dependent channels with the additional constraint of common reconstructions (CR) [8] of the state at the encoder and decoder. Recently, Kittichokechai et al.[9] studied source and channel coding settings with action-dependent states and CR constraints, wherein the actions control the partial channel state information available at the encoder and decoder. The action dependent model has been extended to multi-user channels as well– for instance see Steinberg et al. [10] and Steinberg [11]. 2 Notice that single letter capacity characterizations for the discrete-memoryless action dependent state channel (DMADSC) as well as the DMADSC with CR constraints were presented in [3] and [7] respectively. However, the Gaussian counterparts are listed therein as open problems. Another interesting question listed in [3] is whether strictly causal state-information at the action encoder increases the capacity. In this work, we consider a more general model where the channel encoder has an additional private message stream along with CR constraints. Our contributions are summarized below. The capacity region for the ADSC with additional private message and CR is derived for both the discrete-memoryless and Gaussian versions. We prove the optimality of Gaussian auxiliaries for the Gaussian action dependent model with CR constraints [7]. We show that the capacity of an ADSC is unchanged by strictly causal state feedback to the action encoder, even if the encoders are allowed to randomize, thereby settling a question left open in [3]. We note that our problem framework without common reconstruction constraints is somewhat similar to the co-operative multiple access model studied by Zaidi et al. [12] [13]. The setting in [13] consists of a state dependent multiple access channel with degraded message sets, wherein the encoder sending only the common message (non-cognizant encoder) observes the state strictly causally, while the other encoder observes the state non-causally. The capacity region was derived for both the discrete memoryless as well as Gaussian versions, with the observation that strictly causal state information can enlarge the capacity region compared to the case of no state observation at the non-cognizant encoder. Though the action encoder in our setting can be viewed to be playing the role of the non-cognizant encoder, the fundamental difference between the two settings is that the state Snin [13] is generated by nature IID, while it is the output of a DMC fed with the message dependent action sequence in our case. An equivalence can be established between the two settings if and only if p(sja) =p(s), i.e. the state sequence is independent of the action sequence. As such, our conclusion that strictly causal state feedback does not increase the capacity for the common message case is consistent with the observation that the common message capacity in [13] is independent of strictly causal state observation at the non-cognizant encoder- see Corollary 2and Remark 5in [13]. Nevertheless, the capacity region in the Gaussian case without common reconstructions is the same as that established in Theorem 4and Corollary 3of [13]. The novelty in our model is that we are interested in common reconstruction of the state process in the action-dependent setting with additional messages, which also settles the optimality of Gaussian auxiliaries for the model studied in [7]. Organization : We introduce the system model and main results in Section II. Section III contains the proof of our main result. The extension to the Gaussian case is given in Section IV, which also deals with the Gaussian action dependent channel with common reconstruction constraints as well as reversible input constraints. The generalization of strictly causal state information with randomization at the action encoder is discussed in Section V. Concluding remarks are given in Section VI. II. S YSTEM MODEL Consider the model shown in Fig. 1. There are two encoders, namely an action encoder Eactand a channel encoderEchan. A common message Wcis observed by both EactandEchan. The action encoder chooses the output symbol a2A which is fed to a DMC p(sja). The output of this DMC forms the state sequence of a channel with input x2X , outputy2Y and transition probability p(yjx;s). The encoder Echanhas non-causal access to the state sequence Sn.Echanalso needs to convey a private message W1. We term this model as DMADSC with additional private message . More generally, one can consider common reconstruction (CR) of the state process [8], wherein Echanand the decoder must agree on a reconstruction of the state viz. ^Sn. We call this model as DMADSC with CR . The inputs have to satisfy an average cost constraint deﬁned by a vector function :AX ! [0;1)2, where the cost function for sequences is 3 EactAn p(sja) EchanXnWc Dec W1^Snp(yjx;s)YnSn ^Wc ^Sn d ^W1 Fig. 1. Action-Dependent Channel with additional private message, and with/without common reconstructions deﬁned as (an;xn) =1 nPn i=1 (ai;xi). Deﬁne a single letter distortion measure d:S ^S! [0;1)for state reconstruction, where the distortion between sequences is deﬁned as d(sn;^sn) =1 nPn i=1d(si;^si). We assume that the distortion measure is bounded and let Dmax= maxs2S;^s2^Sd(s;^s). We also assume that all the alphabetsjAj,jSj,jXj,jYj,j^Sjare ﬁnite. Deﬁnition 1. Letbe a vector in R2 +. For the DMADSC with additional private message, an (n;R 1;Rc;;) scheme consists of two encoder maps: An(Wc) : [1 : 2nRc]!An; Xn(Wc;W1;Sn) : [1 : 2nRc][1 : 2nR1]Sn!Xn; and a decoding map (Yn) :Yn![1 : 2nR1][1 : 2nRc]such that for independent and uniformly distributed choices of (Wc;W1), we have P( (Yn)6= (W1;Wc)); (1) nX i=1E[ k(Ai;Xi)]n(k+);k= 1;2: (2) (where kandkrepresent the kth coordinates of and.) For the DMADSC with CR, we additionally deﬁne a sender quantization map :Snf1;;2nRcg f1;;2nR1g! ^Snand a decoder reconstruction map 2(Yn) :Yn!^Sns.t. P( 2(Yn)6= (Sn;Wc;W1)); (3) E[d(Sn; 2(Yn))]n(D+): (4) We say that a tuple (R1;Rc;D;)is achievable if an (n;R 1;Rc;D;;)coding scheme exists for every >0for sufﬁciently large n. LetCdmadsc CR be the collection of all achievable (R1;Rc;D;)tuples. Our main result is stated now. Theorem 2. For the DMADSC (p(sja);p(yjx;s))with CR,Cdmadsc CR is the closure of the union of all (R1;Rc;D;)tuples such that R1I(U;YjA)I(U;SjA); (5) R1+RcI(A;U;Y)I(U;SjA); (6) where the union is over distributions of the form p(a)p(sja)p(uja;s)p(xju;s)p(yjx;s)for which there exists a map :U ! ^Ssuch that E[d(S; (U))]DandE[ (A;X )](where the cost constraint is to be understood componentwise), with jUjjAjjXjjSj + 2. Notice that U!(X;S)!Yand A!(U;S)!Xare Markov chains. Remark 3. For the special case of no CR (i.e. DDmax) andRc= 0 (Wc= ), the private message capacity is R1 max a2A;p(uja;s);p(xju;s)[I(U;YjA=a)I(U;SjA=a)]; 4 which corresponds to selecting the action sequence that leads to the maximum Gelfand-Pinsker rate. On the other hand, when DDmaxandR1= 0 (W1= ), the common message capacity is Rc max p(a);p(uja;s);p(xju;s)[I(A;U;Y)I(U;SjA)]; which is nothing but the characterization in [3, Theorem 1]. III. P ROOF OF THEOREM 2 Proof of Achievability: The achievability is proven using a combination of Gelfand-Pinsker (GP) coding and superposition coding. Here, an action codebook is built ﬁrst based on the common message. Then for eachan(action) sequence, a conditional GP codebook Ushall be generated according to the private message. The details are given in Appendix A. Proof of Converse: By Fano’s inequality, we can write: H(W1;Wc;^SnjYn)nn;wherenn!1! 0: (7) We suppress the nnterms in the sequel. We can write the following chain of inequalities for the private rate: nR1=H(W1)(a)=H(W1jWc) =H(^Sn;W1jWc)H(^SnjW1;Wc) (b)=H(^Sn;W1jWc)H(^SnjW1;Wc) +H(^SnjW1;Wc;Sn) (c)I(^Sn;W1;YnjWc;An)I(^Sn;SnjW1;Wc;An) (d)=I(^Sn;W1;YnjWc;An)I(^Sn;W1;SnjWc;An) =nX i=1h I(^Sn;W1;YijWc;Yi1;An)I(^Sn;W1;SijWc;An;Sn i+1)i (e) nX i=1h I(^Sn;W1;Wc;Yi1;Ai1;An i+1;YijAi)I(^Sn;W1;Wc;Sn i+1;Ai1;An i+1;SijAi)i (f)=nX i=1h I(^Sn;W1;Wc;Yi1;Sn i+1;An;YijAi)I(^Sn;W1;Wc;Yi1;Sn i+1;An;SijAi)i (g)=nX i=1[I(Ui;YijAi)I(Ui;SijAi)]; (8) where (a) follows since W1? ?Wc, (b) follows since ^Snis a deterministic function of (W1;Wc;Sn), (c) follows from Fano’s inequality and since WcdeterminesAn, (d) follows since (W1;Wc)!An!Sn, (e) follows since Si!Ai!(Wc;Sn i+1;Ai1;An i+1), (f) follows from the Csisz ´ar sum lemma and (g) follows with a choice of Ui= (^Sn;W1;Wc;Yi1;Sn i+1;An)that satisﬁes the Markov conditions Ui!(Xi;Si)!Yi andAi!(Ui;Si)!Xi. Now by introducing a time-sharing random variable Q, independent of everything else and uniformly drawn on [1 :n], we have nR1n[I(UQ;YQjAQ;Q)I(UQ;SQjAQ;Q)] =n[I(UQ;YQjAQ;Q)I(UQ;Q;SQjAQ)] n[I(UQ;Q;YQjAQ)I(UQ;Q;SQjAQ)]: (9) Now the proof is completed by replacing (Q;UQ) =U,YQ=Y,SQ=S,XQ=XandAQ=Aand noting that the Markov conditions U!(X;S)!YandA!(U;S)!Xhold. For the sum rate, consider the 5 following chain of inequalities: n(R1+Rc) =H(W1;Wc) =H(^Sn;W1;Wc)H(^SnjW1;Wc) (a)=H(^Sn;W1;Wc;An)I(^Sn;SnjW1;Wc;An) (b)I(^Sn;W1;Wc;An;Yn)I(^Sn;SnjW1;Wc;An) (c)=I(^Sn;W1;Wc;An;Yn)I(^Sn;W1;Wc;SnjAn) (d) nX i=1h I(^Sn;W1;Wc;Yi1;An;Yi)I(^Sn;W1;Wc;Sn i+1;Ai1;An i+1;SijAi)i (e)=nX i=1h I(^Sn;W1;Wc;Yi1;Sn i+1;An;Yi)I(^Sn;W1;Wc;Yi1;Sn i+1;An;SijAi)i (f)=nX i=1[I(Ui;Ai;Yi)I(Ui;SijAi)]; (10) where (a) follows since ^Snis a deterministic function of (W1;Wc;Sn)and sinceWcdetermines An, (b) follows from Fano’s inequality, (c) follows since (W1;Wc)!An!Sn, (d) follows since Si!Ai! (Sn i+1;Ai1;An i+1), (e) follows from the Csisz ´ar sum lemma and (f) follows since Ui= (^Sn;W1;Wc;Yi1;Sn i+1;An). Now by introducing a time-sharing RV Q, as in (9), we have n(R1+Rc)nX i=1[I(Ui;Ai;YijQ=i)I(Ui;SijAi;Q=i)] =n[I(UQ;AQ;YQjQ)I(UQ;SQjAQ;Q)] =n[I(UQ;AQ;YQjQ)I(UQ;Q;SQjAQ)] n[I(UQ;Q;AQ;YQ)I(UQ;Q;SQjAQ)]: (11) For the bound on input costs, we proceed as follows: E[ k(A;X )] =X a;xP(A=a;X =x) k(a;x) =X a;xP(AQ=a;XQ=x) k(a;x) =X a;xnX i=1P(AQ=a;XQ=xjQ=i)P(Q=i) k(a;x) =1 nnX i=1X a;xP(Ai=a;Xi=x) k(a;x) =1 nnX i=1E[ k(Ai;Xi)](k+);k= 1;2; (12) where the last step follows from the fact that for any successful (n;R 1;Rc;D;;)scheme, we have from (2) n(k+)nX i=1E[ k(Ai;Xi)];k= 1;2: (13) We next consider the bound on the distortion. Let ^Sn dbe the receiver’s reconstruction of the state sequence. 6 Deﬁne the eventB:=f^Sn=^Sn dg. Notice that P(B)1;8>0. Hence n(D+)nX i=1Eh d(Si;^Sdi)i =EB"nX i=1Eh d(Si;^Sdi)i B# P(B)nX i=1Eh d(Si;^Si)i (a) (1)nX i=1E[d(Si; i(Ui))] =n(1)EQ[E[d(SQ; Q(UQ))]jQ] =n(1)E[d(SQ; Q(UQ))] =n(1)E[d(S; Q(UQ))] (b)=n(1)E[d(S; (UQ;Q))] (c)=n(1)E[d(S; (U))]; where (a) follows by taking i(Ui) =^Si, (b) follows by deﬁning : (Q;UQ)7! Q(UQ)and (c) follows since (UQ;Q) =U. Finally, the bound on jUjfollows by an application of the support lemma [14, Appendix C]. IV. G AUSSIAN SETTING The Gaussian action-dependent state channel [3] (GADSC) is given by Y=X+A+W+Z; (14) withWN(0;2 W)andZN(0;2 Z),W? ?Z, andAandXbeing constrained in average power to PA andPXrespectively. The state itself is given by S=A+W, withAbeing independent of W. We have the following theorem. Theorem 4. For the GADSC with CR constraints, the capacity region is achieved by appropriate jointly Gaussian choices of p(a),p(u;xja;s)in Theorem 2. Speciﬁcally, the capacity region Cgadsc CR is given by Cgadsc CR=[ f(R1;Rc)jR1Rpriv;R1+RcRsumg; (15) where the union is over 1;22[1;1]satisfying2 1+2 21andD(12 2)PX2 W PX+ 22 W+2 2p PX2 W, for the rate functions (Rpriv;Rsum)as in (19),(20) and as in (23). Proof. We will prove this theorem using the single-letter expression in Theorem 2. While Theorem 2 was shown for the discrete memoryless case, it does hold for the Gaussian case as well. The achievability of Theorem 2 for the Gaussian case follows from an application of the discretization procedure [14, Sec. 3.4.1]. But note that the converse for the discrete memoryless case assumed ﬁnite j^Sj(see (7), i.e. Fano’s inequality for ^Sn). However, without loss of generality, we can restrict attention to an exponential number of agreed reconstructions, i.e. j^Snj=O(2nc), wherecis a constant, as explained next. Remark 5. It can be shown that if there exists a scheme without any cardinality bounds on the reproductions which achieves (R1;Rc;D), then for any >0,(R1;Rc;D+)can be achieved using a scheme where the reproductions are conﬁned to lie in an alphabet of size which scales as 2nc(). This can be proven using, for instance, a scalar quantizer whose average distortion is and whose rate scales with nas2nc(). Thus, the converse of Theorem 2 also applies for the Gaussian case. 7 Rpriv(1;2) =1 2log2 Z+ (12 12 2)PX 2 Z ; (19) Rsum(1;2) =1 2log"2 Z+ (12 12 2)PX 2 Z PX+PA+2 Z+2 W+ 21pPXPA+ 22p PX2 W (12 1)PX+2 Z+2 W+ 22p PX2 W!# : (20)  We now prove the rest of the converse starting with expressions (5) and (6) from Section II: R1h(YjA)h(YjA;U)h(SjA) +h(SjA;U) =h(YjA)h(YjA;U;S )h(SjA) +h(SjY;A;U ) h(YjA)h(YjA;U;S;X )h(SjA) +h(SjY;A;U ) =h(YjA)h(Z)h(SjA) +h(SjY;A;U ) 1 2log" 2 YjA 2 Z! 2 SjY;A;U 2 W!# : (16) Similarly, for the sum rate R1+Rch(Y)h(YjU;A)h(SjA) +h(SjA;U) =h(Y)h(YjA;U)h(SjA) +h(SjA;U) =h(Y)h(YjA;U;S )h(SjA) +h(SjY;A;U ) h(Y)h(YjA;U;S;X )h(SjA) +h(SjY;A;U ) h(Y)h(Z)h(SjA) +h(SjY;A;U ) 1 2log"2 Y 2 Z 2 SjY;A;U 2 W!# : (17) where the variance terms in (16) and (17) are deﬁned as 2 SjY;A;U = min ; ; E[S Y A U]2: (18) Thus it can be seen that, via the differential entropy maximizing property of Gaussian random variables for a given variance, the optimal auxiliary Umust be jointly Gaussian with (A;S;X;Y ). This completes the proof of converse. For the achievability, we choose p(a),p(u;xja;s)as follows. The action input is chosen asAN(0;PA). We take the channel input to be X=1r PX PAA+2s PX 2 WW+G; (21) where1and2satisfy2 1+2 21, andGN (0;(12 12 2)PX)is independent of (A;W;Z ). We choose the auxiliary random variable as follows: U=X+A+ W; (22) where=1= 1q PX PA and the coefﬁcient is chosen as =(12 12 2)PX2q PX 2 W2 Z (12 12 2)PX+2 Z: (23) 8 The common reconstruction constraint is as follows: DE[S^S]2=Var [SjU;A]=(12 2)PX2 W PX+ 22 W+2 2p PX2 W: Now on evaluating the terms in (16), (17) with the above jointly Gaussian choices, we arrive at the rate constraints in (19), (20). Remark 6. For the GADSC with only a common message and CR constraints considered in [7], the capacity characterization can be obtained by setting W1= i.e.R1= 0in Theorem 4, which is given by (24). Note that [7] only gave an achievable region, while its optimality was not established therein. C(D) = max (1;2) 2 1+2 21;D(12 2)PX2 W PX+ 22 W+2 2p PX2 WRsum(1;2): (24) Remark 7. On further setting D2 W, i.e. the case of no CR constraints, the characterization simpliﬁes to C= max (1;2) 2 1+2 21Rsum(1;2); (25) which is a complete characterization of the Gaussian action dependent channel. This can also be inferred from the results in Zaidi et al. [12] [13, Theorem 4]. A. Action-Dependent Channels with Reversible inputs We consider a GADSC with reversible inputs, i.e. with an additional constraint that the input to the channel must be reconstructed reliably at the receiver, in addition to the message. [9] derived the capacity of this model in the discrete case to be C= maxI(A;X ;Y)I(X;SjA); (26) where the joint pmf is of the form p(a)p(sja)p(xja;s)p(yjx;s)and the maximization is over all p(a)and p(xja;s)such that 0I(X;YjA)I(X;SjA). In the following, we establish the capacity characterization in the Gaussian setting. The converse can be proved from the single letter characterization due to [9]: 0h(YjA)h(YjA;X )h(SjA) +h(SjA;X ) =h(YjA)h(YjA;X;S )h(SjA) +h(SjY;A;X ) h(YjA)h(Z)h(W) +h(SjY;A;X ) 1 2logVar [YjA] 2 ZVar [SjY;A;X ] 2 W ; (27) Similarly, we have Rh(Y)h(YjA;X )h(SjA) +h(SjA;X ) =h(Y)h(YjA;X )h(SjA) +h(SjA;X ) =h(Y)h(YjA;X;S )h(SjA) +h(SjY;A;X ) h(Y)h(Z)h(W) +h(SjY;A;X ) 1 2logVar [Y] 2 ZVar [SjY;A;X ] 2 W : (28) Thus it can be seen that via the max-entropy principle that (A;S;X;Y )must be jointly Gaussian. This completes the proof of converse. For the achievability, we now choose AN (0;PA)andp(xja;s)as in (21) and compute (27), (28). The ﬁnal characterization evaluates to (29), (30). 9 CRI= max (1;2):2 1+2 21 01 2log 12 12 2 (12 12 2)2 W+(12 1)2 Z (12 1)PX+2 Z+2 W+22p PX2 WRRI(1;2); (29) RRI(1;2) =1 2log12 12 2 (12 12 2)2 W+ (12 1)2 Z PX+PA+2 Z+2 W+ 21p PXPA+ 22q PX2 W : (30) V. S TRICTLY CAUSAL STATE WITH COMMON RANDOMNESS AT THE ACTION ENCODER In [3], the question of whether strictly causal state feedback to the action encoder can increase capacity was left open. In other words, the problem can be stated as whether actions of the form Ai(M;Si1)help compared to An(M). We additionally assume a more general encoding mechanism in which an unlimited amount of common randomness is allowed between the channel and action encoders, in the form of a real-valued RV uniformly distributed on [0;1]. We see that such state feedback does not help, and the capacity still remains C= max p(a);p(uja;s);p(xju;s)[I(A;U;Y)I(U;SjA)]: (31) In other words, the optimal strategy is the one which ignores the extra information Si1. The converse can be proved by a slightly different choice of auxiliary RV in [3], as shown next. nR=H(M)(a)=H(Mj) (b)I(M;Ynj) =nX i=1I(M;YijYn i+1;)nX i=1I(M;Yn i+1;Yij) =nX i=1[I(M;Yn i+1;Si1;Yij)I(Si1;YijM;Yn i+1;] (c) nX i=1[I(M;Yn i+1;Si1;;Yi)I(Si;Yn i+1jM;Si1;)] (d)=nX i=1[I(M;Yn i+1;Si1;;Ai;Yi)I(Si;Yn i+1jM;Si1;;Ai)] (e)=nX i=1[I(M;Yn i+1;Si1;;Ai1;Ai;Yi)I(M;Yn i+1;Si1;;Ai1;SijAi)] (f)=nX i=1[I(Ui;Ai;Yi)I(Ui;SijAi)] nmax [I(U;A;Y)I(U;SjA)]; (32) where (a) follows since M? ?, (b) follows from Fano’s inequality, (c) follows from the Csisz ´ar sum lemma, (d) follows since (M;Si1;)determines Ai, (e) follows since Si!Ai!(M;Si1;;Ai1) and (f) follows with a choice of Ui= (M;Si1;;Yn i+1;Ai1)that satisﬁes the Markov conditions Ui! (Xi;Si)!YiandAi!(Ui;Si)!Xi. 10 VI. C ONCLUSION We studied a generalization of the action-dependent channel with multiple messages and CR constraints, and derived complete characterizations for both discrete memoryless as well as Gaussian models. As a result, we obtained the capacity for a Gaussian action dependent model with only common message and CR. Furthermore, we proved that the capacity of the action-dependent model remains unchanged even if the actions are randomly drawn based on past channel states and the message. APPENDIX A ACHIEVABILITY PROOF FOR THEOREM 2 Codebook Generation: Fix the p.m.f. p(a)p(uja;s)p(xju;s). Randomly and independently generate 2nRc sequencesan(wc);wc2[1 : 2nRc]i.i.d. according toQn i=1pA(ai). For eachan(wc)sequence, randomly and conditionally independently generate 2n(R1+R0)sequencesun(wc;w1;j)forw12[1 : 2nR1]andj2[1 : 2nR0], i.i.d. according toQn i=1pUjA(uijai(wc)). LetBU(w1)be the set of sequences within the bin indexed by w12[1 : 2nR1]in theu- codebook. Encoding: Fix0>0. Givenwc2[1 : 2nRc], the action encoder selects the corresponding sequence an(wc) in theAcodebook. The state sequence Snis generated in response to the action sequence via the channel p(sja). Givenw12[1 : 2nR1], the channel encoder picks the least index jsuch that (an(wc);un(wc;w1;j);sn)2 Tn 0(U;A;S ). An error is declared if no such index is found. The channel encoder then draws xni.i.d. conditionally given (un;sn)according toQn i=1p(xijui;si), and sends it. The channel encoder also generates its state reconstruction ^Si= (ui);i2[1 :n]. Decoding: Let>0. We use simultaneous decoding. The decoder declares that ( ^wc;^w1)is sent if it is the unique message pair such that (an( ^wc);un( ^wc;^w1;^j);yn)2Tn (U;A;Y )for some ^j2BU( ^w1). An error is declared otherwise. Error Analysis: Assume without loss of generality that the messages W1= 1andWc= 1were sent, and the index of the chosen Unsequence is J. The encoding error events are E1=f(An(1);Un(1;1;j);Sn)=2Tn 08j2[1 : 2nR0]g: (33) The decoding error events at the receiver are as follows: E2=f(An(1);Un(1;w1;j);Yn)2Tn for somew16=1;j2BU(w1)g; E3=f(An(wc);Un(wc;w1;j);Yn) 2Tn (U;A;Y )for somewc6= 1;w16= 1;j2BU(w1)g; E4=f(An(wc);Un(wc;1;J);Yn)2Tn for somewc6= 1g: By the covering lemma [14], we have, P(E1)n!1! 0ifR0I(U;SjA) +(0): (34) By the packing lemma [14], we can write P(E2)n!1! 0ifR1+R0I(U;YjA)(); P(E3);P(E4)n!1! 0ifRc+R1+R0I(U;A;Y)(): Thus we arrive at the rate constraints: R1I(U;YjA)I(U;SjA)(0)(); (35) R1+RcI(U;A;Y)I(U;SjA)(0)(): (36) Input Cost Analysis: From the error analysis, we have P(E1) =P((Un(W1;Wc;J);Sn;An(Wc))=2Tn 0) =P((Un(W1;Wc;J);Sn;Xn;An(Wc))=2Tn 0)n!1! 0: 11 But if (xn;an)2Tn 0, then we have (xn;an)by the typical average lemma [14]. Hence we have E[ (Xn;An)]=P(E1)E[ (Xn;An)jE1]+P(Ec 1)E[ (Xn;An)jEc 1] P(E1)max+P(Ec 1);where max= max a2A;x2X (a;x) =)lim sup n!1E[ (Xn;An)];sinceP(Ec 1)n!1! 1: Distortion Analysis: The mentioned distortion can be obtained by making the estimate on a per-letter basis. Since (U)satisﬁes the distortion constraint, it follows from the random codebook construction that asn!1 , we have E[d(Sn; (Un))] =1 nnX i=1E[d(Si; (Ui))] n!1! E[d(S; (U))]D: (37) Also, since both the encoder as well as the decoder (assuming correct decoding) can generate ^Si= (Ui);i2 [1 :n], the common reconstruction constraint is met.