15 RANGAN The result also holds for the “genie” algorithm in Ap- pendix B with H$_{i}$$_{→}$$_{j}$ ( t ) and H$_{i}$$_{←}$$_{j}$ ( t ) replaced by H genie i → j ( t ) and H genie i ← j ( t ) . shown that if (42c) holds for t , then (42a) holds for t +1 . One can also show that if (42c) holds for t , then (42b) holds for t +1 using similar arguments except we replace the summations over ℓ ∈ N$_{in}$ ( j ) = i with ℓ ∈ N$_{in}$ ( j ) . Similar to the proof of Theorem 1(a), we prove Theorem 3 by induction. For the initial step in the induction, note that, for the regular (non-Genie) algorithm, H$_{i}$$_{→}$$_{j}$ ( t ) is empty and ̂ z$_{i}$$_{→}$$_{j}$ (1) is the prior on z$_{i}$$_{→}$$_{j}$ . For the genie algorithm, H genie i → j ( t ) contains the entire vector x and ̂ z$_{i}$$_{→}$$_{j}$ (1) = z$_{i}$$_{→}$$_{j}$ . Therefore, part (a) of Theorem 3 holds for t = 1 . In part A below, we will show that if (a) holds for some t , (b) holds for t + 1 . In part B, we will show the reverse implication that if (b) holds for some t so does (a). In part C, we apply Theorem 3 to prove Theorem 1(b) and (c). Parts (b) and (c) of Theorem 1 can be proven along the lines of Guo and Wang’s analysis in [13] and [14] using the concept of an asymptotically sufficient statistic along with a standard sandwiching argument. Specifically, using their analysis, we will show that the regular and “genie” versions of the relaxed BP algorithm provide sufficient statistics for certain conditional distribution of the vectors x and z . The regular BP algorithm provides a sufficient statistic relative to the sigma algebras H$_{i}$$_{←}$$_{j}$ ( t ) and H$_{i}$$_{→}$$_{j}$ ( t ) , and the “genie” relaxed BP algorithm in Appendix B provides a sufficient statistic relative to H genie i ← j ( t ) and H genie i → j ( t ) . Moreover, the MSE relative to the sigma algebras is described by the state evolution equations starting from the “high” initial conditions for the regular algorithm and “low” initial condition for the genie algorithm. Since the sigma algebra generated by the actual observation vector y lies somewhere between these sigma algebras, H and H $^{genie}$, the MSE of the optimal estimator is “sandwiched” between the two solutions to the state evolution equations. Suppose that part (a) of Theorem 3 holds for some t ≥ 1 . We will prove part (b) holds for t + 1 . The asymptotic limit (78) has already been proven. We only need to show that ($_{̂}$ q$_{i}$$_{←}$$_{j}$ ( t ) , s$_{j}$ ) is asymptotically sufficient to describe the conditional distribution of x$_{j}$ given H$_{i}$$_{←}$$_{j}$ ( t + 1) . To this end, suppose that G$_{i}$$_{←}$$_{j}$ ( t + 1) is a tree. By the construction of the computation subgraphs, G$_{ℓ}$$_{→}$$_{j}$ ( t ) must be a tree for every ℓ ∈ N$_{in}$ ( j ) , ℓ = j . Now define, for any r ≥ 1 , the “actual” derivatives of the likelihood Since the arguments in this section follow very closely with Guo and Wang’s analysis in [13], [14], we will just sketch the proof. Similar sandwiching arguments can be found in the early analysis of LDPC codes in [39]. We begin with the following definition. Definition 1: Suppose that ( x$_{n}$, q$_{n}$, H$_{n}$ ) is a sequence where, for every n , x$_{n}$ and q$_{n}$ are random variables and H$_{n}$ is a sigma algebra. We will say that q$_{n}$ is an asymptotically sufficient statistic for x$_{n}$ given H$_{n}$ with limiting distribution ( x$_{n}$, q$_{n}$ ) → ( x, q ) if: where p u ℓ → $_{j}$( t, u ) is defined in (11). Since G$_{ℓ}$$_{→}$$_{j}$ ( t ) is a tree, Lemma 5 shows that p z ℓ → $_{j}$( t, z$_{ℓ}$$_{→}$$_{j}$ ) in (11) is the conditional distribution z$_{ℓ}$$_{→}$$_{j}$ given H$_{ℓ}$$_{→}$$_{j}$ ( t ) . Bringing the derivatives in (79) inside the expectation in (11) we can rewrite (79) as where the expectation is over the conditional distribution of z$_{ℓ}$$_{→}$$_{j}$ given H$_{ℓ}$$_{→}$$_{j}$ ( t ) . Also, using (15) and (16), we can write almost surely. The definition is a natural generalization of the concept of a sufficient statistic. Specifically, it says that the conditional estimate E ( f ( x$_{n}$ ) | H$_{n}$ ) can be replaced by E ( f ( x ) | q = q$_{n}$ ) with asymptotically vanishing error. That is, it is sufficient to use just q$_{n}$ instead of the entire sigma algebra H$_{n}$ and use just the limiting distribution ( x, q ) as opposed to the termwise distributions ( x$_{n}$, q$_{n}$ ) . where the expectation is over z ∼ N ($_{̂}$ z, µ ) . Now, the induction hypothesis, Theorem 3(a), states that ̂ z$_{ℓ}$$_{→}$$_{j}$ ( t ) is asymptotically sufficient for z$_{ℓ}$$_{→}$$_{j}$ given H$_{ℓ}$$_{→}$$_{j}$ ( t ) with the asymptotic distribution Following along the lines of Guo and Wang [13], [14], we now prove the following. Theorem 3: For the relaxed BP algorithm: where µ $^{z}$( t ) = µ z $_{hi}$( t ) for the regular algorithm and µ $^{z}$( t ) = µ z $_{lo}$( t ) for the “genie algorithm”. Applying this property to (80) to (81), we obtain that almost surely. (b) If G$_{i}$$_{←}$$_{j}$ ( t ) is a tree, then ($_{̂}$ q$_{i}$$_{←}$$_{j}$ ( t ) , s$_{j}$ ) is an asymptot- ically sufficient statistic for x$_{j}$ given H$_{i}$$_{←}$$_{j}$ ( t ) with the asymptotic distribution (78). (a) If G$_{i}$$_{→}$$_{j}$ ( t ) is a tree, then ̂ z$_{i}$$_{→}$$_{j}$ ( t ) is an asymptotically sufficient statistic for z$_{i}$$_{→}$$_{j}$ given H$_{i}$$_{→}$$_{j}$ ( t ) with the asymptotic distribution (42c). (c) For any bounded continuous function f ( x ) , (b) ( x$_{n}$, q$_{n}$ ) → ( x, q ) in distribution; (a) q$_{n}$ is H$_{n}$ -measurable; lim n →∞ lim d $_{→∞}$D ℓ → j $_{r,act}$( t, y$_{ℓ}$ ) − D$_{r}$ ( y$_{ℓ}$,$_{̂}$ z$_{ℓ}$$_{→}$$_{j}$ ( t ) , µ $^{z}$( t )) = 0 , (82) lim d →∞ lim n $_{→∞}$( z$_{ℓ}$$_{→}$$_{j}$,$_{̂}$ z$_{ℓ}$$_{→}$$_{j}$ ( t )) = N (0 , P$_{z}$ ( µ $^{z}$( t )) , D$_{r}$ ( y,$_{̂}$ z, µ ) = − E$^{[}$ ∂ r ∂u r log p$_{Y}$$_{|}$$_{Z}$ ( y$_{i}$ | u + z ) ∣ u =0 | ̂ z, µ$^{]}$ , (81) lim n $_{→∞}$( E ( f ( x$_{n}$ ) | H$_{n}$ ) − E ( f ( x ) | q = q$_{n}$ )) = 0 D ℓ → j $_{r,act}$( t, y$_{ℓ}$ ) = − E$^{[}$ ∂ r ∂u r log p$_{Y}$$_{|}$$_{Z}$ ( y$_{i}$ | u + z$_{ℓ}$$_{→}$$_{j}$ ) ∣ u =0 | H$_{ℓ}$$_{→}$$_{j}$ ( t )$^{]}$ , (80) D ℓ → j $_{r,act}$( t, y$_{ℓ}$ ) = − ∂ r ∂u r log p u ℓ → $_{j}$( t, u ) ∣ u $_{=0}$, (79) A. Analysis of the Input Node Update APPENDIX F PROOF OF THEOREM 1(B) AND (C)