Exercises

$\mu_{f \to x_2}(x_2) = \sum_{x_1 \in \{\pm 1\}} e^{\theta x_1 x_2} \mu(x_1)$ $= e^{\theta x_2} \mu(+1) + e^{-\theta x_2} \mu(-1)$.

$\mu_{f \to x_2}(+1) = e^\theta \mu(+1) + e^{-\theta} \mu(-1)$, $\mu_{f \to x_2}(-1) = e^{-\theta} \mu(+1) + e^\theta \mu(-1)$.

$\log\frac{\mu_{f\to x_2}(+1)}{\mu_{f\to x_2}(-1)} = \log\frac{e^\theta + e^{-\theta}/r}{e^{-\theta} + e^\theta/r}$ where $r = \mu(+1)/\mu(-1) = e^L$. Simplifying, $L_{f \to x_2} = 2\operatorname{atanh}(\tanh\theta \cdot \tanh(L/2))$.

$\tanh(L_2/2) = \tanh(-1.5) \approx -0.905$. $\tanh(L_3/2) = \tanh(0.75) \approx 0.635$. Product $\approx -0.575$. $L_{\text{out},1} = 2\operatorname{atanh}(-0.575) \approx -1.31$.

Signs: $(-)(+) = -$. Magnitudes: $\min(3, 1.5) = 1.5$. $L_{\text{out},1}^{\text{min-sum}} = -1.5$.

Min-sum magnitude (1.5) is larger than exact (1.31) — min-sum overestimates. A scale factor $\alpha = 1.31/1.5 \approx 0.87$ would match; normalized min-sum uses $\alpha \in [0.75, 0.9]$.

$\epsilon(1 - (1-x)^5)^2 = x$ and $10\epsilon(1-(1-x)^5)(1-x)^4 = 1$.

From first: $\epsilon = x/(1-(1-x)^5)^2$. Substitute in the second: $10 (1-x)^4 x / (1-(1-x)^5) = 1$.

Solve $10(1-x)^4 x = 1 - (1-x)^5$ numerically. Root: $x \approx 0.2606$. Then $\epsilon^* \approx 0.2606/(1 - (0.7394)^5)^2 \approx 0.4294$.

$\lambda(x) = x, \rho(x) = x^3$. Recursion: $x_{\ell+1} = \epsilon \cdot (1 - (1 - x_\ell)^3)$.

Solve $\epsilon(1-(1-x)^3) = x$ and $3\epsilon(1-x)^2 = 1$. From second: $\epsilon = 1/(3(1-x)^2)$. Substitute: $(1 - (1-x)^3)/(3(1-x)^2) = x$, i.e., $1-(1-x)^3 = 3x(1-x)^2$. Expand: $1 - (1 - 3x + 3x^2 - x^3) = 3x - 6x^2 + 3x^3$. LHS: $3x - 3x^2 + x^3$. Equation: $3x - 3x^2 + x^3 = 3x - 6x^2 + 3x^3$, i.e., $3x^2 - 2x^3 = 0$, i.e., $x(3 - 2x) = 0$. Nontrivial root $x = 3/2$? Fails $[0,1]$. So the equation does not have a tangent fixed point in $(0, 1)$, meaning no inflection and $\epsilon^* =$ whenever the map first fails to drive $x \to 0$.

$T(x) = \epsilon(1-(1-x)^3)$ is convex increasing. Zero fixed point is stable iff $T'(0) = 3\epsilon < 1$, i.e., $\epsilon < 1/3$. So $\epsilon^*_{(2,4)} = 1/3 \approx 0.333$.

Shannon: $\epsilon \leq 1 - R = 0.5$. Gap $0.5 - 0.333 = 0.167$. The (2,4) code is much further from Shannon than the (3,6) code. Variable degree 2 is too small — one of the reasons (3,6) is canonical.

From $s_0 = 0$: $V_1(0) = \log 0.3 = -1.20, V_1(1) = \log 0.7 = -0.36$.

$V_2(0) = \max(V_1(0) + \log 0.3, V_1(1) + \log 0.6) = \max(-2.40, -0.87) = -0.87$, bp = 1. $V_2(1) = \max(V_1(0) + \log 0.7, V_1(1) + \log 0.2) = \max(-1.56, -1.97) = -1.56$, bp = 0.

$V_3(0) = \max(V_2(0) + \log 0.3, V_2(1) + \log 0.6) = \max(-2.07, -2.07) = -2.07$, tie (bp = 0 or 1). $V_3(1) = \max(V_2(0) + \log 0.7, V_2(1) + \log 0.2) = \max(-1.23, -3.17) = -1.23$, bp = 0.

