The simple random walk covers all points of Z_n^2 in 4n^2(log n)^2/pi steps

You need to know: Addition and subtraction modulo n, limits, basic probability theory, notation P[.] for probability of something.

Background: Let ${\mathbb Z}_n^2$ be the set of points $x=(a,b)$ such that $0\leq a < n$ and $0\leq b < n$ are integers. Let $x_k, k=0,1,2,\dots$ be a (random) sequence of points in ${\mathbb Z}_n^2$ , such that, if $x_k=(a_k,b_k)$ , then $x_{k+1}$ can be $(a_k+1,b_k)$ , or $(a_k-1,b_k)$ , or $(a_k,b_k+1)$ , or $(a_k,b_k-1)$ with equal chances, where the addition and subtraction are modulo n. Let $T_n$ be the smallest integer m such that for every $x\in{\mathbb Z}_n^2$ we have $x=x_i$ for some $0\leq i \leq m$ .

The Theorem: On 26th July 2001, Yuval Peres, Jay Rosen, and Ofer Zeitouni submitted to the arxiv and Annals of Mathematics a paper in which they proved, among other results, that for any $\epsilon>0$ , $\lim\limits_{n\to \infty}P\left[\left|\frac{T_n}{(n \log n)^2} - \frac{4}{\pi}\right|>\epsilon\right] = 0.$

Short context: Random walk is a simple model for various applications, it can be used to approximate stock prices, model the movement of a molecule in a liquid or gas, etc. The time it takes for a random walk to cover all points in a certain set has been intensively studied and has numerous applications. The problem of estimating the cover time $T_n$ for ${\mathbb Z}_n^2$ was asked by Wilf in 1989 who called it “the white screen problem”. In the same year, Aldous conjectured that $T_n/(n \log n)^2$ converges to $4/\pi$ . The Theorem confirms this conjecture.

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 4.8 of this book for an accessible description of the Theorem.

Go to the list of all theorems

Any two components of the USF in Z^d are adjacent a.s. if d is at most 8

You need to know: Finite and infinite graph, tree, forest, path, connected component, subgraph, induced subgraph. Basic probability theory, select an object uniformly at random, an event happening almost surely (a.s.). Notation $\left \lfloor{x}\right \rfloor$ for the largest integer not exceeding real number x.

Background: Let ${\mathbb Z}^d$ be (infinite) graph with vertices $x=(x_1, \dots, x_d)$ with integer coordinates, where x and y are connected by an edge if $\sum_{i=1}^d|x_i-y_i|=1$ . Let ${\mathbb Z}_n^d$ be the (finite, induced) subgraph of ${\mathbb Z}^d$ consisting on vertices $x=(x_1, \dots, x_d)$ with $|x_i|\leq n$ for all i. A spanning tree on ${\mathbb Z}_n^d$ is a (non-induced) subgraph of ${\mathbb Z}_n^d$ which (i) is a tree, and (ii) contains at least 1 edge incident to each vertex of ${\mathbb Z}_n^d$ . Let $H_n^d$ be a spanning tree on ${\mathbb Z}_n^d$ selected uniformly at random. For any set C of edges in ${\mathbb Z}^d$ , let $P_n(C)$ be the probability that all these edges are included in $H_n^d$ , and let $P(C)=\lim\limits_{n\to\infty} P_n(C)$ . A (random) subgraph $H^d$ of ${\mathbb Z}^d$ such that any set C of edges of ${\mathbb Z}^d$ is included into $H^d$ with probability $P(C)$ is called the uniform spanning forest (USF) on ${\mathbb Z}^d$ . For $x,y \in {\mathbb Z}^d$ , let $N(x, y)$ be the minimum number of edges outside the USF in a path joining x and y in ${\mathbb Z}^d$ .

The Theorem: On 19th July 2001, Itai Benjamini, Harry Kesten, Yuval Peres, and Oded Schramm submitted to arxiv a paper in which they proved that, almost surely, $\max\limits_{x,y\in {\mathbb Z}^d}N(x,y) = \left \lfloor{\frac{d-1}{4}}\right \rfloor$ .

