Discrete Probability (10frg155)

Objectives

The purpose of this group, which calls itself the "Institute for Elementary Studies" (IES), is to bring together talent from different fields (particularly combinatorics, probability, computer science and statistical physics) to solve problems and pursue new ideas in discrete probability. Since its creation in 1992, the group has opened up new fields (e.g. dynamic percolation, invariant allocations) and produced numerous results in Markov chains, quasi-random processes, physical models, and randomized algorithms.

The meeting will focus on topics in geometric probability and probabilistic number theory. Random processes on geometric structures have many current physical and algorithmic applications. In these models, a large number of simple components behave according to simple probabilistic rules, each interacting with its neighbours in some underlying geometric space (such as Euclidean or hyperbolic space, or a graph). From these local interactions, remarkable global structures can emerge. Such models have been studied for decades by mathematical physicists who focussed on the case where the underlying network was a Euclidean lattice. Some of the concepts from the physics literature (phase transitions, critical exponents, self-organization) retain their importance far beyond the domain where they were created, while other geometric concepts (isoperimetric inequalities, flows) become relevant. Of particular interest are processes that are invariant in distribution under symmetries of the underlying space.

Below is a selection of particular areas and open questions to be considered at this meeting.

Invariant processes and coupling. Given an invariant process, we ask whether it is possible to construct from it a further process having some specified property, either as a deterministic function of the original process, or using some additional randomness. In most cases the difficulty lies in constructing the process in an invariant manner, i.e. respecting symmetries of the space. For example, the allocation problem for a point process is to partition space into cells of equal volume, with each cell assigned to a point of the process. Several invariant allocations have constructed in recent years, but some of their properties are not yet fully understood, for example concerning the distribution of diameters of the cells. As another example, if red and blue points occur as independent Poisson processes in the plane, does there exist a translation-invariant matching between the red and blue points such that the line segments connecting matched pairs do not cross?

Shifts of finite type and finitary factors. Suppose that the vertices of a graph are assigned random colours via a local function of some process of independent random vertex labels. That is, the colour of vertex v is determined by a rule which examines the labels within a random distance R of v, and the same rule applies at all vertices. If the resulting process must satisfy some system of local constraints, what behaviours are possible for the distribution of R? On the Euclidean lattice, examples are known where the optimal R has power law tail, and where the tail decays according to a tower of exponentials, but it is not known for example whether exponential decay is possible.

Interacting random walks. While random walks on graphs are comparatively well understood, much less is known once several random walks interact in simple ways. For example, suppose that whenever two random walks visit the same site they either coalesce, or annihilate. How long does it take until a single particle remains? In the annihilating walkers model, any configuration with an odd number of walkers will eventually reduce to a single walker. On a circle, is it true that the configuration that takes the maximal time (in expectation) to achieve this has three equally spaced particles?

Probabilistic number theory. Most factoring algorithms in use today are randomized, and their rigorous analysis is a source of highly relevant problems. An example arises in Pomerance's sieving model (Proc. ICM 1994). Numbers $X_j$ are chosen IID uniformly from $1...N$. These are then represented as vectors over the two element field, where the p-th coordinate is the parity of the number of times the prime p occurs as a factor of $X_j$. The problem is to estimate the time until there is a modulo-2 linear dependence among the vectors. This requires sophisticated number-theoretic estimates, for instance on the number of numbers $k<x$ with no prime factors greater than y (as in e.g. Croot, Granville, Pemantle and Tetali 2008; Ford, Ann. Math. 2008). Of particular interest in the further analysis of seiving algorithms would be refinement of such estimates when k is restricted to the quadratic residues modulo N.

Questions such as the foregoing constitute the number-theoretic part of the necessary technology. On the probabilistic end, further successful analysis will rely on formulation and analysis of tractable probability models. For example, the best results on the basic sieving model above were proved by showing that the vectors converge weakly to a Poisson process. For sharper results, one must rule out phenomena such as the occurrence of the zero vector, which would form a trivial linear dependence. The p-th column contains a one with probability asymptotic to $1/p$, whence an independent model predicts the zero vector with probability exp $(- sum_{p < N} 1/p) = (log N)^{-1 + o(1)}$. This is too big. The independent model is asymptotically correct for finitely many columns at a time, but not for large deviations such as the all-zero vector. Replacing the independent model with one that is still tractable but predicts the correct stopping time is the likely key to sharpening threshold results for sieving analysis. For example, it is an open question whether conditioning the independent model on the sum of log p over the columns where ones occur will yield the right answer. Another possibility is to use the sampling algorithm of Arratia, Barbour and Tavare (Notices AMS 1997).

The IES has met four times before (in the California Sierras, in Door County, Wisconsin, in Harsa, Sweden, and at BIRS (03frg003)). The meetings have consisted of informal discussions (no transparencies or laptops) and intense periods of problem-solving. The 2003 meeting was unanimously agreed to be the best so far, with the facilities and setting of BIRS being a perfect fit. The membership and focus change somewhat from one meeting to the next; we have tried to keep the group fresh with new ideas and participants. We have an additional list of strong researchers to invite if more than a few of those listed decline.

Some examples of new areas of study initiated at past meetings are as follows. Dynamic percolation was originally invented and studied at an IES meeting, and has become a flourishing subject boasting many publications, including: Schramm & Steif (Annals of Math., to appear). A similar BIRS focussed research group (not an IES meeting, but involving many of the same people) led to substantial progress on random sorting networks, including: Angel, Holroyd, Romik & Virag (Advances in Math., 2007). Many other results on Markov chains, physical models, and randomized algorithms were proved at, or as an immediate result of, other IES meetings.