Best end state: $s_3 = 1$ (metric $-1.23$ vs $-2.07$). Traceback: bp at 3 says $s_2 = 0$; bp at 2 says $s_1 = 1$; $s_0 = 0$ given. Path: $(0, 1, 0, 1)$. Most likely sequence.

Each BP message on the BEC is either fully informative or erased. In density evolution, this is captured by the probability of erasure $x_\ell$ for a randomly chosen variable-to-check edge.

Variable-to-check erased iff channel erased AND all other $d_v-1$ incoming check messages erased: $x_{\ell+1} = \epsilon \cdot (\text{all other checks erased})$. Check-to-variable erased iff any of $d_c - 1$ other variable-to-check inputs is erased.

Plug in: $x_{\ell+1} = \epsilon (1 - (1-x_\ell)^{d_c-1})^{d_v-1}$ for regular $(d_v, d_c)$, equivalent to $\epsilon \lambda(1 - \rho(1 - x_\ell))$ for irregular.

$\det(\mathbf{J}) = 3(9-1) - (-1)(-3 - 0) + 0 = 24 - 3 = 21$. Cofactors give $\mathbf{J}^{-1} = \frac{1}{21}\begin{pmatrix} 8 & 3 & 1 \\ 3 & 9 & 3 \\ 1 & 3 & 8 \end{pmatrix}$. $\boldsymbol{\mu} = (8 + 0 + 1, 3 + 0 + 3, 1 + 0 + 8)^T/21 = (9, 6, 9)/21 = (3/7, 2/7, 3/7)$.

Graph: $1-2-3$ with edges weighted by $\mathbf{J}$. Forward: $J_{1\to 2} = -(-1)^2 / (J_{11}) = -1/3$, $h_{1\to 2} = -(-1) \cdot h_1 / 3 = 1/3$. Then at node 2: $J_{2\to 3} = -(-1)^2/(J_{22} + J_{1\to 2}) = -1/(3 - 1/3) = -3/8$, $h_{2\to 3} = -(-1)(h_2 + h_{1\to 2})/(8/3) = (1/3)(3/8) = 1/8$. Backward analogously.

$J_3^\star = J_{33} + J_{2\to 3} = 3 - 3/8 = 21/8$. $h_3^\star = h_3 + h_{2\to 3} = 1 + 1/8 = 9/8$. $\mu_3 = (9/8) / (21/8) = 9/21 = 3/7$. ✓ Similarly $\mu_1 = 3/7, \mu_2 = 2/7$.

BP makes only local decisions — it cannot exploit long-range correlations that the optimal decoder can use. This creates a nonzero gap.

For $(d_v, d_c)$-regular codes with $d_v \geq 3$, the MAP threshold $\epsilon_{\text{MAP}}^*$ equals $1-R = 1 - d_v/d_c$ asymptotically, but the BP threshold $\epsilon_{\text{BP}}^*$ is strictly smaller. The gap shrinks as $d_c \to \infty$ (and $d_v$ grows accordingly).

By carefully mixing degrees, irregular codes can push $\epsilon_{\text{BP}}^*$ to within $< 0.01$ of $1 - R$ — essentially matching Shannon.

Fixed-point messages satisfy $(h_{i \to j}, J_{i \to j})$ expressions in terms of $(h_{k \to i})$. Write $\mu_j^\star = h_j^\star / J_j^\star$ where $J_j^\star = J_{jj} + \sum_k J_{k \to j}$, $h_j^\star = h_j + \sum_k h_{k \to j}$.

Substitute the message fixed-point equations into $\sum_k J_{jk} \mu_k^\star$ and simplify. After algebra (Schur complement identities), this equals $h_j$. Hence $(\mathbf{J}\boldsymbol{\mu}^\star)_j = h_j$ for every $j$.

Alternative proof: expand $\mu_j^\star = (\mathbf{J}^{-1}\mathbf{h})_j$ as a walk-sum $\sum_{\text{walks}} \text{weight}$; GaBP's update collects all walks from sources to $j$ even on loopy graphs.

Each stable fixed point has a basin of attraction in message space. The initialization determines which basin the trajectory enters.

Run BP from multiple random initializations. If outputs differ, the system has multiple fixed points and the solution is initialization-dependent — a sign of underlying model multimodality.

Each fixed point corresponds to a Bethe free energy stationary point. The 'correct' fixed point is usually the global minimum, but BP can get stuck at local minima.

$P(Y=0|X=0) = 0.9, P(Y=0|X=1) = 0.1$. $L = \log(0.9/0.1) = \log 9 \approx 2.197$ when $y = 0$. $L = \log(0.1/0.9) = -\log 9 \approx -2.197$ when $y = 1$.

$O(|\mathcal{E}|) = 5 \times 10^4$ scalar ops per iteration. With 20 iterations: $10^6$ ops.