Short context: The USF was introduced by Pemantle in 1991 as a way to choose a spanning forest in ${\mathbb Z}^d$ uniformly at random. Pemantle proved that, for $d\leq 4$ (but not for $d\geq 5$ ), the USF is connected (and thus is a spanning tree) almost surely. In other words, $N(x,y)=0$ for all $x,y \in {\mathbb Z}^d$ if and only if $d\leq 4$ . The Theorem computes $\max\limits_{x,y\in {\mathbb Z}^d}N(x,y)$ in all dimensions. In particular, $N(x,y) \leq 1$ a.s. for all $x,y \in {\mathbb Z}^d$ if and only if $d\leq 8$ .

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 4.9 of this book for an accessible description of the Theorem.

Go to the list of all theorems

Largest eigenvalue of X’X, with x_ij i.i.d. normal, approaches the Tracy–Widom law

You need to know: Limits, derivatives, integrals, independent random variables, standard normal distribution $N(0,1)$ , cumulative distribution function (cdf), convergence in the distribution, matrices, transpose $X'$ of matrix $X$ , matrix multiplication, eigenvalues of a matrix.

Background: Let $A(x)=\frac{1}{\pi}\int_0^\infty \cos\left(\frac{t^3}{3}+xt\right) dt$ , and $q(x)$ be the (unique) function such that $q''(x)=xq(x)+2q^3(x)$ and $\lim\limits_{x\to+\infty}\frac{q(x)}{A(x)}=1$ . The probability distribution with cdf $F(s) = \exp\left(-\frac{1}{2}\int_s^\infty (q(x) + (x-s)q^2(x)) dx\right), s \in {\mathbb R}$ is called the Tracy–Widom law of order 1.

Let X be an $n \times p$ matrix whose entries are independent and follow $N(0,1)$ . Let $l_{np}$ be the largest eigenvalue of matrix $X'X$ . Let $\mu_{np} = \left(\sqrt{n-1}+\sqrt{p}\right)^2$ and $\sigma_{np} = \left(\sqrt{n-1}+\sqrt{p}\right)\left(\frac{1}{\sqrt{n-1}}+\frac{1}{\sqrt{p}}\right)^{1/3}$ .

The Theorem: In August 2000, Iain Johnstone submitted to the Annals of Statistics a paper in which he proved that, if $n=ak$ , $p=bk$ , where $a\geq b$ are constants and $k\to\infty$ , then $\frac{l_{np}-\mu_{np}}{\sigma_{np}}$ converges in the distribution to the Tracy–Widom law of order 1.

Short context: Understanding the distribution of eigenvalues of random matrices is the problem of fundamental importance both in mathematics and in many of its applications. In a series of papers in 1993-1996, Tracy and Widom proved that the maximal eigenvalue of random square matrices (in several important models of randomness), appropriately scaled, converges to an explicit distribution which have got the name Tracy–Widom law. The Theorem generalises this result to rectangular matrices.

Links: The original paper can be found here.

Go to the list of all theorems

Random polynomial of degree n has no real zeros with probability n^(-b+o(1))

You need to know: Polynomials, basic probability: random variables, distribution, independence, sequence of i.i.d. (independent identically distributed) random variables, expectation (or mean), variance. You also need $o(1)$ notation for context section.

Background: We say that random variable X possess finite moments of all orders if expectation of $|X|^k$ is finite for all $k>0$ . Let $a_0, a_1, a_2, \dots$ be a sequence of zero-mean, unit-variance, i.i.d. random variables possessing finite moments of all orders. Let $f_n(x)=\sum\limits_{i=0}^{n-1} a_i x^i$ , and let $P_n$ be the probability that $f_n(x) \neq 0, \,\, \forall x \in{\mathbb R}$ .

The Theorem: On 30th May 2000, Amir Dembo, Bjorn Poonen, Qi-Man Shao, and Ofer Zeitouni submitted to the Journal of the AMS a paper in which they proved that $\lim\limits_{n\to \infty}\frac{\log P_{2n+1}}{\log(2n+1)}=-b$ , where $b>0$ is a constant.

Short context: The study of real zeros of random polynomials has a long history, is mentioned by Waring in as early 1782, systematically studied by Littlewood and
Offord in 1938, and then by many others. In 1999, Poonen and Stoll, motivated by applications in arithmetic geometry, conjectured that $P_n=n^{-b+o(1)}$ for some $b>0$ . The Theorem confirms this prediction. The authors also prove that $0.4 \leq b \leq 2$ and predict that $b \approx 0.76 \pm 0.03$ .

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

