content_image/406686.jpg content_image/406687.jpg content_image/406704.jpg content_image/406693.jpg content_image/406694.jpg content_image/406698.jpg content_image/406699.jpg content_image/406688.jpg content_image/406689.jpg content_image/406685.jpg content_image/406690.jpg content_image/406691.jpg content_image/406692.jpg content_image/406695.jpg content_image/406702.jpg content_image/406703.jpg content_image/406700.jpg content_image/406701.jpg
Also, 

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

Substituting (55) and (56) into (54), we obtain that 

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

Then (51a) follows by substituting (53) and (57) into (52). Equation (51b) is proved by similar manipulations. 

## B. Analysis of the Output Node Update 

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. 

Under the induction hypothesis (42a), we first consider the convergence of the terms µ z i → $_{j}$( t ) . From the factorization (28) we have that 

Using (18) and (58), we have that 

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 

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 

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 

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

where the convergence is in distribution and the last step follows from the definition of µ $^{z}$( t ) in (37). 

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

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

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

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

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 

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

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 

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

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 

and 

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 ) . 

## C. Analysis of the Input Node Update 

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 

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 

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

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

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

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

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

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

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

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

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

