versing path whose first step is $v\to u$). 
If $i$ is a variable index and $a$ a parity-check index, let
$\mu_{i\to a}(\, \cdot\, )$ be the measure over $\underline{x} = \{x_j:\,
j\in G(i\to a)\}$, that is obtained by retaining in 
Eq.~(\ref{eq:ProbLDPC}) only those terms that are related to nodes
in $G(i\to a)$:
\begin{eqnarray}
\mu_{i\to a}(\underline{x}) = \frac{1}{Z(i\to a)}\, \prod_{j\in G(i\to a)}
Q(y_i|x_i)\;\prod_{b\in G(i\to a)} {\mathbb I}(x_{i_1(b)}\oplus\cdots\oplus
x_{i_k(b)}={\tt 0})\,.
\end{eqnarray}
The measure $\widehat{\mu}_{a\to i}(\,\cdot\,)$ is defined analogously
for the subtree $G(a\to i)$. The marginals $\mu_{i\to a}(x_i)$
(respectively $\widehat{\mu}_{a\to i}(x_i)$) are easily seen to
satisfy the recursions 
\begin{eqnarray}
\mu_{i\to a}(x_i)  & \propto&  Q(y_i|x_i)\!\prod_{b\in\partial i\backslash a}
\widehat{\mu}_{b\to i}(x_i)\,,\label{eq:TreeRec1}\\
\widehat{\mu}_{a\to i}(x_i) & \propto & \sum_{\{x_j\}}
{\mathbb I}(x_i\oplus x_{j_1}\oplus \cdots\oplus x_{j_{k-1}}= {\tt 0})
\prod_{j\in\partial a\backslash i}\mu_{j\to a}(x_j)\,,\label{eq:TreeRec2}
\end{eqnarray}
which coincide, apart from the time index, with the BP recursion
(\ref{eq:BPdec1}), (\ref{eq:BPdec2}). That such recursions
converges to $\{\mu_{i\to a}(x_i),\widehat{\mu}_{a\to i}(x_i)\}$
follows by induction over the tree depth.

In statistical mechanics equations similar to
(\ref{eq:TreeRec1}), (\ref{eq:TreeRec2}) are 
often written as recursions on the constrained partition function.
They allow to solve exactly models on trees. 
However they have been often applied as mean-field approximation
to statistical models on non-tree graphs. 
This is often referred to as  the \emph{Bethe-Peierls approximation}
\cite{Bethe}.

The Bethe approximation presents several advantages with respect to 
`naive-mean field' \cite{YedidiaFreemanWeiss}
(that amounts to writing `self-consistency'
equations for expectations over single degrees of freedom).
It retains correlations among degrees of freedom that interact directly,
and is exact on some non-empty graph (trees). It is often asymptotically
(in the large size limit) exact on locally tree-like graphs.
Finally, it is quantitatively more accurate for non-tree like graphs and
offers a much richer modeling palette.

Within the theory of disordered systems
(especially, glass models on sparse random graphs), 
Eqs.~(\ref{eq:TreeRec1}) and (\ref{eq:TreeRec2}) are also referred
to as the \emph{cavity equations}. With respect to Bethe-Peierls, the cavity 
approach includes a hierarchy of (`replica symmetry breaking') refinements
of such equations that aim at capturing long range correlations
\cite{MezardParisiBethe}. 
This will briefly described in Section \ref{sec:beyondcoding}.

We should finally mention that several improvements over 
Bethe approximation have been developed within statistical physics.
Among them, Kikuchi's cluster variational method 
\cite{Kikuchi} is worth mentioning
since it motivated the development of a `generalized 
belief propagation' algorithm, which spurred a lot of
interest within the artificial intelligence community 
\cite{YedidiaFreemanWeiss}.
\subsection{Density Evolution}
Although BP  converges to the exact marginals on tree graphs,
this says little about its performances on practical codes
such as the LDPC ensembles introduced in Section~\ref{sec:sparsegraphcode}.
Fortunately, a rather precise picture on the performance of LDPC ensembles can be derived in the large 
blocklength limit $N\to\infty$. The basic reason for 
this is that the corresponding random factor graph is locally 
tree-like with high probability if we consider large blocklengths.

Before elaborating on this point, notice that the performance under BP decoding 
(e.g., the bit error rate) is independent on the transmitted codeword.
For the sake of analysis, we shall hereafter assume that the all-zero 
codeword $\underline{\tt 0}$ has been transmitted.

Consider a factor graph $G$ and let $(i, a)$ be one of its edges.
Consider the message $\nu^{(t)}_{i\to a}$ sent by the BP decoder in iteration
$t$ along edge $(i, a)$. A considerable amount of information is contained in the 
distribution of $\nu^{(t)}_{i\to a}$ with respect to the channel realization,
as well as in the analogous distribution for $\widehat{\nu}^{(t)}_{a\to i}$.
To see this, note that under the all-zero codeword 
assumption, the bit error rate after $t$ iterations is given by
\begin{eqnarray}
{\rm P}_{{\rm b}}^{(t)} = \frac{1}{n}\sum_{i=1}^n
{\mathbb P}\left\{\Phi_i(\{\widehat{\nu}_{b\to i}^{(t)};b\in\partial i\};y_i)\neq {\tt 0}\right\}\,.
\end{eqnarray}
Therefore, if the messages $\widehat{\nu}_{b\to i}^{(t)}$ are independent, then the bit
error probability is determined by the distribution of $\widehat{\nu}^{(t)}_{a\to i}$.

Rather than considering one particular graph (code) and a specific
edge, it is much simpler to take the average over all edges and all graph realizations.
We thus consider the distribution ${\sf a}_t^{(N)}(\,\cdot\,)$
of $\nu^{(t)}_{i\to a}$ with respect to the channel, the edges, \emph{and} the graph
realization. While this is still a
quite difficult object to study rigorously, it is on the other
hand possible to characterize its large blocklength limit
${\sf a}_t(\,\cdot\,) = \lim_N{\sf a}_t^{(N)}(\,\cdot\,)$.
This distribution satisfies a simple recursion.
\begin{figure}[htp]
\centering
\setlength{\unitlength}{0.8bp}%
\begin{picture}(322,490)(-22,-10)
\tiny
\put(0,400)
{
\multiputlist(-22,14.2)(0,14.2)[l]{$0.05$,$0.10$,$0.15$,$0.20$}
\multiputlist(0,-10)(23.65,0)[b]{$\text{-}10$,$0$,$10$,$20$,$30$,$40$}
\multiputlist(158,14.2)(0,14.2)[l]{$0.05$,$0.10$,$0.15$,$0.20$}
\multiputlist(180,-10)(23.65,0)[b]{$\text{-}10$,$0$,$10$,$20$,$30$,$40$}
\put(0,0){\includegraphics[scale=0.8]{densvar0.ps}}
\put(180,0){\includegraphics[scale=0.8]{denscheck0.ps}}
}
\put(0,300)
{
\multiputlist(-22,14.2)(0,14.2)[l]{$0.05$,$0.10$,$0.15$,$0.20$}
\multiputlist(0,-10)(23.65,0)[b]{$\text{-}10$,$0$,$10$,$20$,$30$,$40$}
\multiputlist(158,14.2)(0,14.2)[l]{$0.05$,$0.10$,$0.15$,$0.20$}
\multiputlist(180,-10)(23.65,0)[b]{$\text{-}10$,$0$,$10$,$20$,$30$,$40$}
\put(0,0){\includegraphics[