The posterior mean of the number infected is
Run sum-product belief propagation on the tree to compute every exact one-vertex posterior marginal. Summing their probabilities of state one gives the requested mean. Messages have fixed size and every directed edge is processed once, so the exact computation costs
Writing , the edge term rewards neighboring computers having the same infection state, as in a ferromagnetic Ising model, while expresses a mild prior preference for the rarer uninfected state. Thus the prior encodes local transmission over the network without assuming independent infections.
The observation likelihood is
Consequently the posterior distribution is
This remains a binary pairwise Markov random field on a tree. To find its maximum a posteriori estimate, run max-product belief propagation: send a two-entry message in each direction along every edge, then backtrack from the maximizing root state. Each message examines four state pairs, and the maximum degree is bounded, so the total cost is
Let
and choose attaining the maximum. For every , the Strong Markov property at time gives
Thus
If , then
Since , this is impossible when . Allowing for integer times, one may take any smaller absolute constant, for example
Let be a finite reversible Markov chain with stationary distribution , and write for an oriented transition edge . For every ordered pair choose a directed path from to using positive-capacity edges, and define the congestion
Then the Canonical paths comparison theorem gives the Poincaré inequality
for every real function , and hence the spectral gap is at least .
Indeed,
Write each difference as the sum of edge differences along and apply Cauchy-Schwarz inequality:
Interchanging the pair and edge sums, then applying the definition of , bounds the result by
For a nonregular graph, use the degree-weighted Hamming metric
Under the same coupling,
Here the final double sum equals . Since and whenever the chains differ,
Couple two noisy voter model chains by choosing the same update vertex, the same refresh coin and refreshed spin, and, for a voter update, the same chosen neighbor. Let be their Hamming distance. If is -regular, conditioning on the current disagreement set gives
because every disagreeing vertex is counted in exactly neighbor sets. Therefore
The coupling inequality for total variation and give
Take and start from the lower endpoint. The stationary distribution of this birth-death chain satisfies detailed balance with
so it is concentrated within of the upper endpoint . Before reaching that region the walk has drift . The weak law of large numbers and exponential concentration therefore imply that its hitting time of is
At time the chain is still macroscopically below the stationary region with probability tending to one, so its total-variation distance tends to one. Under the monotone coupling from part (b), by time the extremal copies have coalesced with probability tending to one, so the distance tends to zero. Therefore the family has
Use the monotone grand coupling in every coordinate: at each step use the same attempted move for chains started from the bottom and top states, censoring moves that leave the interval. The two copies coalesce after the lower copy has accumulated enough upward drift and boundary censoring has removed their initial separation. Away from the boundary, one step has mean displacement
Standard exponential concentration for sums of bounded independent increments shows that for every fixed the one-coordinate coupling time satisfies
All other initial states lie between the extremal copies. Coupling the coordinates independently and using the union bound gives
because . The coupling inequality for total variation therefore gives
The chain is a random walk on the finite abelian group , so its stationary distribution is uniform and its characters diagonalize the transition operator. For one coordinate and , the eigenvalue is
Uniformly in ,
for an absolute . Hence the one-coordinate chi-squared distance after is at most . The coordinates evolve independently, so the product formula for chi-squared distance gives
The chi-squared divergence bound on total variation distance now yields
uniformly in .
For , the first nonconstant character has eigenvalue modulus , uniformly in . Testing against its real or imaginary part gives a fixed positive total-variation distance until time . Thus
Exhaust by finite boxes and let be a uniform spanning tree of . Every finite tree satisfies the handshaking lemma, so
Choose the root uniformly from . The proportion of roots within any fixed distance of the boundary tends to zero, and the rooted trees converge locally to the uniform spanning tree of . Since every degree is at most four, expectations also converge. Translation invariance therefore gives
The four edges incident to have equal inclusion probability by the rotations and reflections of the square lattice. If that common probability is , then . Consequently
for every edge by translation invariance.
For an infinite locally finite recurrent connected graph, take an increasing exhaustion by finite connected subgraphs and sample a uniform spanning tree in each. The restrictions to any fixed finite edge set converge in distribution; on a recurrent graph the free and wired limits coincide and form one tree. This infinite-volume law is called the uniform spanning tree of the recurrent graph.
It can be generated by Wilson's algorithm. Fix a root and an enumeration of the remaining vertices. Starting with the root, run a random walk from the first vertex not yet in the tree until it hits the existing tree, erase its loops chronologically, and add the resulting path. Recurrence ensures every walk hits the finite tree almost surely. Repeating this operation produces the infinite uniform spanning tree, independently of the enumeration.
Let be the voltage with , , and harmonic values at every other vertex. For any other admissible , write , where . Its discrete Dirichlet energy expands as
Discrete summation by parts turns the cross term into
because is harmonic in the interior and vanishes at the boundary. Thus minimizes the energy. Under a unit voltage drop, its energy equals the total current from to , namely the effective conductance . Therefore the Dirichlet principle gives
Put and let . The conductance-hitting identity for an electrical network is
where the vertices of are wired together. It follows by taking the hitting probability of before returning to as a voltage and computing its total current out of .
Split the walk into successive excursions from . The first excursion that hits determines whether or is hit first. Its conditional probability of hitting is at most the probability that an arbitrary excursion hits , divided by the probability that it hits . Hence
A voltage with boundary values and is a function that is harmonic at every other vertex:
A current flow is an antisymmetric function satisfying Kirchhoff's node law away from its source and sink. Voltage and current are related by Ohm's law,
The effective resistance is the voltage drop divided by the total current from to . Equivalently, it is the voltage drop generated by a unit current flow:
By Tonelli theorem,
If , part (a) bounds the summand by . There are only polynomially many vertices at each radius, so the series converges and .
Conversely, suppose . Then . Choose so close to that
Use the standard sprinkling coupling for Bernoulli percolation: first expose the -open clusters, then independently open each remaining edge with probability . Explore the -cluster of the origin cluster by following sprinkled edges. Each discovered -cluster has at most times its number of vertices as many incident edges, so the exploration is dominated by a Galton-Watson process of mean at most . This process dies out almost surely, and hence there is no infinite -open cluster. Thus , and implies . Therefore
Because , choose a finite set with . Let exceed the -distance from to every endpoint of an edge in , and put
On the one-arm event to distance , take the first oriented boundary edge used by an open self-avoiding path. The connection , the open edge , and the remaining connection from to occur disjointly. The Van den Berg-Kesten inequality and translation invariance therefore give
Iteration yields up to an inessential finite-scale adjustment. Since , each of the finitely many remaining is strictly below one, so reducing the exponent if necessary produces a constant valid for every :
This is the finite-size proof of exponential decay of subcritical percolation.

Pinned article: Introduction to the OurBigBook Project

Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
We have two killer features:
  1. topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculus
    Articles of different users are sorted by upvote within each article page. This feature is a bit like:
    • a Wikipedia where each user can have their own version of each article
    • a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
    This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
    Figure 1.
    Screenshot of the "Derivative" topic page
    . View it live at: ourbigbook.com/go/topic/derivative
  2. local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:
    This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
    Figure 5. . You can also edit articles on the Web editor without installing anything locally.
    Video 3.
    Edit locally and publish demo
    . Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.
  3. https://raw.githubusercontent.com/ourbigbook/ourbigbook-media/master/feature/x/hilbert-space-arrow.png
  4. Infinitely deep tables of contents:
    Figure 6.
    Dynamic article tree with infinitely deep table of contents
    .
    Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact