13 RANGAN We next consider the convergence of the variables ̂ z$_{i}$$_{→}$$_{j}$ ( t ) . If we define z$_{i}$$_{→}$$_{j}$ as in (9), then (18) and (58) show that By Lemma 6(b) the terms in the summation (61) are indepen- dent. Also assuming (42a) holds, the terms in the summation converge as Substituting (55) and (56) into (54), we obtain that Then (51a) follows by substituting (53) and (57) into (52). Equation (51b) is proved by similar manipulations. Also, where the convergence is in distribution and the random variables x , s and q are the terms in θ $^{x}$( t ) in (39). The variances of the terms converge as Using (30a), (30b) and (60), we can apply the Modified Central Limit Theorem (Lemma 3) to (61) to obtain where the convergence is in distribution. Similarly one can show that where µ z init is defined in (33). Equations (62) and (63) imply that where z and ̂ z are the Gaussian random variables in (35) with µ = µ$_{z}$ ( t ) . Combining (60) and (64) proves (42c). This argument shows that if (42a) is true for some t , then so is (42c). A similar argument shows that (42a) also implies (42d), except we replace the summations over the sets r ∈ N$_{out}$ ( i ) = j with r ∈ N$_{out}$ ( i ) . By Lemma 6(b) and the assumption that G$_{i}$$_{→}$$_{j}$ ( t ) is a tree, the terms in the summation in (59) are independent. Also, the induction hypothesis (42a) shows that their asymptotic distribution is given by For the next step in the induction proof, we want to prove that if (42c) holds for some t , then (42a) holds for t + 1 . Throughout this section, fix the input index j and variables s$_{j}$ and x$_{j}$ . For each output index ℓ ∈ N$_{in}$ ( j ) and u ∈$_{R}$ , define the Markov chain C. Analysis of the Input Node Update where the random variables are distributed as Suppose the Markov chains are independent over different values of ℓ . We use the superscript “G” here to indicate that where the convergence is in distribution and the last step follows from the definition of µ $^{z}$( t ) in (37). where E$_{in}$ ( µ $^{q}$( t − 1)) is defined in (32). Using (30c), we can apply the Modified Law of Large Numbers (Lemma 2), to the sum in (59) to obtain where the convergence is in distribution and the random variables s and q are the terms in θ $^{x}$( t ) in (39). For the regular relaxed BP algorithm µ $^{q}$( t − 1) = µ q $_{hi}$( t − 1) and, for the genie algorithm, µ $^{q}$( t − 1) = µ q $_{lo}$( t − 1) . In either case, the expectation of this limiting random variable is Under the induction hypothesis (42a), we first consider the convergence of the terms µ z i → $_{j}$( t ) . From the factorization (28) we have that Let t ≥ 1 and suppose that (42a) holds for some t . We will show that this induction hypothesis implies (42c) and (42d). We will just prove this implication for t > 1 . The proof for t = 1 is similar. B. Analysis of the Output Node Update z$_{i}$$_{→}$$_{j}$ − ̂ z$_{i}$$_{→}$$_{j}$ ( t ) = ∑ r ∈ N$_{out}$ ( i ) = j Φ$_{ir}$( x$_{r}$ − ̂ x$_{i}$$_{←}$$_{r}$ ) = 1 √ d ∑ r ∈ N$_{out}$ ( i ) = j a$_{ir}$ √ s$_{r}$ ( x$_{r}$ − ̂ x$_{i}$$_{←}$$_{r}$ ) . (61) ∫ 1 p$_{Y}$$_{|}$$_{U}$ ( y | 0) ( ∂ ∂u p$_{Y}$$_{|}$$_{U}$ ( y | u ) ∣ u =0 ) 2 dy = ∫ ∂ ∂u p$_{Y}$$_{|}$$_{U}$ ( y | u ) ∣ u =0 ∂ ∂u log p$_{Y}$$_{|}$$_{U}$ ( y | u ) ∣ u =0 dy = − ∫ ∂ ∂u p$_{Y}$$_{|}$$_{U}$ ( y | u ) ∣ u =0 D$_{1}$ ( y ) dy. (56) E [ D$_{2}$ ( y ) | u = 0] = − ∫ ∂ ∂u p$_{Y}$$_{|}$$_{U}$ ( y | u ) ∣ u =0 D$_{1}$ ( y ) dy. (57) lim d →∞ lim n →∞ √ s$_{r}$ ( x$_{r}$ − ̂ x$_{i}$$_{←}$$_{r}$ ) = √ s ( x − F$_{in}$ ( q, µ $^{q}$( t − 1) /s )) , lim d →∞ lim n $_{→∞}$E $^{[}$s$_{r}$ | x$_{r}$ − ̂ x$_{i}$$_{←}$$_{r}$ | 2 ] = E $^{[}$s | x − F$_{in}$ ( q, µ $^{q}$( t − 1) /s ) | 2 ] = E$_{in}$ ( µ $^{q}$( t − 1)) . lim d →∞ lim n $_{→∞}$z$_{i}$$_{→}$$_{j}$ − ̂ z$_{i}$$_{→}$$_{j}$ ( t ) = N (0 , µ $^{z}$( t )) , (62) lim d →∞ lim n $_{→∞}$z$_{i}$$_{→}$$_{j}$ = N (0 , µ z $_{init}$) (63a) lim d →∞ lim n $_{→∞}$( z$_{i}$$_{→}$$_{j}$ − ̂ z$_{i}$$_{→}$$_{j}$ ( t ))$_{̂}$ z$_{i}$$_{→}$$_{j}$ ( t ) = 0 , (63b) Φ$_{ij}$ = 1 √ d a$_{ij}$ √ s$_{j}$, ∀ j ∈ N$_{out}$ ( i ) . (58) µ z i → $_{j}$( t ) = ∑ r ∈ N$_{out}$ ( i ) = j | Φ$_{ir}$ | $^{2}$µ x i ← r = 1 d ∑ r ∈ N$_{out}$ ( i ) = j | a$_{ir}$ | $^{2}$s$_{r}$ µ x i ← $_{r}$( t ) . (59) lim d →∞ lim n $_{→∞}$( z$_{i}$$_{→}$$_{j}$, ̂ z$_{i}$$_{→}$$_{j}$ ( t )) = ( z, ̂ z ) , (64) and Using (18) and (58), we have that lim d →∞ lim n $_{→∞}$s$_{r}$ µ x i ← $_{r}$( t ) = s E$_{in}$ ( q, µ $^{q}$( t − 1) /s ) , E [ s E$_{in}$ ( q, µ $^{q}$( t − 1) /s )] = E$_{in}$ ( µ $^{q}$( t − 1)) , ̂ z G ℓ → z G ℓ ( u ) → y G ℓ ( u ) , ̂ z G ℓ ∼ N (0 , µ z init − µ $^{z}$( t )) z G ℓ ( u ) ∼ N ($_{̂}$ z G ℓ + u, µ $^{z}$( t )) y G ℓ ( u ) ∼ p$_{Y}$$_{|}$$_{Z}$ ( y | z G ℓ ( u )) . lim d →∞ lim n $_{→∞}$µ z i ← $_{j}$( t ) = β E$_{in}$ ( µ $^{q}$( t − 1)) = µ $^{z}$( t ) , (60)