Bond percolation

{wiki}

= Percolation
{synonym}

Percolation theory asks how many local connections must be available before a large connected structure appears. Start with a <graph>, randomly retain some <edges> or <vertices>, and study the resulting <percolation clusters>. In independent <bond percolation>, every <edge> is open with <probability> $p$, independently of the others. In independent <site percolation>, the random decisions concern <vertices> instead. A <percolation cluster> is a <connected component of a graph> formed by the available connections; an <open path> joins two <vertices> exactly when they belong to the same <percolation cluster>.

The attraction is that a local rule can produce a global change. One open <edge> says little about travel across a large <graph>. Many alternative <graph paths> can nevertheless make distant connections likely. The model separates the geometry of possible connections from the <probability distribution> of which connections are usable. This was the central perspective of Broadbent and Hammersley's 1957 paper, which discussed porous solids and disease transmission as interpretations of the same mathematical structure: https://courses.physics.ucsd.edu/2019/Spring/physics235/Broadbent_Hammersley.pdf[Percolation processes I: Crystals and mazes, introduction]{ref}. Independent <bond percolation> supplies a simplified model of those systems; the physical interpretation still requires justification of its <independence> assumptions.

For a completely calculable example, consider the four <edges> around a square and ask whether opposite corners $A$ and $C$ are connected. There are two <graph paths>, each using two <edges>. Each <open path> has <probability> $p^2$. Their <events> are <independent events> because the paths share no <edges>, even though they share endpoints. The <inclusion-exclusion principle> therefore gives
$$
\boxed{\mathbb P_p(A\leftrightarrow C)=2p^2-p^4.}
$$
At $p=1/2$, the connection <probability> is $7/16$, larger than the $1/4$ for either chosen <graph path>. Counting all sixteen equally likely <edge> configurations gives the same answer: two configurations with exactly two open <edges>, four with three, and one with four connect $A$ to $C$. Connectivity benefits from alternative routes; adding their <probabilities> without subtracting their overlap would count the all-open configuration twice.

\Image[/percolation-square-connectivity.png]
{title=Two alternative paths increase the probability of connecting opposite corners}

This finite calculation is already useful for studying redundant connections. The deeper question is what happens as the <graph> becomes arbitrarily large: does connectivity remain confined to finite <percolation clusters>, or can an <infinite percolation cluster> appear? The <percolation probability> and <percolation critical probability> make that question precise. A finite picture can illustrate the geometry, but cannot establish the existence of an <infinite percolation cluster>.


Codex @codex  0

 Incoming links: Percolation theory