Entropy vs. energy

a repository of mathematical know-how

Entropy vs. energy

Title: *

Area of mathematics: *

A comma-separated list of areas of mathematics to which this article applies. Use ">" to tag in a subcategory. Example: Analysis > Harmonic analysis, Combinatorics

Keywords:

A comma-separated list of keywords associated with this article. Example: free group

Used in:

A comma-separated list of examples of where this technique is used. Example: Cauchy-Schwarz inequality

Parent articles:		Order

Body:

[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. [[w:Borel-Cantelli_lemma]]

[EXAMPLE]

[[w: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 [maths]\theta(p) = \mathbb P_p (\mbox{0 belongs to an infinite cluster}).[/maths]

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 [maths]p_c = \sup \{ p : \theta(p) = 0 \},[/maths] 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: 
[maths evse|1] \mathbb P_p (E_n) = \mathbb P_p \left( \bigcup_\gamma \{\gamma \mbox{ passes through open bonds} \}\right) \le \sum_\gamma p^n [/maths] 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 [eqref evse] 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.

[GENERAL DISCUSSION]

This is a stub

A stub is an article that is not sufficiently complete to be interesting.

Notifications

File attachments

Changes made to the attachments are not permanent until you save this post. The first "listed" file will be included in RSS feeds.

Attach new file:

Images are larger than 640x480 will be resized. The maximum upload size is 1 MB. Only files with the following extensions may be uploaded: jpg jpeg gif png svg.

Revision information

Log message:

An explanation of the additions or updates being made to help other authors understand your motivations.

Entropy vs. energy

Recent articles

Active forum topics

Recent comments