Dense inversion: $N^3 = 10^{12}$ — intractable. Sparse direct solver: $O(N^{1.5}) = 10^6$, similar but with factorization overhead.

GaBP is competitive with sparse direct solvers and more parallel-friendly. Advantage grows with sparsity.

$\alpha_t(s) = p(y_{1:t}, s_t = s) = \sum_{s'} \alpha_{t-1}(s') P(s|s') P(y_t|s)$.

$\beta_t(s) = p(y_{t+1:T} | s_t = s) = \sum_{s'} P(s'|s) P(y_{t+1}|s') \beta_{t+1}(s')$.

$p(s_t = s | \mathbf{y}) \propto \alpha_t(s) \beta_t(s)$. Forward-backward is sum-product on the HMM factor graph.

If all $L_{i\to c} = 0$, then variable-node update gives $L_{c \to i} = 2\operatorname{atanh}(0) = 0$. Then variable-to-check $L_{i \to c} = 0 + \sum 0 = 0$. Fixed.

Without channel information, BP remains uncertain. This is the erasure $\epsilon = 1$ limit: nothing to decode.

Any tiny nonzero channel LLR (say from a single non-erased bit) propagates through iterations, breaking symmetry. BP is symmetry-aware.

Each factor-to-variable $\max$ update selects the best configuration of its $d$-ary factor given the best incoming messages. Storing the argmax at each step creates a chain of optimal choices consistent across the tree.

Example: $p(0, 0) = p(1, 1) = 0.5$. Max-marginals are uniform, so $\arg\max b_i$ gives any tied choice independently per node — could yield $(0, 1)$, which has probability zero. Backpointers resolve ties consistently.

Always follow backpointers for joint MAP reconstruction on trees. Independent argmax is incorrect when the posterior has symmetries.

At node $i$, incoming messages $(h_{k \to i}, J_{k \to i})$ for $k \in \partial i$. Total precision: $J_i = J_{ii} + \sum_k J_{k \to i}$. Total potential: $h_i^{\text{tot}} = h_i + \sum_k h_{k \to i}$.

Exclude neighbor $j$: $J_{i \to j} = -(J_{ij})^2 / (J_{ii} + \sum_{k \neq j} J_{k \to i})$. $h_{i \to j} = -J_{ij} \cdot (h_i + \sum_{k \neq j} h_{k \to i}) / (J_{ii} + \sum_{k \neq j} J_{k \to i})$.

(1) Kalman filter/smoother: HMM with Gaussian transitions and emissions → chain factor graph, GaBP = Kalman filter. (2) Gaussian Markov random field denoising on a tree (e.g., along a pyramid or quadtree).

$n$ variable nodes connected to a single factor $f(\mathbf{x}) = \mathbb{1}\{x_1 = \ldots = x_n\}$.

Variable-to-factor: $L_{i \to f} = L_i^{\text{ch}}$. Factor-to-variable: $L_{f \to i} = \sum_{j \neq i} L_{j \to f}$ (by the equality-check factor: flipping any one bit is infeasible, so the message is $\sum$ of the others).

$L_i^{\text{tot}} = L_i^{\text{ch}} + \sum_{j \neq i} L_j^{\text{ch}} = \sum_j L_j^{\text{ch}}$. Decision: $\hat{x}_i = \operatorname{sgn}(\sum L_j) =$ majority.

All messages equal $(m, 1-m)$ for some $m$. The check-node update: $L = 2\operatorname{atanh}(\tanh\theta \cdot \tanh(L/2))$, where $L$ is the common LLR. Solving: $L = 2\theta$ (the fixed point matches the intrinsic pairwise strength).

$L_i = 2L = 4\theta$, so $b(x_i = +1) = \sigma(4\theta)$.

By symmetry, $p(x_i = +1) = 1/2$. BP is wrong — it says a skewed marginal because the cycle has created phantom correlation. Loopy BP fails on this small graph.

Short cycles combined with strong coupling can severely mislead loopy BP. Longer cycles or weaker coupling would improve performance.

Let $f_\ell(L)$ be the density of variable-to-check messages at iteration $\ell$. Variable-node update: convolution of $d_v - 1$ check messages with channel LLR. Check-node update: a nonlinear transform via $\phi$.

Assume $f_\ell \approx \mathcal{N}(m_\ell, 2 m_\ell)$ (symmetric Gaussian). Track only $m_\ell$. Then density evolution reduces to a scalar recursion in $m_\ell$: $m_{\ell+1} =$ function of $m_\ell$ (involves expectations under Gaussian).

Threshold SNR = largest SNR for which $m_\ell \to 0$ fails. For $(3,6)$-regular on BI-AWGN: threshold $\approx 1.11$ dB (Shannon limit for rate 1/2: $\approx 0.187$ dB, gap 0.92 dB).