17 RANGAN 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 where, for any random variables X and W , F ( W | X = x ) is the Fisher information 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}$ . 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 ( µ ) . for some µ with µ = G ( µ ) . Moreover, the limiting value µ is the largest value satisfying µ = G ( µ ) and µ ∈ [0 , µ$_{max}$ ] . 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 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 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 , Now suppose that µ ( t + 1) ≤ µ ( t ) for some t . Then, using the monotonicity of G ( µ ) , 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 , 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 ( µ ) . 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 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 , Also, the definitions of z , ̂ z$_{1}$ and ̂ z$_{2}$ above show that, for i = 1 , 2 , when u = 0 , 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 ( z, ̂ z$_{i}$ ) ∼ N (0 , P$_{z}$ ( µ$_{i}$ )) , E [ E$_{in}$ ( q, µ )] ( a ) = var ( X | Q ) ( b ) ≤ var ( X ) ( c ) = µ x $_{init}$. µ $^{z}$( t + 1) = G ( µ $^{z}$( t )) . G ( µ ) = β E$_{in}$ $^{[}$E$_{out}$ ( µ ) $^{]}$, (87) µ ( t + 1) = G ( µ ( t )) ≥ µ$_{1}$. ̂ z$_{2}$ ∼ N (0 , µ z init − µ$_{2}$ ) z ∼ u + ̂ z$_{1}$ + N (0 , µ$_{1}$ ) ̂ z$_{1}$ ∼ ̂ z$_{2}$ + N (0 , µ$_{2}$ − µ$_{1}$ ) u → ($_{̂}$ z$_{1}$, y ) → ($_{̂}$ z$_{2}$, y ) F ($_{̂}$ Z$_{1}$, Y | U = 0) ≥ F ($_{̂}$ Z$_{2}$, Y | U = 0) . (90) 0 ≤ µ$_{1}$ ≤ µ$_{2}$ ≤ µ z $_{init}$. E$_{in}$ ( µ$_{i}$ ) = E [ s var ( X | Q$_{i}$, S = s )] . (89) µ ( t + 2) = G ( µ ( t + 1)) ≤ G ( µ ( t )) = µ ( t + 1) . µ (2) = G ( µ (1)) ≤ µ$_{max}$ = µ (1) var ( X | Q$_{1}$, S = s ) ≤ var ( X | Q$_{2}$, S = s ) . (88) q$_{2}$ = q$_{1}$ + w, w ∼ N (0 , ( µ$_{2}$ − µ$_{1}$ ) /s ) , q$_{1}$ = x + v$_{1}$, v$_{1}$ ∼ N (0 , µ$_{1}$/s ) , lim t $_{→∞}$µ ( t ) = µ, G ( µ ) ≤ β E ( s ) µ x init = µ z $_{init}$, E$_{in}$ ( µ ) = E [ s E$_{in}$ ( q, µ/s )] ≤ E ( s ) µ x $_{init}$. F ( W | X = x ) = − E$^{[}$ ∂ 2 ∂x 2 log p$_{W}$$_{|}$$_{X}$ ( w | x )$^{∣}$ ∣ ∣ X = x$^{]}$ (86) (a) Consider the sequence µ ( t + 1) = G ( µ ( t )) initialized with µ (1) = µ$_{max}$ . Then (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.