Probability and Computing

[2025 Summer] Statistical Physics and Computation

Location: 软件学院 1319

Schedule

[Sep 03] Decoding wiht belief propagation

Following Chapter 15 of [MM09], we study the decoding of LDPC codes using belief propagation and explore the density evolution equation on locally tree-like random factor graphs. For the special case of the Binary Erasure Channel (BEC), we show that this equation can be solved analytically, resulting in a method for designing the optimal factor graph ensemble, \(\bb D(\Lambda,P)\), that achieves the channel capacity.

[Aug 20] Belief propagation on trees

Following Chapter 14 of [MM09], this lecture introduces Belief Propagation (BP) equations. We show that the iterative BP algorithm is exact for computing marginals on tree-structured factor graphs. We then demonstrate how to use BP messages to calculate key quantities in statistical physics, including internal energy, free energy, and entropy. Finally, we introduce the notion of Bethe free entropy, a concept useful for identifying fixed points of BP equations on graphs with cycles (loopy graphs).

[Aug 13] Naive mean field approximation and TAP equation for SK model, Cavity method, Belief propagation

We first examine the naive mean field approximation of the average magnetization for the Ising model and explain why it fails for the SK model. Then we present a fix for this issue: the Thouless-Anderson-Palmer equation and derive it using the cavity method. This part is based on [Nis21]. At last, we introduce an algorithmic approach towards the cavity method, namely the Belief Propagation (BP) algorithm, following Chapter 14 of [MM09].

[July 30] The SK model, RS solution

We study the SK model \(\mu(x)\propto \exp\tp{\frac{\beta}{2}x^\top J x}\) where \(J_{ij}\sim \+N(0,\frac{1}{n})\) and derive the critical temperature \(\beta_c=1\) using a replica symmetry argument.

One notably technique used in the calculation is the Hubbard-Stratonovich transformation, or equivalenty the formula for the Gaussian MGF.

Our calculations mainly follow those in [Nis21].

[July 23] The REM model, RS and 1-RSB solution for REM

We define the Random Energy Model (REM) and study its phase transition.

• The phase transition of its free energy can be rigorously derived via simple probabilistic argument. See [Tal03].
• We also demonstrate the prediction of the phase transition using the heuristic of the replica trick and 1-replica symmetric breaking. See [MM09] and [Kab].

References

• [Tal11] Mean Fields Models for Spin Glasses, Vol I. Michel Talagrand
• [Tal03] Spin Glasses: A Challenge for Mathematicians. Michel Talagrand (This is in fact the first version of the above. But I found something useful.)
• [MM09] Information, Physics, and Computation. Marc Mézard, Andrea Montanari
• [Kab] Introduction to the replica method. Yoshiyuki Kabashima
• [Nis21] Statistical Physics of Spin Glasses and Information Processing An Introduction. Hidetoshi Nishimori