RELAXED BELIEF PROPAGATION 14 is identical to ( y G ℓ (0) , z G ℓ (0)) ; and (d) follows from the SE equation (37a). We next turn to the distribution of ̂ q$_{i}$$_{←}$$_{j}$ ( t ) . Using (19), the update (20a) can be simplified to the random variables are Gaussian approximations to actual random variables in the problems. To be specific, first observe that Combining (66) with the definition of z$_{i}$$_{→}$$_{j}$ in (9) and the fact that z = Φ x , we have So, using (69) and (72), where The induction hypothesis (42c) and Lemma 6(a) then show that where here and below we use the shorthand lim$_{d,n}$ for lim$_{d}$ lim$_{n}$ . Now define so we can rewrite (74) as where the convergence is in distribution. With these definitions, we first consider the convergence of µ q i ← $_{j}$( t ) . Using (19b), (20b) and (66), we have that By Lemma 6(a), given x$_{j}$ and s$_{j}$ , all the terms in (70) are independent. Also, using (69), we have the limit where the last step follows from (74) and (58). Now, applying Lemma 7 to e$_{ℓ}$ in (75), From the definition of u$_{ℓ}$ in (68), the O ( | u$_{ℓ}$ | $^{2}$) terms are O (1 /d ) and thus can be ignored. Applying the Modified Central Limit Theorem (Lemma 3) to the sum in (76) along with (30c) we obtain where the limit in (a) is in distribution and follows from (70) and (71); (b) follows from (30c) and the Modified Law of Large Numbers; (c) follows from the definition of E$_{out}$ ( · ) in (34) and the fact that the expectation over ( y, z ) in (34) where the convergence is in distribution, x ∼ p$_{X}$ ( x ) and s ∼ p$_{S}$ ( s ) . Applying (21) to (78) shows (42a). Therefore, we have Also since x$_{j}$ ∼ p$_{X}$ ( x$_{j}$ ) and s$_{j}$ ∼ p$_{S}$ ( s$_{j}$ ) , (72) and (77) together show that for any iteration t , lim d →∞ lim n $_{→∞}$( x$_{j}$, s$_{j}$, ̂ q$_{i}$$_{←}$$_{j}$ ( t ) , µ q i ← $_{j}$( t )) = ( x, s, N ( x, 1 s µ$_{q}$ ( t )$^{)}$ , 1 s µ$_{q}$ ( t )$^{)}$ , (78) lim d →∞ lim n →∞ 1 µ q i ← $_{j}$( t ) ( a ) = lim d →∞ lim n →∞ 1 d ∑ ℓ ∈ N$_{in}$ ( j ) = i | a$_{ℓj}$ | $^{2}$s$_{j}$ × D$_{2}$ ( y G ℓ (0) ,$_{̂}$ z G ℓ (0) , µ $^{z}$( t )) ( b ) = s$_{j}$ E $^{[}$D$_{2}$ ( y G ℓ (0) ,$_{̂}$ z G ℓ (0) , µ $^{z}$( t )) ] ( c ) = s$_{j}$ E$_{out}$ ( µ $^{z}$( t )) ( d ) = s$_{j}$ µ $^{q}$( t ) , (72) lim d →∞ lim n →∞ ̂ q$_{i}$$_{←}$$_{j}$ ( t ) = x$_{j}$ + ( µ $^{q}$( t )) 2 s$_{j}$ N ( 0 , 1 µ $^{q}$( t )$^{)}$ = N ( x$_{j}$, µ $^{q}$( t ) s$_{j}$ ) . (77) var ( e$_{ℓ}$ | u$_{ℓ}$ ) = E $^{[}$D$_{2}$ ( y G ℓ (0) ,$_{̂}$ z G ℓ (0) , µ $^{z}$( t )) $^{]}$+ O ( | u$_{ℓ}$ | $^{2}$) = 1 µ $^{q}$( t ) + O ( | u$_{ℓ}$ | $^{2}$) . lim d →∞ lim n $_{→∞}$D$_{2}$ ( y$_{ℓ}$,$_{̂}$ z$_{ℓ}$$_{→}$$_{j}$ ( t ) , µ z ℓ → $_{j}$( t )) ( a ) = D$_{2}$ ( y G ℓ ( u$_{ℓ}$ ) ,$_{̂}$ z G ℓ ( u$_{ℓ}$ ) µ $^{z}$( t )) ( b ) = D$_{2}$ ( y G ℓ (0) ,$_{̂}$ z G ℓ (0) , µ $^{z}$( t )) + O ( | u$_{ℓ}$ | $^{3}$) ( c ) = D$_{2}$ ( y G ℓ (0) ,$_{̂}$ z G ℓ (0) , µ $^{z}$( t )) (71) where the convergence in (a) is in distribution; (b) follows from the assumption that D$_{3}$ ( · ) is uniformly bounded and (c) follows from the fact that (68) shows that | u$_{ℓ}$ | 3 = O ( d − 3 / $^{2}$) → 0 . We can apply the Modified Law of Large Numbers (Lemma 2) to the sum (70) to obtain the limit 1 µ q i ← $_{j}$( t ) = ∑ ℓ ∈ N$_{in}$ ( j ) = i | Φ$_{ℓj}$ | 2 µ u ℓ → $_{j}$( t ) = 1 d ∑ ℓ ∈ N$_{in}$ ( j ) = i | a$_{ℓj}$ | $^{2}$s$_{j}$ D$_{2}$ ( y$_{ℓ}$,$_{̂}$ z$_{ℓ}$$_{→}$$_{j}$ ( t ) , µ z ℓ → $_{j}$( t )) . (70) lim d →∞ lim n →∞ ̂ q$_{i}$$_{←}$$_{j}$ ( t ) = − lim d,n →∞ ∑ ℓ = i 1 s$_{j}$ Φ ∗ $_{ℓj}$e$_{ℓ}$ − lim d,n →∞ ∑ ℓ = i µ $^{q}$( t ) | Φ$_{ℓj}$ | $^{2}$x$_{j}$ s$_{j}$ E $^{[}$D$_{2}$ ( y G ℓ (0) ,$_{̂}$ z G ℓ (0) , µ $^{z}$( t )) ] = − lim d,n →∞ µ $^{q}$( t ) $^{√}$ds$_{j}$ ∑ ℓ = i a ∗ $_{ℓj}$e$_{ℓ}$ + x$_{j}$, (76) e$_{ℓ}$ = D$_{1}$ ( y G ℓ ( u$_{ℓ}$ ) ,$_{̂}$ z G ℓ ( u$_{ℓ}$ ) , µ $^{z}$( t )) + Φ$_{ℓj}$ x$_{j}$ E $^{[}$D$_{2}$ ( y G ℓ (0) ,$_{̂}$ z G ℓ (0) , µ $^{z}$( t )) $^{]}$, (75) lim d →∞ lim n $_{→∞}$($_{̂}$ z$_{ℓ}$$_{→}$$_{j}$ ( t ) , z$_{ℓ}$, y$_{ℓ}$, µ z ℓ → $_{j}$( t )) = ($_{̂}$ z G ℓ , z G ℓ ( u$_{ℓ}$ ) , y G ℓ ( u$_{ℓ}$ ) , µ $^{z}$( t )) , (69) u$_{ℓ}$ = Φ$_{ℓj}$ x$_{j}$ = 1 √ d a$_{ℓj}$ √ s$_{j}$x$_{j}$. (68) z$_{ℓ}$ = ∑ r ∈ N$_{out}$ ( ℓ ) Φ$_{ℓj}$ x$_{j}$ = u$_{ℓ}$ + z$_{ℓ}$$_{→}$$_{j}$, (67) Φ$_{ℓj}$ = 1 √ d a$_{ℓj}$ √ s$_{j}$, ∀ ℓ ∈ N$_{out}$ ( j ) . (66) ̂ q$_{i}$$_{←}$$_{j}$ ( t ) = µ q i ← $_{j}$( t ) ∑ ℓ = i Φ ∗ ℓj ̂ u$_{ℓ}$$_{→}$$_{j}$ ( t ) µ u ℓ → $_{j}$( t ) = − µ q i ← $_{j}$( t ) ∑ ℓ = i Φ ∗ $_{ℓj}$D$_{1}$ ( y$_{ℓ}$,$_{̂}$ z$_{ℓ}$$_{→}$$_{j}$ ( t ) , µ z ℓ → $_{j}$( t )) . (73) lim d →∞ lim n →∞ ̂ q$_{i}$$_{←}$$_{j}$ ( t ) = − µ $^{q}$( t ) s$_{j}$ lim d,n →∞ ∑ ℓ = i Φ ∗ $_{ℓj}$D$_{1}$ ( y G ℓ ( u$_{ℓ}$ ) ,$_{̂}$ z G ℓ ( u$_{ℓ}$ ) , µ $^{z}$( t )) , (74) E ( e$_{ℓ}$ | u$_{ℓ}$ ) = O ( | u$_{ℓ}$ | $^{2}$)