RELAXED BELIEF PROPAGATION 16 definition of an asymptotically sufficient statistic shows that We can now rewrite p x i ← $_{j}$( t + 1 , x$_{j}$ ) in (13) as lim d →∞ lim n $_{→∞}$E ( x$_{j}$ | H$_{i}$$_{←}$$_{j}$ ( t )) − ̂ x$_{i}$$_{←}$$_{j}$ ( t + 1) ( a ) = lim d →∞ lim n $_{→∞}$E ( x | q = ̂ q$_{i}$$_{←}$$_{j}$ ( t ) , s = s$_{j}$ ) − ̂ x$_{i}$$_{←}$$_{j}$ ( t + 1) ( b ) = lim d →∞ lim n $_{→∞}$F$_{in}$ ($_{̂}$ q$_{i}$$_{←}$$_{j}$ ( t ) , µ $^{q}$( t ) /s$_{j}$ ) − ̂ x$_{i}$$_{←}$$_{j}$ ( t + 1) ( c ) = 0 (84) lim d →∞ lim n $_{→∞}$E ( var ( x$_{j}$ | H$_{i}$$_{←}$$_{j}$ ( t )) | s$_{j}$ = s ) = lim d →∞ lim n $_{→∞}$E $^{(}$| x$_{j}$ − E ( x$_{j}$ | H$_{i}$$_{←}$$_{j}$ ( t )) | $^{2}$| s$_{j}$ = s ) ( a ) = lim d →∞ lim n $_{→∞}$E $^{(}$| x$_{j}$ − ̂ x$_{i}$$_{←}$$_{j}$ ( t ) | $^{2}$| s$_{j}$ = s ) ( b ) = E $^{(}$| x − F$_{in}$ ( q, µ $^{q}$( t ) /s ) | $^{2}$| s ) ( c ) = E ( E$_{in}$ ( q, µ $^{q}$( t ) /s ) | s ) ( d ) = E$_{in}$ ( µ $^{q}$( t ) , s ) ( e ) = µ $^{x}$( t + 1 , s ) , (85) lim d →∞ lim n $_{→∞}$p x i ← $_{j}$( t + 1 , x$_{j}$ ) = lim d →∞ lim n $_{→∞}$const × p$_{X}$ ( x$_{j}$ ) exp$^{[}$ 1 2 µ q i ← $_{j}$( t ) | x$_{j}$ − ̂ q$_{i}$$_{←}$$_{j}$ ( t ) | 2 ] . (83) var ( x$_{j}$ | y ) ≥ var ( x$_{j}$ | H genie i ← j ( t )) . var ( X | Y ) ≤ var ( X | Z ) . F ( Z | X = x ) ≤ F ( Y | X = x ) lim d →∞ lim n →∞ − log p x i ← $_{j}$( t + 1 , x$_{j}$ ) + log p$_{X}$ ( x$_{j}$ ) + const ( a ) = lim d →∞ lim n →∞ ∑ ℓ ∈ N$_{in}$ ( j ) = i log p u ℓ → $_{j}$( t, Φ$_{ℓj}$ x$_{j}$ ) ( b ) = lim d →∞ lim n →∞ ∑ ℓ ∈ N$_{in}$ ( j ) = i D ℓ → j $_{r,act}$( t, y$_{ℓ}$ )Φ$_{ℓj}$ x$_{j}$ + 1 2 D ℓ → j $_{r,act}$( t, y$_{ℓ}$ ) | Φ$_{ℓj}$ x$_{j}$ | 2 + O ( | Φ$_{ℓj}$ x$_{j}$ | $^{3}$) ( c ) = lim d,n →∞ ∑ ℓ ∈ N$_{in}$ ( j ) = i D$_{r}$ ( y$_{ℓ}$,$_{̂}$ z$_{ℓ}$$_{→}$$_{j}$ ( t ) , µ $^{z}$( t ))Φ$_{ℓj}$ x$_{j}$ + 1 2 D$_{r}$ ( y$_{ℓ}$,$_{̂}$ z$_{ℓ}$$_{→}$$_{j}$ ( t ) , µ $^{z}$( t )) | Φ$_{ℓj}$ x$_{j}$ | 2 ( d ) = lim d,n →∞ 1 2 µ q i ← $_{j}$( t ) | x$_{j}$ − ̂ q$_{i}$$_{←}$$_{j}$ ( t ) | 2 ( e ) = lim d,n →∞ s$_{j}$ 2 µ $^{q}$( t ) | x$_{j}$ − ̂ q$_{i}$$_{←}$$_{j}$ ( t ) | 2 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 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, 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 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. 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) . 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. 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, APPENDIX G PROOF OF THEOREM 2 B. Analysis of the Output Update C. MSE Relationships (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 , Using Theorem 3, we can now prove parts (b) and (c) of Theorem 1. First observe that Theorem 3 along with the