Entropy vs. energy

Quick description

Entropy vs. energy is a powerful technique in discrete probability. You begin with a probability measure which depends on some parameter. To estimate certain events under this measure, you tune the parameter so that the number of possible configurations (entropy) does not outweigh the probability of each configuration satisfying that event (energy).

Prerequisites

Elementary probability. Borel-Cantelli_lemma

Example 1

Percolation. Consider the lattice $\mathbb Z^d$ for $d \ge 2$ . Let $p \in [0,1]$ . Independently, we consider each bond (edge) of the lattice to be open with probability $p$ and closed with probability $1-p$ . We write the probability measure of this model $\mathbb P_p$ , indicating the dependence on the parameter $p$ .

A natural question to ask is if there exists a connected component of infinitely many open bonds, which we call an infinite cluster. This is a random event which depends on the parameter $p$ . Since the existence of such a cluster is translation-invariant, the Kolmogorov 0-1 Law says that a cluster either exists with $\mathbb P_p$ -probability one or zero. If such a cluster exists, the origin may or may not belong to it. This is not a translation-invariant event, so we write

$\theta(p) = \mathbb P_p (\mbox{0 belongs to an infinite cluster}).$

If $p = 1$ , every bond is open so $\theta(1) = 1$ , that is 0 trivially belongs to the cluster. Conversely, if $p = 0$ , every bond is closed so $\theta(0) = 0$ . We are interested in the behavior of the function $\theta(p)$ . Let

$\theta(p) = 0 \},$

be the highest value of $p$ such that there is no infinite cluster. It is a major early result of percolation that $p_c \in (0,1)$ .

In what follows, we use the energy vs. entropy technique to demonstrate that $p_c > 0$ . Fix a positive integer $n$ . Let $E_n$ be the event that there exists a path $\gamma$ such that $\gamma(0) = 0$ , $|\gamma| = n$ , $\gamma$ does not intersect itself, and $\gamma$ passes through only open bonds. We will show that for small but positive values of $p$ , $\mathbb P_p(E_n)$ decays exponentially in $n$ . Since $\sum_n \mathbb P_p(E_n)$ converges, the Borel-Cantelli lemma will imply that the event $E_n$ holds for only finitely many $n$ . So for such values of $p$ , 0 will belong to the infinite cluster with probability zero, hence such a cluster will almost surely not exist.

Here is the crucial observation:

$\mathbb P_p (E_n) = \mathbb P_p \left( \bigcup_\gamma \{\gamma \mbox{ passes through open bonds} \}\right) \le \sum_\gamma p^n$ (1)

where the union and outer sum are over all self-avoiding paths $\gamma$ starting at the origin of length $n$ . We overestimate the number of such paths: at the origin, $\gamma$ has $2d$ choices of direction, but at all successive points it has no more than $2d-1$ choices since it cannot backtrack. Thus the number of such paths is bounded above by $2d(2d-1)^{n-1}$ . This is an example of an entropy statement, where we count all possible configurations, versus the energy term $p^n$ .

Thus, the quantity in (1) is bounded above by $\tfrac{2d}{2d-1} (2d-1)^n p^n$ . This is quite an awful estimate, but we have considerable freedom in choosing the value of $p$ . In particular, if we choose $p < \tfrac{1}{2d-1}$ , then the series $\sum_n \mathbb P_p (E_n)$ is bounded above by a convergent geometric series, and the Borel-Cantelli lemma applies as stated above. Thus for such $p$ , $\theta(p) = 0$ , proving that the critical value $p_c$ is strictly positive.

This is not the end of the story, of course. In the case $d = 2$ , this argument shows that $p_c \ge 1/3$ . This argument was formulated in the sixties by Hammersley (I think, needs verification). However, the true value of $p_c$ for $\mathbb Z^2$ is $p_c = 1/2$ , which was not proved until Kesten in 1982 (I think). Entropy vs. energy is a powerful technique, provided you do not need optimal parameters.