Topics (384k) Articles (398k) Users (410) Discussions (242) Comments (383) Files (13k) New article
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 215 4 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Use . The Dirichlet form of a Markov chain isThe equality follows by expanding the square and using row sums one and the stationary distribution identity. For the reversible Markov chain, detailed balance makes a self-adjoint operator, with real orthonormal eigenbasis and ordered eigenvalues .
Adding a constant changes neither the variance nor the Dirichlet form of a Markov chain. Expand the centered function as . ThenFor every nonconstant the quotient is at least , and equality is attained at . This provesEquivalently minimize the Dirichlet form of a Markov chain over centered unit-norm functions. This is the variational characterization underlying the Poincare inequality for a reversible Markov chain, and does not require the transition matrix to have nonnegative eigenvalues. For a one-state chain there is no nonconstant test function; the displayed minimization concerns .
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 215 3 d Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
For each subset , take the Walsh character , including . Under the uniform distribution on a finite set these functions are an orthonormal basis: has mean zero unless , since the coordinates are independent fair signs. There are such functions, the full dimension of the function space.
Flipping a coordinate in changes the sign, while flipping one outside leaves the value unchanged. The total probability of a sign change is , soThe spectrum of lazy random walk on the hypercube is thereforeAll eigenvalues are nonnegative and the second largest is . Hence both the ordinary spectral gap and the absolute spectral gap equal . The requested bound in part (c) is smaller than the exact gap by a factor ; even the refined increasing-coordinate canonical paths Poincare bound loses a factor . The true optimal Poincare inequality for a reversible Markov chain constant is .
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 215 3 c Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
The lazy Markov chain has holding probability and transition probability to each neighbour in the hypercube graph. Its stationary distribution is by symmetry.
For choose the path changing the differing coordinates in increasing order. Its length is at most . Fix a directed edge that flips coordinate . A path uses this edge exactly when , , for , and for . The coordinates for and for are free. Thus exactly ordered pairs use it, whileThe unweighted load divided by capacity equals ; multiplying by the maximum length yields . The canonical paths Poincare bound therefore proves the slightly stronger , and in particular the requestedOne can keep the actual lengths: among these pairs, coordinate always differs, and each of the other coordinates differs for half the pairs. Their mean path length is , giving exact congestion . This refinement still has order .
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 215 3 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
For a finite irreducible Markov chain satisfying detailed balance, define the directed-edge capacity . For every ordered pair choose a path from to using only positive-capacity edges; take the empty path for . Let count occurrences of the directed edge . The canonical paths Poincare bound says thatis a valid Poincare inequality for a reversible Markov chain constant. Simple paths give ; allowing repetitions requires the multiplicities shown.
To prove the theorem, expand the variance using two independent samples from :Telescoping along and applying the Cauchy-Schwarz inequality givesInterchange the finite sums, then use the definition of :Consequently . All edges here are directed, so the in the Dirichlet form of a Markov chain is retained consistently.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 215 3 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
On a finite state space with at least two states, as in the surrounding questions, for a real function write and . The Poincare inequality for a reversible Markov chain with constant iswhere the Dirichlet form of a Markov chain isThe associated spectral gap is the ordinary gap , with variational formulaEquivalently minimize subject to and . Thus the Poincare inequality for a reversible Markov chain holds precisely for , and the optimal constant is . It controls the ordinary rather than absolute spectral gap, so negative eigenvalues do not invalidate it. If the unspecified state space in this part is infinite, the Poincare inequality for a reversible Markov chain and the variational infimum still make sense on nonconstant functions in , using the self-adjoint operator on that Hilbert space; the resulting spectral gap need not be represented by an actual second eigenvalue. The finite-state formula above is the intended specialization.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 215 2 d Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Use the ratio definition of cutoff from part (a), and write . In the reversible Markov chain setting of the preceding parts let and . In particular .
If did not tend to infinity, there would be a subsequence and for which . Along it part (c) implies, for every fixed ,Since , choose fixed so small that . The lower limit of this ratio is then greater than one, contradicting cutoff for Markov chains. Thus the Peres product condition holds:In fact the argument with proves the stronger absolute-gap product condition. Part (d) does not repeat the reversible Markov chain hypothesis; the ordinary real ordering of eigenvalues above uses that hypothesis. If arbitrary chains are intended, define the spectral gap explicitly: the eigenvalue lower bound for total variation mixing works for complex eigenfunctions too, and proves the same assertion for or for , which is at least . No real ordering of complex eigenvalues is implicit.
For the requested counterexample take nonlazy simple random walk on the complete graph , . Let have every row equal to the uniform distribution on a finite set, and let . ThenThus and : every fixed-level mixing time is eventually one. This is a bounded-time jump satisfying the ratio definition of cutoff. The ordinary spectral gap is and the absolute one is , so both products with tend to one, not infinity. The divergence assumption on is therefore essential under this convention.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 215 2 c Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Let be the number of states and putThe absolute L2 spectral gap of a reversible Markov chain is ; in this question the relaxation time means the absolute relaxation time. For a nonlazy reversible Markov chain, it may differ from the reciprocal of the ordinary spectral gap . For a finite irreducible Markov chain that is an aperiodic Markov chain, .
For , choose a real eigenfunction whose eigenvalue has modulus , and an initial state maximizing . It has , and the definition of total variation distance impliesThis is the eigenvalue lower bound for total variation mixing, . At , for ,The second inequality follows from , the supplied inequality with . Since ,When the left side is zero, so no logarithm of zero is needed. For the left side is nonpositive and the conclusion is automatic. A one-state chain has mixing time zero; with the convention the bound is again trivial.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 215 2 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Take the real inner productThe stationary distribution is strictly positive for an irreducible Markov chain. Detailed balance gives , so is a self-adjoint operator. Choose a real orthonormal eigenbasis , where , , , , and for .
For fixed , apply the spectral decomposition to . Its coefficient against is , whereas . Thus the spectral kernel expansion of a reversible chain isThis holds for all integers ; at each multiplier is one, including when . Negative eigenvalues are allowed, and retain their signs for odd .
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 215 2 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
For a finite irreducible Markov chain that is an aperiodic Markov chain, setHere is its unique stationary distribution, and the distance is total variation distance. Applying a Markov kernel contracts total variation distance, so is nonincreasing and the minimum is finite.
Use the ratio definition of cutoff: a family has cutoff for Markov chains if, for every fixed ,with the denominator positive eventually. Thus the transition between any two fixed distance levels takes negligible time compared with the mixing time scale. By monotonicity and squeezing, this also gives for any fixed .
Some definitions of cutoff for Markov chains additionally require the mixing time to diverge. That extra requirement cannot be built into the definition here: the final request in part (d) explicitly asks for a bounded-time counterexample. The ratio convention is the one consistent with that request.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 215 1 c Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Let interchange the two complete graphs, sending to and fixing . This involution preserves the transition matrix of the simple random walk. A mirror coupling under an involution starts at , keeps until the hitting time of , and then makes the two walks move identically. Each coordinate has the correct transition probabilities, and they coalesce precisely at . The coupling inequality for total variation gives
There is a genuine error in the printed expected hitting time bound, as well as an unspecified initial law. For , write and for . From every clique vertex there is a positive chance of reaching within two steps, uniformly over the finite state space for each fixed , so has finite expected value. First-step analysis, using the degree of a vertex at and at the other clique vertices, givesSolving these linear equations yieldsIn particular even the attachment vertex exceeds the printed bound by one. The valid uniform replacement is , the hitting time of the bridge vertex between two cliques formula.
We must also handle arbitrary starting states, including , before applying the mirror argument. Identify related vertices and consider the lumped Markov chain on . Its transition matrix has for , , for and , and , with all other entries zero. Here the row for only ranges over .
For and , direct two-step calculation givesAll these entries are at least . Thus for every , where is the uniform distribution on a finite set and . This is a Doeblin condition. At each two-step block couple the two quotient endpoints to the same sample from with probability , using the residual probability distributions otherwise. The first successful block has expected value at most , so the alignment time has . Lift each endpoint coupling of probability distributions to the original walks by their conditional two-step path laws; this preserves every marginal path law. The success test uses fresh block randomness and so permits restarting the walks with their original transition matrix at the aligned endpoints.
At alignment the original walks are equal or related. Use identical transitions in the first case and the mirror coupling under an involution in the second. The resulting coalescing coupling has coalescence time satisfying for every pair of initial states. Therefore Markov inequality and the pairwise mixing diameter implyFor the hint's particular starting states, the quotient one-step laws from two different clique indices have a common component of mass at least : for two ordinary indices it is ; for one attachment index it is . A maximal coupling therefore aligns those indices with probability , as suggested. The two-step argument above additionally covers .
The nonlazy walk is an aperiodic Markov chain for , because the connected graph contains a triangle. For it is a periodic Markov chain on a bipartite graph; each bipartition class has stationary mass , and the walk stays on a single class at each time. Hence and the mixing time is infinite. The asymptotic conclusion is valid for .
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 215 1 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
A coupling of probability distributions is a joint probability distribution of random variables with the specified marginal distributions: and . No independence is required.
For every set , the difference of the two indicator functions vanishes when . ConsequentlyMaximizing over gives the coupling inequality for total variation:
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 215 1 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
For probability distributions on a finite set, the total variation distance isThe equality follows by taking : the positive and negative parts of have the same mass, since its total mass is zero.
Use the stationary distribution identity . For each initial state ,The triangle inequality for total variation distance, followed by the definition of the pairwise mixing diameter, givesTaking the maximum over proves . This particular inequality only needs a stationary distribution; it does not require an irreducible Markov chain or an aperiodic Markov chain.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 214 4 c Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
First take . Sample a uniform spanning tree using Wilson's algorithm rooted at , with processed first. The first walk runs from until its first hit of , so its loop erasure is exactly the unique -to- graph path of the resulting tree. Later attachments cannot alter that graph path. This is the uniform-spanning-tree path representation of loop-erased random walk.
Instead root Wilson's algorithm at and process first. The resulting tree still has the same uniform law, while its first attachment has the law of loop-erased random walk from to . A tree's graph path between two fixed graph vertices has the same unoriented edge set in both directions. Pushing the common tree law through this graph path map therefore givesHere means the set of unoriented edges. In fact, reversing the complete graph vertex sequence from the first loop-erased walk has the law of the second, giving reversibility of loop-erased random walk. If and first hitting allows time zero, both graph paths are empty and the equality is immediate.
This is a distributional assertion, not a pathwise identity between chronological loop erasure and reversal. For example, the valid walk trajectory in a graph containing the triangle on and the edges erases forward to . Erasing the reversed trajectory and then reversing the result gives , a different graph path. Wilson's root-independent tree law is what proves the stated equality of probability distributions.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 214 4 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
For finite , choose a root and an ordering of the other graph vertices. Begin with a tree consisting only of . At each stage take the first graph vertex not already in the tree, run an independent simple random walk from it until its first hit of the existing tree, erase the loops chronologically, and add the resulting graph path. In chronological loop erasure, revisiting a graph vertex already in the current list deletes all list entries after that graph vertex; otherwise append the new graph vertex. The retained final graph path is simple, with new internal graph vertices and exactly one endpoint in the old tree. Adding it therefore preserves connectedness and creates no graph cycle. Graph vertices already included are skipped. On a finite connected graph each walk hits the existing tree almost surely; after finitely many attachments all graph vertices are present.
The Wilson algorithm theorem states that this tree is a uniform spanning tree, independently of the chosen root and order. The required hypotheses here are an undirected connected finite graph and transition probabilities proportional to conductance; unit conductances give simple random walk and the uniform law. This is the sampling result being described, not a claim that arbitrary walk transition probabilities would produce a uniform tree.
For an infinite connected locally finite recurrent graph, choose a fixed finite root and enumerate all graph vertices. A connected locally finite graph is countable, since its finite-radius balls are finite. Run the same algorithm successively. Recurrence and irreducibility imply that a walk from any graph vertex hits almost surely, hence hits the current tree. Every attached graph path is therefore finite. The countable intersection of these probability-one events has probability one, and the increasing union is an acyclic connected subgraph containing all graph vertices: each graph vertex receives a finite route to .
This gives the uniform spanning tree of a recurrent infinite graph. It is not a uniform counting measure on all infinite spanning trees. Equivalently, its joint probability distributions on finite collections of edges are the common limits of uniform spanning trees along any graph exhaustion, using the approximations defining the free uniform spanning forest and the wired uniform spanning forest. To check that equivalence, fix a finite edge set and run the chosen enumeration through a finite prefix containing all its endpoints. Once those graph vertices are in the tree, later attachments cannot add an edge with both endpoints already included, so membership of is settled permanently. Only finitely many random walks have been used; each has a finite trajectory almost surely. All their visited graph vertices and all their graph neighbours lie in a sufficiently large exhaustion set. Couple finite-volume and infinite-volume walks with the same steps there. Whether the exterior is deleted or wired to one boundary graph vertex, these initial trajectories and their loop erasures then agree. This proves convergence of the probabilities of cylinder sets determined by those edges.
The limiting law is unchanged by the root and ordering because the laws on finite graphs have this invariance. The same coupling shows that changing the exhaustion also leaves the law unchanged. ThusThe result is a single spanning tree because the graph is recurrent. On a transient graph, infinite-volume spanning-tree limits may instead be uniform spanning forests; recurrence cannot be omitted from this conclusion.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 214 4 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-20
Let be the finite set of spanning trees of the connected graph. A spanning tree has all the graph vertices, is connected, and contains no graph cycle. Connectedness ensures that at least one exists, for example by repeatedly deleting an edge of a graph cycle while retaining connectedness. The uniform spanning tree is the random edge set withEvery tree has edges, so uniformity is over complete trees, not over arbitrary subsets of that size. Such subsets can be disconnected or cyclic and do not belong to . Nor are indicators of the tree edges generally independent. The matrix-tree theorem gives as any cofactor of the unweighted graph Laplacian if a numerical normalizing constant is needed.
This definition uses the ordinary undirected unweighted graph convention. With positive conductances the analogous law for spanning trees weights proportionally to and is generally not uniform. When the graph has one graph vertex the empty edge set is the unique spanning tree, so its probability is one.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 214 3 c Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Group the random resistance cost by unoriented edges. For , its resistance contributes once whenever the walk traverses it in either direction. Pathwise,The graph is finite and the commute has finite expected value. Linearity of expectation, or Tonelli theorem for these nonnegative terms, therefore permits taking expectations of the sum. By the directed edge occupation in a random-walk commute, both directed traversal counts have expected value . ThusApply Foster's theorem from part (a) to obtainThe factor two counts the two orientations of each edge. It would be lost by treating the expected directed count in part (b) as an expected count for both directions together. The same distinct-terminal and simple-random-walk conventions from part (b) remain in force.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 214 3 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-20
Use simple random walk on the loopless undirected unweighted graph, with transition probability to each graph neighbour, and take . Set . Returns to before visiting do not end the commute. After its first visit to , stop at the subsequent first visit to , so . Count transitions with departure times , including the final step arriving at . The expected hitting times are finite: in a finite connected graph there is a uniformly positive probability to reach any fixed target within a fixed number of steps, giving a geometric tail bound.
We prove the needed killed-walk occupation voltage identity from its visit balance equation. DefineFor , counting arrivals before absorption givesHence, for the graph Laplacian , we have away from . Since the sum of all Laplacian coordinates is zero, . Thus is the electrical voltage of a unit flow from to , grounded at , and .
Construct for the opposite killed leg. It satisfies and . Therefore . The harmonic maximum principle on a finite graph makes constant: at a maximum its value equals the average over its graph neighbours, forcing all of them to share that value, and connectedness propagates it. At the constant equals .
For any oriented edge , each visit to before the target hit produces a transition to with conditional probability . The expected traversals during the first killed leg are therefore , and those during the second leg are by the Strong Markov property at . This proves directed edge occupation in a random-walk commute:In particular, both directions of every unoriented edge have this same expected value, although their counts on an individual commute need not coincide. Summing over the directed edges also recovers the commute time identity .
The distinct-terminal convention is necessary for the printed “returns” interpretation. If and is the first positive return, a graph with two graph vertices and one edge gives while . Thus either take , as intended, or explicitly define the degenerate commute as . A general nonuniform random walk is not covered by the unweighted simple-walk formula.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 214 3 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Fix an edge and orient it from to . For each spanning tree , let be its unique graph path from to . Assign a signed unit graph path flow to oriented edges: value in the direction used by , value on the reversed orientation, and zero otherwise. Define its meanEach has net divergence one at , minus one at and zero elsewhere, so is a unit flow. The mean spanning-tree path current also satisfies the Kirchhoff cycle law. Although its verification is permitted to be omitted, a short counting argument makes it explicit. Let be the two-component spanning forests separating and , write for the component containing , and let be the number of spanning trees. Deleting an edge used by the oriented tree graph path gives one such forest. Conversely adjoining an edge across its two components gives a unique tree with that edge on its -to- graph path. ConsequentlyThe gradient form proves the Kirchhoff cycle law directly and is Ohm's law for unit edge resistance. The Kirchhoff node law then gives , and the electrical unit flow is unique: the difference between two such voltages is a harmonic function on a graph and hence constant on the connected finite graph.
If , its single-edge route is the unique tree graph path from to , so . If , that tree graph path does not use , so . ThereforeBy Ohm's law, ; for a unit terminal current, this voltage difference is exactly the effective resistance between the terminals. We have proved the requested edge-inclusion formula for a uniform spanning tree:Now use linearity of expectation and the fact that every spanning tree has exactly edges. This gives Foster's theorem:The sums here use unoriented edges exactly once. For unit conductance this is the displayed identity; with conductances the inclusion probability and summand become .
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 214 2 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
We use planar duality for rectangle crossings, Harris-FKG inequality and the permitted exponential decay of subcritical percolation. A critical-point detail matters: uniqueness stated only for cannot by itself be applied at . We prove the Burton-Keane theorem by the boundary counting proof of percolation uniqueness, establishing at most one infinite percolation cluster at every parameter and avoiding that gap.
For , the number of infinite percolation clusters is almost surely constant by translation ergodicity of Bernoulli percolation. It cannot be a finite constant greater than one. A sufficiently large box meets two different infinite percolation clusters with positive probability; opening its finitely many interior edges joins them without creating a new infinite percolation cluster, decreasing . Finite modification of Bernoulli percolation gives positive probability to this modification, contradicting constancy.
Nor can . A finite box then meets three different infinite percolation clusters with positive probability. Select one infinite exterior branch from each. In the box and a finite collar retain just an embedded three-armed tree joining those branches and close all other incident edges there. Its branching graph vertex separates three infinite components when removed, so is a trifurcation vertex in percolation. All selections concern finitely many possible entrances and edge patterns; finite-energy property of Bernoulli percolation gives positive probability for at least one such pattern. Translation invariance then gives a common positive trifurcation probability .
Here is the counting contradiction in detail. For a finite box , contract each open component outside that touches to a boundary terminal. In each cluster, the resulting incidence graph is finite and connected. Every trifurcation in separates at least three sets of terminals, since each infinite branch must leave . A minimal subtree joining all terminals must therefore contain that graph vertex with degree of a vertex at least three. Its leaves are terminals. The tree identity bounds the number of those branching graph vertices by the terminal count. Different terminals are represented by different exterior graph neighbours of . Thus the trifurcation boundary-counting lemma givesFor , the two sizes are and . Letting contradicts . Therefore almost surely, with the same conclusion for the translated planar dual graph.
Now prove absence of percolation at by Zhang's argument. Suppose instead that . Almost surely an infinite primal cluster exists, and self-duality gives an infinite dual cluster as well. An infinite connected subgraph of this locally finite lattice contains a graph ray, by the König infinity lemma. Expanding square boxes meet the infinite percolation clusters with probability tending to one.
For , let mean that an open graph ray takes an outward edge through the indicated side and subsequently uses graph vertices outside . The union occurs whenever the box meets an infinite percolation cluster: take the last exit of an infinite graph ray from the finite box. Conversely an exterior arm supplies an infinite percolation cluster meeting its boundary. Quarter-turn symmetry makes the four probabilities equal. Their complements are decreasing events, so the square-root trick for positively associated events givesFor the planar dual graph use the box with boundary coordinates and define its exterior side-arm events in the same way. This box also has quarter-turn symmetry and meets the dual infinite percolation cluster with probability tending to one. Thus each dual side has an infinite exterior arm with probability tending to one. Primal outward edges cross this dual-box contour on the corresponding sides; their remaining graph vertices stay outside it. A union bound makes the simultaneous event of primal north/south arms and dual east/west arms have positive probability for a sufficiently large box.
The four arms alternate around the contour. Open all edges with both endpoints in , leaving all outward and exterior edges intact. This joins the two primal entrance points and preserves all four exterior arms. Finite-energy property of Bernoulli percolation keeps the event's probability positive. The primal north and south arms are now connected through the box. The two dual arms must lie in different infinite dual clusters. To see the separation, a hypothetical finite dual graph path joining the east and west arms cannot enter the dual-box interior: its boundary-crossing and interior edges cross primal edges that were just opened. Erase its loops and cut it at successive hits of the contour. A resulting exterior dual crosscut, together with the corresponding contour arc, encloses one of the two intervening primal entrance points. The infinite primal graph ray from that point would have to cross a dual-open edge, which is impossible. This is the planar separation used in the alternating arms argument at the self-dual percolation parameter. It contradicts uniqueness of the infinite dual cluster. HenceFinally suppose . At the permitted exponential decay of subcritical percolation would supply with . Use the rectangle with graph vertices , and let be its left-to-right open crossing. Planar duality for rectangle crossings identifies its complement with a dual top-to-bottom crossing of a rectangle of width and height . Rotation and translation give the same crossing law; side edges at the entrance and exit boundaries are irrelevant. Thus the exact self-dual rectangle crossing probability isBut a crossing has some starting graph vertex on its -vertex left side connected to distance . The union bound and exponential decay of subcritical percolation imply , a contradiction. ThereforeNo Russo-Seymour-Welsh theorem or continuity assertion for is being used, and critical uniqueness was proved rather than inferred from the supercritical hypothesis.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 214 2 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Use the nearest-neighbour lattice graph with graph vertex set : an unordered pair is an edge precisely when . A bond configuration is ; under the product measure , its edge coordinates are independent Bernoulli distribution with success probability . Edges with coordinate one are open. The open cluster is the connected component of a graph reachable from the origin through open edges.
Define the percolation probability and percolation critical probability byEquivalently, . The monotone coupling of Bernoulli percolation proves the equivalence: assign independent uniform distribution to the edges and open at parameter when . Connection events and then increase with . For , and , so the defining set is nonempty. The definition does not settle what happens at .
By translation invariance all roots have the same probability. Since the graph vertex set is countable, implies that no graph vertex lies in an infinite percolation cluster almost surely. Conversely a positive root probability gives positive probability of an infinite percolation cluster, and translation ergodicity of Bernoulli percolation then makes existence an almost-sure event. In question 2(b), means .
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!
Intro to OurBigBook
. Source. We have two killer features:
- 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-calculusArticles 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/derivativeVideo 2. OurBigBook Web topics demo. Source. - 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.
- to OurBigBook.com to get awesome multi-user features like topics and likes
- as HTML files to a static website, which you can host yourself for free on many external providers like GitHub Pages, and remain in full control
Figure 2. You can publish local OurBigBook lightweight markup files to either OurBigBook.com or as a static website.Figure 3. Visual Studio Code extension installation.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. - Infinitely deep tables of contents:
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





