content_image/432901.jpg content_image/432893.jpg content_image/432882.jpg content_image/432898.jpg content_image/432894.jpg content_image/432885.jpg content_image/432884.jpg content_image/432883.jpg content_image/432900.jpg content_image/432897.jpg content_image/432896.jpg content_image/432895.jpg content_image/432899.jpg content_image/432892.jpg content_image/432891.jpg content_image/432886.jpg content_image/432888.jpg content_image/432887.jpg content_image/432889.jpg content_image/432890.jpg content_image/432881.jpg
where, for any random variables X and W , F ( W | X = x ) is the Fisher information 

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

Proof: See, for example, [42]. 

We will combine this lemma with the following simple iteration result to prove the theorem. 

Lemma 9: Suppose G ( µ ) is a monotonically increasing, continuous function with 0 ≤ G ( µ ) ≤ µ$_{max}$ for all µ and some µ$_{max}$ . 

(a) Consider the sequence µ ( t + 1) = G ( µ ( t )) initialized with µ (1) = µ$_{max}$ . Then 

for some µ with µ = G ( µ ) . Moreover, the limiting value µ is the largest value satisfying µ = G ( µ ) and µ ∈ [0 , µ$_{max}$ ] . 

(b) Similarly, if the above sequence is initialized with µ (1) = 0 , then µ ( t ) → µ where µ is the smallest value satisfying µ ∈ [0 , µ$_{max}$ ] and the fixed point equation µ = G ( µ ) . 

Proof: We will just prove part (a) as part (b) is similar. 

We first prove by, induction, that µ ( t +1) ≤ µ ( t ) for all t . For t = 1 , since µ (1) is initialized to µ$_{max}$ and G ( µ ) ≤ µ$_{max}$ for all µ , we have that 

Now suppose that µ ( t + 1) ≤ µ ( t ) for some t . Then, using the monotonicity of G ( µ ) , 

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

So, by induction, µ ( t ) is a monotonically decreasing sequence. Since it is bounded below by zero, it must converge to some µ . By the continuity of G ( µ ) , the limit point must satisfy the fixed point equation µ = G ( µ ) . 

It remains to show that the limiting value µ is the largest fixed point of G in the interval [0 , µ$_{max}$ ] . To this end, let µ$_{1}$ be any fixed point µ$_{1}$ = G ( µ$_{1}$ ) with 0 ≤ µ$_{1}$ ≤ µ$_{max}$ . Then, µ (1) = µ$_{max}$ ≥ µ$_{1}$ . Also, if µ ( t ) ≥ µ$_{1}$ , by the monotonicity of G , 

So, by the induction the entire sequence µ ( t ) ≥ µ$_{1}$ . Taking the limits as t → ∞ , we have that µ ≥ µ$_{1}$ . Hence µ ≥ µ$_{1}$ for any other fixed point of G . 

We can now prove Theorem 2. Define the function 

so that we can rewrite the density evolution equation (38) as 

We will now apply Lemma 9 to show that µ$_{z}$ ( t ) → µ to a fixed point µ = G ( µ ) . We first upper bound G ( µ ) . For all µ > 0 , 

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

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

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

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

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

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

where the expectation is over the random variable q = x + v , v ∼ N (0 , µ ) ; (a) follows from the definition of E$_{in}$ ( q, µ ) ; (b) is the fact that conditioning cannot increase the variance; and (c) is from the definition of µ x init in (17). Therefore, the definition of E$_{in}$ ( µ ) in (32) implies that 

As a result, G ( µ ) defined in (87) satisfies 

where µ z init is defined in (33). So, we have that G ( µ ) ≤ µ z init for all µ . Also, the “high” sequence µ z $_{hi}$( t ) is initialized with µ z $_{hi}$(1) = µ z init and the “low” sequence with µ z $_{lo}$(1) = 0 So, we will apply Lemma 9 with µ$_{max}$ = µ z $_{init}$. 

By the assumption of the theorem, E$_{in}$ ( µ ) and E$_{out}$ ( µ ) are continuous. Therefore, so is G ( µ ) . 

Hence, to apply Lemma 9, it remains to show that G ( µ ) is monotonically increasing. From (87), we need to show that E$_{in}$ ( µ ) and E$_{out}$ ( µ ) are monotonically increasing. 

We first consider E$_{in}$ ( µ ) . Let µ$_{2}$ ≥ µ$_{1}$ and define the random variables 

where x ∼ p$_{X}$ ( x ) , s ∼ p$_{S}$ ( s ) , and v$_{1}$ and v$_{2}$ are independent. We have that x → q$_{1}$ → q$_{2}$ is a Markov chain, so Lemma 8(a) shows that, for all s , 

Also, q$_{2}$ is identically distributed to q$_{2}$ = x + v$_{2}$ , v$_{2}$ ∼ N (0 , µ$_{2}$/s ) for some v$_{2}$ independent of x . The definition of E$_{in}$ ( µ ) shows that for i = 1 , 2 , 

Combining (88) and (89) shows that E$_{in}$ ( µ ) is monotonically increasing in µ . 

The proof that E$_{out}$ ( µ ) is monotonically increasing is sim- ilar. Let µ$_{1}$ and µ$_{2}$ be variances such that 

For u ∈$_{R}$ , define the random variables 

where all the Gaussian random variables are independent. Also, conditional on z , let y have the distribution y ∼ p$_{Y}$$_{|}$$_{Z}$ ( y | z ) . It can be verified that 

is a Markov chain. It follows from Lemma 8(b) that 

Also, the definitions of z , ̂ z$_{1}$ and ̂ z$_{2}$ above show that, for i = 1 , 2 , when u = 0 , 

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

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

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

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

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

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

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

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

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

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

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

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

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

