key: cord-0669235-ycvistsz authors: Grimmett, Geoffrey R. title: Selected problems in probability theory date: 2022-05-15 journal: nan DOI: nan sha: 346f58b7f080d322407784174c9498aed652c1a6 doc_id: 669235 cord_uid: ycvistsz This celebratory article contains a personal and idiosyncratic selection of a few open problems in discrete probability theory. These include certain well known questions concerning Lorentz scatterers and self-avoiding walks, and also some problems of percolation-type. The author hopes the reader will find something to leaven winter evenings, and perhaps even a project for the longer term. Probability has been a source of many tantalising problems over the centuries, of which the St Petersburg paradox, Fermat's problem of the points, and Bertrand's random triangles feature still in introductory courses. Whereas the conceptual problems of the past are now largely resolved, contemporary questions arise frequently where the intuitive apparatus of sub-fields collide. Many prominent problems are to be found at the conjunction of probability and discrete geometry. This short and idiosyncratic article summarises some of these. This account is personal and incomplete, and is to be viewed as a complete review of nothing. The bibliography is not intended to be complete, and apologies are extended to those whose work has been omitted. The questions highlighted here vary from the intriguing to the profound. Whereas some may seem like puzzles with limited consequence, others will require new machinery and may have far-reaching implications. The problem of counting self-avoiding walks is introduced in Section 2, with emphasis on the existence of critical exponents and the scaling limit in two dimensions, followed by a fundamental counting problem on a random percolation cluster. Section 3 is devoted to Lorentz scatterers and the Ehrenfest wind/tree model, followed by Poissonian mirrors in two dimensions, and finally Manhattan pinball. Two wellknown conjectures concerning product measures are presented in Section 4, namely the bunkbed conjecture and the negative association of a uniform spanning forest. Section 5 is concerned with the identification of criticality for the randomly oriented square lattice. In the final Section 6, we present two basic problems associated with a model for a dynamic spatial epidemic, provoked in part by Covid-19. 2. Self-avoiding walks 2.1. Origins. Self-avoiding walks were first introduced in the chemical theory of polymerisation (see [10, 32] ), and their properties have received much attention since from mathematicians and physicists (see, for example, [5, 14, 30] ). A path in an infinite graph G = (V, E) is called self-avoiding if no vertex is visited more than once. Fix a vertex v ∈ V , and let Σ n (v) be the set of n-step self-avoiding walks (SAWs) starting at v. The principal combinatorial problem is to determine how the cardinality σ n (v) := |Σ n (v)| grows as n → ∞, and the complementary probability problem is to establish properties of the shape of a randomly selected member of Σ n (v). Progress has been striking but limited. Asymptotics. It is now regarded as elementary that the so-called connective constant κ = κ(G), given by exists when G is quasi-transitive, and is independent of the choice of v. Thus, in this case The correction term is much harder to understand. We shall not make precise the concept of a d-dimensional lattice, but for definiteness the reader may concentrate on the hypercubic lattice Z d . See [5, 30] for further discussion and results so far, and the papers [19, 20] of Hara and Slade when G = Z d with d ≥ 5, for which case they prove that γ = 1. Of particular interest is the case when G = H, the hexagonal lattice. By a beautiful exact calculation that verifies an earlier conjecture of Nienhuis [31] based in conformal field theory, Duminil-Copin and Smirnov [8] proved that The proof reveals a discrete holomorphic function that is highly suggestive of a connection to a Schramm-Loewner evolution (see [23] ), namely the following. Question 2.2. Does a uniformly distributed n-step SAW from the origin of H converge weakly, when suitably rescaled, to the Schramm-Loewner random curve SLE 8/3 ? Progress on this question should come hand-in-hand with a calculation of the associated critical exponent γ = 43 32 . Gwynne and Miller [17] have proved the corresponding weak limit in the universe of Liouville quantum gravity. 2.3. Self-avoiding walks in a random environment. How does the sequence (σ n ) behave when the underlying graph G is random? For concreteness, we consider here the infinite cluster I of bond percolation on Z 2 with edge-density p > 1 2 (see [11] ). Question 2.3. Does the limit µ(v) := lim n→∞ σ n (v) 1/n exist a.s., and satisfy µ(v) = µ(w) a.s. on the event {v, w ∈ I}? NE NW Related discussion, including of the issue of deciding when µ(v) = pµ(Z 2 ) a.s. on the event {v ∈ I}, may be found in papers of Lacoin [24, 25] . The easier SAW problem on (deterministic) weighted graphs is considered in [16] . 3.1. Background. The scattering problem of Lorentz [27] gives rise to the following general question. Scatterers are distributed randomly about R d . Light is shone from the origin in a given direction, and is subjected to reflection at the scatterers. Under what circumstances is the light ray: (i) bounded, (ii) unbounded, (iii) diffusive? While certain special cases are understood, the general question remains open. The problems mentioned here are concerned with aperiodic distributions of scatterers; the periodic case is rather easier. Ehrenfest wind/tree model. The following notorious problem on the square lattice Z 2 has resisted solution for many years. Let p ∈ [0, 1]. At each vertex of Z 2 is placed a mirror with probability p, or alternatively nothing. Mirrors are plane and two-sided. Each mirror is designated a north-east (NE) mirror with probability 1 2 , or alternatively a north-west (NW) mirror. The states of different vertices are independent. The meanings of the mirrors are illustrated in Figure 3 .1. Light is shone from the origin in a given compass direction, say north, and it is reflected off the surface of any mirror encountered. The problem is to decide whether or not the light ray is unbounded. that there is no percolation when p = 1, one obtains the less trivial fact that θ(1) = 0 (see [11] ). Very little more is known rigorously about the answer to Question 3.1. Here is version of the wind/tree model in the two-dimensional continuum R 2 . Let Π be a rate-1 Poisson process in R 2 . Let > 0, and let µ be a probability measure on [0, π). We possess an infinity of two-sided, plane mirrors of length , and we centre one at each point in Π; the inclination to the horizontal of each mirror is random with law µ, and different mirrors have independent inclinations. Think of a mirror as being a randomly positioned, closed line segment of length , and let M denote the union of these segments. We call µ degenerate if it is concentrated on a single atom, and shall assume µ is non-degenerate. See Figure 3 .3. Light is shone from the origin at an angle α to the horizontal. Let I α be the indicator function of the event that the light ray is unbounded. Some convention is adopted for the zero-probability event that the light strikes an intersection of two or more mirrors. We may assume that the origin 0 does not lie in M . Let C be the component of R 2 \ M containing 0, and let {0 ↔ ∞} be the event that C is unbounded. It is a standard result of so-called needle percolation (see [36] ) that there exists c = c (µ) ∈ (0, ∞) such that (Here and later, the subscript µ keeps track of the choice of µ.) Obviously, on the event that 0 ∞, we have that I α = 0 for all α. Therefore, P µ (I α = 1 for some α) = 0, > c . The converse issue is much harder and largely open. Let Q be the set of probability measures µ that are non-degenerate and have support in the rational angles πQ. Suppose µ ∈ Q and 0 < < c (µ). Harris [21] has shown the striking fact that, P µ -a.s. on the event that 0 ↔ ∞, we have that I α = 1 for (Lebesgue) almost every α. This leads to a deterministic question. Let K be the set of mirror configurations for which 0 ↔ ∞ but I α = 0 for all α. Harris's theorem implies in effect that P µ (K) = 0 when µ ∈ Q and = c (µ). Question 3.2(c) hints at the possibility that P µ (K) = 0 when µ is the uniform measure on [0, π) and < (µ). Here is a final question concerning diffusivity. Let µ ∈ Q, and denote by X α (t) the position at time t of the light ray that leaves the origin at angle α. Question 3.4. Is it the case that, on the event I α , X α (·) is diffusive? That is, the limit σ 2 := lim t→∞ t −1 var(X α (t)) exists in (0, ∞), and, when normalized, X α (t) is asymptotically normally distributed. Related work on Lorentz models in the so-called Boltzmann-Grad limit may be found in [28, 29] Consider bond percolation with density q on the diagonal lattice. Along each open edge of Z 2 we place a two-sided plane mirror. Light is shone from the origin along a given one of the two admissible directions, and it is reflected by any mirror that it encounters (such reflections are automatically consistent with the Manhattan orientations). Let θ(q) be the probability that the light ray is unbounded. It follows as in Section 3.2 that θ(q) = 0 for q ≥ 1 2 , and it has been proved by Li in [26] that there exists > 0 such that θ(q) = 0 when q > 1 2 − . The proof uses the method of enhancements; see [1] , [11, Sect. 3.3 ]. 4.1. Bunkbed inequality. The mysterious 'bunkbed' inequality was posed by Kasteleyn around 1985 (see [6, Rem. 5] , and also [18] ). Of its various flavours, we select the following. Let G = (V, E) be a finite simple graph. From G we construct two copies denoted G 1 = (V 1 , E 1 ) and G 2 = (V 2 , E 2 ). For v ∈ V we write v i for the copy of v lying in V i . We now attach G 1 and G 2 by adding edges v 1 , v 2 for each v ∈ V . This new graph is denoted G, and it may be considered as the product graph G × K 2 where K 2 is the complete graph on two vertices (that is, an edge). We may think of the G i as being 'horizontal' and the extra edges as being 'vertical'. Each edge of G is declared open with probability p, independently of the states of other edges. Write P p for the appropriate product measure. For two vertices u i , v j of G, we write {u i ↔ v j } for the event that there exists a u i /v j path using only open edges. There is uncertainty over whether this was the exact conjecture of Kasteleyn. For example, it is suggested in [22] (and perhaps elsewhere) that Kasteleyn may have made the stronger conjecture that the inequality holds even after conditioning on the set T of open vertical edges. Some special cases of the bunkbed conjecture have been proved (see the references in [22] , and more recently [35] ), but the general question remains open. Negative correlation. Our next problem is quite longstanding (see [33] ) and remains mysterious. In a nutshell it is to prove that the uniform random forest measure (USF) has a property of negative association. Let G = (V, E) be a finite graph which, for simplicity, we assume has neither loops nor multiple edges. A subset F ⊆ E is called a forest if (V, F ) has no cycles. Let F be the set of all forests in G and let Φ be a random forest chosen uniformly from F. We call Φ edge-negatively associated if (4.1) P(e, f ∈ Φ) ≤ P(e ∈ Φ)P(f ∈ Φ), e, f ∈ E, e = f. For all graphs G, the random forest Φ is edge-negatively associated. One may formulate various forms of negative dependence, amongst which the edge-negative association of (4.1) is quite weak. One may conjecture that Φ has a stronger variety of such dependence. Further discussion may be found in [13, Sec. 3.9] and [33] . Experimental evidence for Conjecture 4.2 is quite strong. A similar conjecture may be made for uniform measure on the set of F ⊆ E such that (V, F ) is connected (abbreviated to UCS). In contrast, uniform spanning tree (UST) is well understood via the Kirchhoff theory of electrical networks, and further by [9] . USF, UCS, and UST are special cases of the so-called random-cluster measure with cluster-weighting factor q satisfying q < 1 (see [13, Sects 1.5, 3.9] ). In recent work, [3, 4] , the percolative properties of the weighted random forest (or 'arboreal gas') on Z d have been explored. It turns out that there is a phase transition if and only if d ≥ 3. The following percolation-type problem remains open. Consider the square lattice Z 2 and let p ∈ [0, 1]. Each horizontal edge is oriented rightward with probability p, and otherwise leftward. Each vertical edge is oriented upward with probability p, and otherwise downward. Write Z 2 for the ensuing randomly oriented network. Let θ(p) denote the probability that the origin 0 is the endpoint of an infinite path of Z 2 that is oriented away from 0. The challenge is to determine for which p it is the case that θ(p) > 0. It is elementary that θ(0) = 1, and that θ(p) = θ(1 − p). It is less obvious that θ( 1 2 ) = 0 (see [11, 1st edn]), which is proved via a coupling with bond percolation. By a comparison with oriented percolation, we have that θ(p) > 0 if p > p c , where p c is the critical point of oriented percolation on Z 2 ; it is not difficult to deduce by the enhancement method (see [1] , [11, Sect. 3.3] ) that there exists p ∈ ( 1 2 , p c ) such that θ(p) > 0 when p > p . It is believed that p c ∼ 0.64, and proved that p c < 0.6735. It is shown in [12] that, for all p, Z 2 is either critical or supercritical in the following sense: if any small positive density of oriented edges is added at random, then there is a strictly positive probability that the origin is the endpoint of an infinite self-avoiding oriented path in the resulting graph. The recent pandemic has inspired a number of mathematical problems, including the following stochastic model (see [15] ). Particles are placed at time 0 at the points of a rate-1 Poisson process in R d , where d ≥ 1. Each particle diffuses around R d according to a Brownian motion, independently of other particles. At any given time, each particle is in one of the states S (susceptible), I (infected), R (removed/dead). At time 0 there exists a unique particle in state I, and all others are in state S. The infection/removal rules are as follows. (a) If an infected particle comes within distance 1 of a susceptible particle, the latter particle is infected. (b) An infected particle remains infected for a period of time having the exponential distribution with parameter α, and is then removed. We call this the 'diffusion model'. Survival is said to occur if, with a strictly positive probability, infinitely many particle are ultimately infected. It is proved in [15] that, when d ≥ 1 and α is sufficiently large, survival does not occur. The following two questions (amongst others) are left open. Question 6.1. (i) When d = 1, could it be that there is no survival for any α > 0? (ii) When d ≥ 2, does survival occur for sufficiently small α > 0? In a variant of this problem termed the 'delayed diffusion model', a much fuller picture is known. Suppose, instead of the above, a particle moves only when it is infected; susceptible particles are stationary. The answers to Question 6.1(i, ii) are then no and yes, respectively, and indeed (when d ≥ 2) there exists a critical value α c (d) ∈ (0, ∞) of α marking the onset of survival. The key difference between the two systems is that the latter model has a property of monotonicity that is lacking in the former. The delayed diffusion model is a continuous space/time cousin of the discrete-time 'frog model' of [2] (see also [34] ), with the addition with removal. Further relevant references may be found in [15] . Strict monotonicity of critical points in percolation and ferromagnetic models Phase transition for the frog model Random spanning forests and hyperbolic symmetry Lectures on self-avoiding walks, Probability and Statistical Physics in Two and More Dimensions A correlation inequality for connection events in percolation Quantum network models and classical localization problems The connective constant of the honeycomb lattice equals 2 + √ 2 Balanced matroids Principles of Polymer Chemistry Infinite paths in randomly oriented lattices The Random-Cluster Model Self-avoiding walks and connective constants, Sojourns in Probability Theory and Statistical Physics Brownian snails with removal: epidemics in diffusing populations Weighted self-avoiding walks Convergence of the self-avoiding walk on random quadrangulations to SLE 8/3 on 8/3-Liouville quantum gravity Probability on bunkbed graphs The lace expansion for self-avoiding walk in five or more dimensions Self-avoiding walk in five or more dimensions. I. The critical behaviour Nontrivial phase transition in a continuum mirror model The bunkbed conjecture holds in the p ↑ 1 limit Schramm-Loewner Evolution Existence of a non-averaging regime for the self-avoiding walk on a high-dimensional infinite percolation cluster Non-coincidence of quenched and annealed connective constants on the supercritical planar percolation cluster On the Manhattan pinball problem The motion of electrons in metallic bodies Invariance principle for the random Lorentz gasbeyond the Boltzmann-Grad limit Invariance principle for the random wind-tree process Self-Avoiding Walks Exact critical points and critical exponents of O(n) models in two dimensions Statistical treatment of polymer solutions at infinite dilution Towards a theory of negative dependence Asymptotic behavior of a stochastic growth process associated with a system of interacting branching random walks Bunkbed conjecture for complete bipartite graphs and related classes of graphs Percolation of Poisson sticks on the plane Duality, statistical mechanics and random matrices, Current Developments in Mathematics Cambridge CB3 0WB, UK Email address: grg@statslab.cam.ac