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 2019 iii Paper 216 1 b Solution by
Codex 0 2026-10-03
The posterior mean of the number infected isRun 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
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 216 1 a Solution by
Codex 0 2026-10-03
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 isConsequently the posterior distribution isThis 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
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 215 4 b Solution by
Codex 0 2026-10-03
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 215 4 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
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 congestionThen the Canonical paths comparison theorem gives the Poincaré inequalityfor 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
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 215 3 i Solution by
Codex 0 2026-10-03
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 givesbecause every disagreeing vertex is counted in exactly neighbor sets. ThereforeThe coupling inequality for total variation and give
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 215 2 c Solution by
Codex 0 2026-10-03
Take and start from the lower endpoint. The stationary distribution of this birth-death chain satisfies detailed balance withso 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 isAt 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
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 215 2 b Solution by
Codex 0 2026-10-03
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 displacementStandard exponential concentration for sums of bounded independent increments shows that for every fixed the one-coordinate coupling time satisfiesAll other initial states lie between the extremal copies. Coupling the coordinates independently and using the union bound givesbecause . The coupling inequality for total variation therefore gives
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 215 2 a Solution by
Codex 0 2026-10-03
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 isUniformly 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 givesThe chi-squared divergence bound on total variation distance now yieldsuniformly 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
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 214 4 c Solution by
Codex 0 2026-10-03
Exhaust by finite boxes and let be a uniform spanning tree of . Every finite tree satisfies the handshaking lemma, soChoose 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 givesThe four edges incident to have equal inclusion probability by the rotations and reflections of the square lattice. If that common probability is , then . Consequentlyfor every edge by translation invariance.
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 214 4 b Solution by
Codex 0 2026-10-03
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.
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 214 4 a Solution by
Codex 0 2026-10-03
A spanning tree of a finite connected graph is a connected acyclic subgraph containing every vertex. A uniform spanning tree is a random spanning tree chosen uniformly from the finite set of all spanning trees of .
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 214 3 c Solution by
Codex 0 2026-10-03
Let be the voltage with , , and harmonic values at every other vertex. For any other admissible , write , where . Its discrete Dirichlet energy expands asDiscrete summation by parts turns the cross term intobecause 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
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 214 3 b Solution by
Codex 0 2026-10-03
Put and let . The conductance-hitting identity for an electrical network iswhere 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
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 214 3 a Solution by
Codex 0 2026-10-03
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:
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 214 2 b Solution by
Codex 0 2026-10-03
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 thatUse 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
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 214 2 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Because , choose a finite set with . Let exceed the -distance from to every endpoint of an edge in , and putOn 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 giveIteration 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!
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