The intersection exponent for two simple random walks on the plane is 5/8

You need to know: Integer lattice ${\mathbb Z}^2$ , vertices of ${\mathbb Z}^2$ , basic probability theory, simple random walk on ${\mathbb Z}^2$ .

Background: For a simple random walk S on ${\mathbb Z}^2$ and integer $k\geq 0$ , denote $S[0,k]$ to be the (random) set of vertices S visited after k steps.

The Theorem: On 27th March 2000, Gregory Lawler, Oded Schramm and Wendelin Werner submitted to Acta Mathematica a paper in which they proved, among other results, that there exists a constant $c>0$ such that inequality $c^{-1}k^{-5/8} \leq P[S[0,k]\cap S'[0,k] = \emptyset] \leq ck^{-5/8}$ holds for all $k\geq 1$ , where S and S’ are two independent simple random walks that start from neighbouring vertices in ${\mathbb Z}^2$ .

Short context: If $P[S[0,k]\cap S'[0,k] = \emptyset]$ decays proportional to $k^{-\gamma}$ for some constant $\gamma>0$ , then $\gamma$ is called the intersection exponent. In 1988 Duplantier and Kwon used ideas from theoretical physics to predicts that, for two simple random walks on the plane, $\gamma=5/8$ . The Theorem provides a rigorous mathematical proof of this prediction.

Links: Free arxiv version of the paper is here, journal version is here.

Go to the list of all theorems

There are three nonempty phases for percolation on planar hyperbolic graph

You need to know: Graph, infinite graph, planar graph, connected components of a graph, basic probability theory, almost sure convergence, bijection, infimum, notation |A| for the number of elements in any finite set A.

Background: An automorphism of graph $G=(V,E)$ is a bijection $\sigma: V \to V$ , such that pair of vertices $(u,v)$ is an edge if and only if $(\sigma(u), \sigma(v))$ is an edge. A (finite or infinite) graph G is called transitive if, for every 2 vertices u and v of G, there is an automorphism $\sigma$ such that $\sigma(u)=v$ . An infinite transitive graph $G=(V,E)$ has one end if, after deletion of any finite set of vertices (and the corresponding edges), the remaining graph has exactly one infinite connected component. A graph $G=(V,E)$ is amenable if, for every $\epsilon>0$ , there is a finite set $A \subset V$ , such that $|\partial A| \leq \epsilon |A|$ , where $\partial A$ is the set of vertices outside A connected by edge to at least one vertex in A. Transitive, nonamenable, planar graph with one end are known as “planar hyperbolic graphs”.

Let $p\in[0,1]$ . The Bernoulli(p) bond percolation on $G=(V,E)$ is a subgraph of G to which each edge of G is included independently with probability p. The Bernoulli(p) site percolation on $G=(V,E)$ is a subgraph of G to which each vertex of G is included independently with probability p, and each edge $(u,v)$ is included if and only if both vertices u and v are. For given G, let $p_c(G)$ be the infimum of all $p\in[0,1]$ such that the Bernoulli(p) (bond or site) percolation on G has an infinite connected component almost surely, and let $p_u(G)$ be the infimum of all p for which this infinite connected component is unique almost surely.

The Theorem: On 30th December 1999, Itai Benjamini and Oded Schramm submitted to the Journal of the AMS a paper in which they proved, among other results, that for any planar hyperbolic graph G we have $0 < p_c(G) < p_u(G) < 1$ , for Bernoulli bond or site percolation on G.

Short context: The Theorem proves that, as p increases from 0 to 1, the Bernoulli(p) percolation on planar hyperbolic graphs passes through three distinct nonempty phases. In the first phase, $p\in(0,p_c]$ , there are no infinite connected components; in the second phase, $p\in(p_c, p_u)$ , there are infinitely many of them; and in the third phase, $p\in[p_u, 1)$ , there is a unique infinite connected component.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

Moderate deviations probability for the Wiener Sausage volume decays fast

You need to know: d-dimensional Euclidean space ${\mathbb R}^d$ , volume in ${\mathbb R}^d$ , limits, basic probability theory, stochastic processes, Wiener process in ${\mathbb R}^d$

Background: Let $W(t)$ be standard Wiener process in ${\mathbb R}^d$ . For $a>0$ and $t \geq 0$ , let $W_a(t) = \{ x \in {\mathbb R}^d \,|\,\exists s \in [0,t] : \rho(x,W(s)) \leq a \}$ , where $\rho$ is the distance in ${\mathbb R}^d$ . $W_a(t)$ is known as Wiener sausage. Let $|W_a(t)|$ denote its (d-dimensional) volume. It is known that $E|W_a(t)| \approx 2\pi t/\ln t$ for $d=2$ , $E|W_a(t)| \approx 2\pi a t$ for $d=3$ , and $E|W_a(t)| \approx K_{a,d} t$ for $d \geq 3$ , where $K_{a,d}>0$ is a constant depending on a and d, $E$ denotes mathematical expectation, and by $f(t) \approx g(t)$ we mean $\lim\limits_{t \to \infty}\frac{f(t)}{g(t)}=1$ .

The Theorem: On 5th July 1999, Michiel van den Berg, Erwin Bolthausen and Frank den Hollander submitted to Annals of Mathematics a paper in which they proved that for every $a>0$ , $b \in (0,K_{a,d})$ , $\lim\limits_{t\to\infty}\frac{1}{t^{(d-2)/d}}\ln P(|W^a(t)|\leq bt) = -C_{a,d,b}, \, d \geq 3,$ where P denotes the probability, and $C_{a,d,b}>0$ is some constant depending on a, d, and b. Similarly, for every $a>0$ , $b \in (0,2\pi)$ , $\lim\limits_{t\to\infty}\frac{1}{\ln t}\ln P(|W^a(t)|\leq bt/\ln t) = -C_b, \, d=2.$

Short context: Let $a$ be fixed and denote $V_t=|W^a(t)|$ . The Theorem implies that, for large t, $P(V_t\leq bE[V_t])$ (which is called moderate deviation probability) decays as $t^{-C}$ for $d=2$ , and as $\text{exp}\left(-C t^{(d-2)/d}\right)$ for $d \geq 3$ . Earlier, similar fast decays were known only for probabilities of the form $P(V_t \leq f(t) E[V_t])$ for some $f(t)$ such that $\lim\limits_{t \to \infty} f(t) = 0$ . These are known as probabilities of large deviations.

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 1.1 of this book for an accessible description of the Theorem.

Go to the list of all theorems

The Erdős-Taylor conjecture on the most visited point of simple plane random walk is true

You need to know: Coordinate plane, vectors, natural logarithm $\log$ , basic probability theory, almost sure convergence.

Background: Let $X_1, X_2, \dots, X_n, \dots$ be a sequence of independent vector-valued random variables, each taking values (1,0), (0,1), (-1,0) and (0,-1) with equal probabilities. Sequence $S_n = \sum\limits_{k=1}^n X_k$ , $n=1,2,\dots$ is called simple random walk in ${\mathbb Z}^2$ . For each pair of integers (x,y) and positive integer n, let $T(n,x,y)$ be the number of positive integers $k \leq n$ such that $S_k=(x,y)$ . Finally, let $T^*(n) = \max_{x,y} T(n,x,y)$ be the number of times that random walk visits the most visited point.

The Theorem: On 10th May 1999, Amir Dembo, Yuval Peres, Jay Rosen, and Ofer Zeitouni submitted to Acta Mathematica a paper in which they proved, among other results, that $\frac{T^*(n)}{(\log n)^2}$ converges to $\frac{1}{\pi}$ almost surely as $n \to \infty$ .

Short context: The question “How many times does the simple plane random walk revisit the most frequently visited point in the first n steps?” was asked by Erdős and Taylor in 1960. They proved that the limit $\lim\limits_{n\to\infty}\frac{T^*(n)}{(\log n)^2}$ , if it exists, is between $\frac{1}{4\pi}$ and $\frac{1}{\pi}$ . They further conjectured that the limit actually exists and is equal to $\frac{1}{\pi}$ almost surely. The Theorem confirms this conjecture.

Links: The original paper is here.

Go to the list of all theorems