content_image/431574.jpg content_image/431570.jpg content_image/431568.jpg content_image/431569.jpg content_image/431571.jpg content_image/431572.jpg content_image/431573.jpg
We can now rewrite p x i ← $_{j}$( t + 1 , x$_{j}$ ) in (13) as 

<img src='content_image/431574.jpg'>

where the constant is independent of x$_{j}$ ; (a) follows from (13); (b) is the Taylor’s series expansion of log p u ℓ → $_{j}$( t, Φ$_{ℓj}$ x$_{j}$ ) ; (c) follows from (82) and (30d); (d) follows from (19) and (20) and (e) follows from (72). Here, with some abuse of notation, we have written lim A = lim B in place of lim( A − B ) = 0 . Using this same convention, the above equations show that 

<img src='content_image/431570.jpg'>

From Lemma 5, the left hand side of (83) precisely the conditional distribution of x$_{j}$ given H$_{i}$$_{←}$$_{j}$ ( t +1) (or H genie i ← j ( t ) ). Therefore, (83) shows that this conditional distribution is asymptotically only a function of ̂ q$_{i}$$_{←}$$_{j}$ ( t ) and s$_{j}$ , and there- fore ($_{̂}$ q$_{i}$$_{←}$$_{j}$ ( t ) , s$_{j}$ ) is asymptotically sufficient for x$_{j}$ given H$_{i}$$_{←}$$_{j}$ ( t + 1) . 

## B. Analysis of the Output Update 

Continuing the induction argument, we next show that if the part (b) of Theorem 3 holds for some t , then so does part (a). We have already proven the asymptotic distribution (42c). So, we just need to show that the conditional distribution of z$_{i}$$_{→}$$_{j}$ given H$_{i}$$_{→}$$_{j}$ ( t ) asymptotically depends only on ̂ z$_{i}$$_{→}$$_{j}$ ( t ) . 

Now, from Lemma 5, the conditional distribution of z$_{i}$$_{→}$$_{j}$ given H$_{i}$$_{→}$$_{j}$ ( t ) is given by p z i → $_{j}$( t, z$_{i}$$_{→}$$_{j}$ ) from the BP algo- rithm. But this distribution is described by the summation (9). The analysis in Appendix E-B shows that this summation has an asymptotic Gaussian distribution N ($_{̂}$ z$_{i}$$_{→}$$_{j}$ ( t ) , µ $^{z}$( t )) . So, ̂ z$_{i}$$_{→}$$_{j}$ ( t ) is asymptotically sufficient to describe the distribution. 

This completes the induction argument and proves Theo- rem 3. 

## C. MSE Relationships 

Using Theorem 3, we can now prove parts (b) and (c) of Theorem 1. First observe that Theorem 3 along with the 

definition of an asymptotically sufficient statistic shows that 

<img src='content_image/431568.jpg'>

where in (a) the expectation is with respect to ( x, q, s ) dis- tributed as (78); (b) follows from the definition of F$_{in}$ ( · ) in Section IV-A; and (c) follows from (21) and (78). The limit (84) shows that the conditional variance is given by 

<img src='content_image/431569.jpg'>

where (a) is due to the limit (84); (b) is due to the limit (78); (c) is the definition of E$_{in}$ ( q, µ ) ; (d) follows from (32); and (e) is from (37b). The limit (85) holds for the regular algorithm with µ $^{x}$( t +1 , s ) = µ x $_{hi}$( t +1 , s ) and for genie algorithm with µ $^{x}$( t + 1 , s ) = µ x $_{lo}$( t + 1 , s ) . With the regular (non-genie) algorithm, the limit (85) shows (43a). Also, for the genie algorithm, the sigma algebra H genie i ← j ( t ) is contains the sigma generated by just y . Therefore, 

Combining this inequality with (85) shows (44a). 

A similar argument can be used to show (43b) and (44b). We have thus shown part (b) and (c) of Theorem 1. 

The proof is based on a degradation argument, which is used commonly for convergence proofs of BP algorithms [40]. Suppose that X → Y → Z is a Markov chain. Then, we say that Z is degraded with respect to Y , since estimates of X from Z are strictly worse than those from Y . The following lemma states a standard property of degraded random variables. 

Lemma 8: Suppose that X → Y → Z is a Markov chain. Then, 

(a) The conditional variance of X satisfies 

(b) Suppose the likelihood function of X given Y and the likelihood of X given Z both have continuous third derivatives. Then, for any x , 

<img src='content_image/431571.jpg'>

## PROOF OF THEOREM 2 

<img src='content_image/431572.jpg'>

<img src='content_image/431573.jpg'>

## APPENDIX G 

