Skorohod Representation Theorem

Posted on October 13, 2014 by dominicyeo

Continuing the theme of revising theory in the convergence of random processes that I shouldn’t have forgotten so rapidly, today we consider the Skorohod Representation Theorem. Recall from the standard discussion of the different modes of convergence of random variables that almost sure convergence is among the strongest since it implies convergence in probability and thus convergence in distribution. (But not convergence in $L_1$ . For example, take U uniform on [0,1], and $X_n=n\mathbf{1}_{\{U<\frac{1}{n}\}}$ .)

Almost sure convergence is therefore in some sense the most useful form of convergence to have. However, it comes with a strong prerequisite, that the random variables be defined on the same probability space, which is not required for convergence in distribution. Indeed, one can set up weak versions of convergence in distribution which do not even require the convergents to be random variables. The Skorohod representation theorem gives a partial converse to this result. It states some conditions under which random variables which converge in distribution can be coupled on some larger probability space to obtain almost sure convergence.

Skorohod’s original proof dealt with convergence of distributions defined on complete, separable metric spaces (Polish spaces). The version discussed here is from Chapter 5 of Billingsley [1], and assumes the limiting distribution has separable support. More recent authors have considered stronger convergence conditions (convergence in total variation or Wasserstein distance, for example) with weaker topological requirements, and convergence of random variables defined in non-metrizable spaces.

Theorem (Skorohod representation theorem): Suppose that distributions $P_n\Rightarrow P$ , where P is a distribution with separable support. Then we can define a probability space $(\Omega,\mathcal{F},\mathbb{P})$ and random variables $X,(X_n)_{n\ge 1}$ on this space such that the laws of $X,X_n$ are $P,P_n$ respectively and $X_n(\omega)\rightarrow X(\omega)$ for all $\omega\in\Omega$ .

NB. We are proving ‘sure convergence’ rather than merely almost sure convergence! It is not surprising that this is possible, since changing the value of all the $X_n$ s on a set with measure zero doesn’t affect the conditions for convergence in distribution.

Applications: Before going through the Billingsley proof, we consider one simple application of this result. Let S be a separable metric space containing the support of X, and g a continuous function $S\rightarrow S'$ . Then

$X_n\stackrel{a.s.}{\rightarrow}X\quad\Rightarrow\quad g(X_n)\stackrel{a.s.}{\rightarrow}g(X).$

So, by applying the Skorohod representation theorem once, and the result that almost sure convergence implies convergence in distribution, we have shown that

$X_n\stackrel{d}{\rightarrow}X\quad\Rightarrow\quad g(X_n)\stackrel{d}{\rightarrow}g(X),$

subject to these conditions on the space supporting X. And we have avoided the need to be careful about exactly which class of functions determine convergence in distribution, as would be required for a direct argument.

Proof (from [1]): Unsurprisingly, the idea is to construct realisations of the $(X_n)$ from a realisation of X. We take X, and a partition of the support of X into small measurable sets, chosen so that the probability of lying in a particular set is almost the same for $X_n$ as for X, for large n. Then, the $X_n$ are constructed so that for large n, with limitingly high probability $X_n$ lies in the same small set as X.

Constructing the partition is the first step. For each $x\in S:=\mathrm{supp}(X)$ , there must be some radius $\frac{\epsilon}{4}<r_x<\frac{\epsilon}{2}$ such that $P(\partial B(x,r_x)=0$ . This is where we use separability. Since every point in the space is within $\frac{\epsilon}{4}$ of some element of a countable sequence of elements of the space, we can take a countable subset of these open balls $B(x,r_x)$ which cover the space. Furthermore, we can take a finite subset of the balls which cover all of the space apart from a set of measure at most $\epsilon$ . We want the sets to be disjoint, and we can achieve this by removing the intersections inductively in the obvious way. We end up with a collection $B_0,B_1,\ldots,B_k$ , where $B_0$ is the leftover space, such that

$P(B_0)<\epsilon$
$P(\partial B_i)=0,\quad i=0,1,\ldots,k$
$\mathrm{diam}(B_i)<\epsilon,\quad i=1\ldots,k$ .

Now suppose for each m, we take such a partition $B^m_0,B^m_1,\ldots,B^m_{k_m}$ , for which $\epsilon_m=\frac{1}{2^m}$ . Unsurprisingly, this scaling of $\epsilon$ is chosen so as to use Borel-Cantelli at the end. Then, from convergence in distribution, there exists an integer $N_m$ such that for $n\ge N_m$ , we have

$P_n(B^m_i)\ge (1-\epsilon_m)P(B^m_i),\quad i=0,1,\ldots,k_m.$ (*)

Now, for $N_m\le n <N_{m+1}$ , for each $B^m_i$ with non-zero probability under P, take $Y_{n,i}$ to be independent random variables with law $P_n(\cdot | B^m_i)$ equal to the restriction onto the set. Now take $\xi\sim U[0,1]$ independent of everything so far. Now we make concrete the heuristic for constructing $X_n$ from X. We define:

$X_n=\sum_{i=0}^{k_m}\mathbf{1}_{\{\xi\le 1-\epsilon_m, X\in B^m_i\}} Y_{n,i} + \mathbf{1}_{\{\xi>1-\epsilon_m\}}Z_n.$

We haven’t defined $Z_n$ yet. But, from (*), there is a unique distribution such that taking $Z_n$ to be independent of everything so far, with this distribution, we have $\mathcal{L}(X_n)=P_n$ . Note that by iteratively defining random variables which are independent of everything previously defined, our resulting probability space $\Omega$ will be a large product space.

Note that $\xi$ controls whether the $X_n$ follow the law we have good control over, and we also want to avoid the set $B^m_0$ . So define $E_m:=\{X\not \in B^m_0, \xi\le 1-\epsilon_m\}$ . Then, $P(E_m)<2\epsilon_m=2^{-(m-1)}$ , and so by Borel-Cantelli, with probability 1, $E_m$ holds for all m larger than some threshold. Let us call this $\liminf_m E_m=: E$ , and on this event E, we have by definition $X_n \rightarrow X$ . So we have almost sure convergence. But we can easily convert this to sure convergence by removing all $\omega\in\Omega$ for which $\xi(\omega)=1$ and setting $X_n\equiv X$ on $E^c$ , as this does not affect the distributions.

Omissions:

Obviously, I have omitted the exact construction of the distribution of $Z_n$ . This can be reverse reconstructed very easily, but requires more notation than is ideal for this medium.
It is necessary to remove any sets $B^m_i$ with zero measure under P for the conditioning to make sense. These can be added to $B^m_0$ without changing any of the required conditions.
We haven’t dealt with any $X_n$ for $n<N_1$ .

The natural question to ask is what happens if we remove the restriction that the space be separable. There are indeed counterexamples to the existence of a Skorohod representation. The clearest example I’ve found so far is supported on (0,1) with a metric inducing the discrete topology. If time allows, I will explain this construction in a post shortly.

References

[1] – Billingsley – Convergence of Probability Measures, 2nd edition (1999)

More on Testing Dyson’s Conjecture

Ornstein-Uhlenbeck Process

Posted on October 11, 2014 by dominicyeo

A large part of my summer has been spent proving some technical results pertaining to the convergence of some functionals of a critical Frozen Percolation process. This has been worthwhile, but hasn’t involved a large amount of reading around anything in particular, which has probably contributed to the lack of posts in recent months. Perhaps a mixture of that and general laziness?

Anyway, it turns out that the limit of the discrete processes under consideration is the Ornstein-Uhlenbeck process. The sense in which this limit holds (or at least, for now, is conjectured to hold) is something for another article. However, I thought it would be worth writing a bit about this particular process and why it is interesting.

The O-U process is described by the SDE

$dX_t=-\beta (X_t-\mu)dt+\sigma dW_t,$

where W is a standard Brownian motion. We think of $\mu$ as the ‘mean’. The extent to which this behaves as a mean will be discussed shortly. The process is then mean-reverting, in the sense that the drift is directed against deviations of the process away from this mean. The parameter $\beta$ measures the extent of this mean reversion, while as usual $\sigma$ controls the magnitude of the Brownian noise.

The motivation for considering mean-reverting processes is considerable. One measure of this is how many equations with articles on Wikipedia turn out to be precisely this Ornstein-Uhlenbeck process with different context or notation. In most cases, the motivation arises because Brownian motion is for some reason unsuitable to take as a canonical random process. We will see why the O-U process is somehow the next most canonical choice for a random process.

In physics, it is sometimes unsatisfactory to model the trajectory of a particle with Brownian motion (even though this motivated the name…) as the velocities are undefined (see this post from ages ago), or infinite, depending on your definition of velocity. Using the Ornstein-Uhlenbeck process to model the velocity of a particle is often a satisfactory alternative. It is not unreasonable that there should be a mean velocity, presumably zero. The mean reversion models a frictional force from the underlying medium, while the Brownian noise describes random collisions with similar particles.

In financial applications, the Ornstein-Uhlenbeck model has been applied, apparently under the title of the Vasicek model since the 70s to describe quantities such as interest rates where there is some underlying reason to ban indefinite growth, and require mean reversion. Another setting might be a commodity which, because of external driving factors, has over the relevant time-scale well-defined mean value, around which mean-reverting fluctuations on the observed time-scale can be described. As with other financial models, it is undesirable for a process to take negative values. This can be fixed by taking a positive mean, then setting the volatility to be state dependent, decaying to zero as the state tends to zero, so for small values, the positive drift dominates. I don’t fully understand why patching this aspect is significantly more important than patching any other non-realistic properties of the model, but the resulting SDE is, at least in one particular case where the volatility is $\sqrt{X_t}$ , called the Cox-Ingersoll-Ross model.

Anyway, a mathematical reason to pay particular attention to this Ornstein-Uhlenbeck process is the following. It is the unique family of continuous Markov processes to have a stationary Gaussian distribution. It is the mean-reverting property that is key. There is no chance of Brownian motion having any stationary distribution, let alone a Gaussian one. If this isn’t clear, you can convince yourself by thinking of the stationary distribution of SRW on $\mathbb{Z}$ . Since the process is space-homogeneous, the only stationary measure is the uniform measure.

I want to focus on one particular property of the O-U process, through which some other aspects will be illuminated. If we take $\sigma=\beta$ and let $\beta\rightarrow\infty$ , then the stationary processes converge to white noise.

First though, we should note this is perhaps the easiest SDE to solve explicitly. We consider $X_t e^{\theta t}$ , and applying Ito’s lemma rapidly gives

$X_t=\mu + (X_0-\mu)e^{-\beta t}+\sigma\int_0^t e^{-\beta(t-s)}dW_s.$

W is Gaussian so the distribution of $X_t$ conditional on $X_0=x_0$ is also Gaussian, and since W is centred we can read off the expectation. Applying the Ito isometry then gives the variance. In conclusion:

$X_t\stackrel{d}{=}\mathcal{N}(\mu+(x_0-\mu)e^{-\beta t}, \frac{\sigma^2}{\beta}(1-e^{-2\beta t})).$

In particular, note that the variation has no dependence on $x_0$ . So as t grows to infinity, this converges to $\mathcal{N}(\mu, \frac{\sigma^2}{\beta})$ . This is, unsurprisingly, the stationary distribution of the process.

To address the white noise convergence, we need to consider $\text{Cov}(X_0,X_t)$ in stationarity. Let’s assume WLOG that $\mu=0$ so most of the expectations will vanish. We obtain

$\text{Cov}(X_0,X_t)=\mathbb{E}[X_0X_t]=\mathbb{E}_{x_0}\left[\mathbb{E}[X_t| X_0=x_0]\right]=\mathbb{E}[X_0^2 e^{-\beta t}]= \frac{sigma^2}{2\beta}2^{-\beta t}.$

If we want, the Chapman-Kolmogorov equations work particularly nicely here, and we are able to derive a PDE for the evolution of the density function, though obviously this is very related to the result above. This PDE is known as the Fokker-Planck equation.

So, in particular, when $\sigma=\beta\rightarrow \infty$ , this covariance tends to 0. I’m not purporting that this constitutes a proof that the Ornstein-Uhlenbeck processes converge as processes to white noise. It’s not obvious how to define process convergence, not least because there’s flexibility about how to view white noise as a process. One doesn’t really want to define the value of white noise at a particular time, but you can consider the covariance of integrals of white noise over disjoint intervals as a limit, in similar way to convergence of finite dimensional distributions.

The fact that taking $\beta=0$ gives Brownian motion, and this case gives white noise, intermediate versions of the Ornstein-Uhlenbeck process are sometimes referred to as coloured noise.

Finally, the Ornstein-Uhlenbeck process emerges as the scaling limit of mean-reverting discrete Markov chains, analogous to Brownian motion as the scaling limit of simple random walk. One particularly nice example is the Ehrenfest Urn model. We have two urns, and 2N balls. In each time step one of the 2N balls is chosen uniformly at random, and it is moved to the other urn. So a ball is more likely to be removed from an urn with more than N balls. We can view this as a model for molecules in, say a room, with a slightly porous division between them, eg a small hole. More complicated interface models in higher dimensions lead to fascinating PDEs, such as the famous KPZ equation, which are the subject of much ongoing interest in this area.

This result can be an application of the theory of convergence of Markov chains to SDEs pioneered by Stroock and Varadhan, about which more may follow very soon. In any case, it turns out that the fluctuations in the Ehrenfest Urn model are on the scale of $\sqrt{n}$ , unsurprisingly, and are given by a centred Ornstein-Uhlenbeck process.

Investigating this has reminded me how much I’ve forgotten, or perhaps how little I ever knew, about the technicalities of stochastic processes are their convergence results, so next up will probably be a summary of all the useful definitions and properties for this sort of analysis.

Noise Sensitivity and Influence 1

Posted on September 17, 2014 by dominicyeo

Last week, Simon gave a junior probability seminar about noise sensitivity, and its applications in particular to dynamic critical percolation, so I thought I would write something about this topic based on his talk, and some other sources.

The motivation is critical site percolation on the triangular lattice. This has critical probability $p_c=\frac12$ , and, at this critical probability, almost surely there is no infinite component. But it turns out that there is ‘almost’ an infinite component, in the following technical sense. Dynamical site percolation is given by switching the state of each site according to independent Poisson processes with the same parameter. Then, by construction, if we start at time 0 with the critical probability, then at any fixed time T>0, the configuration is distributed as critical site percolation, and hence almost surely has no infinite component. If, however, we consider the interval of times [0,T], then almost surely there *is* a time when there is an infinite component, and indeed the set of such times has positive Hausdorff dimension.

Definitions

Noise sensitivity addresses the question of how likely some function of a product measure is to change under small perturbations to the state. To give a precise definition, we take a function $f_n:\{0,1\}^n \rightarrow \{0,1\}$ on a product space, with product measure $\mu$ . Then given $\omega\in\Omega_n=\{0,1\}^n$ , define $w^\epsilon$ to be the outcome when each component of $\omega$ is resampled with probability $\epsilon$ . Note that it matters quantitatively whether we consider ‘resampled’ or ‘swapped’, but it doesn’t affect any of the results qualitatively.

Then the noise stability of f at level $\epsilon$ is defined to be

$S_\epsilon(f):=\text{Cov}(f(\omega)f(\omega^\epsilon),$

where $\omega \sim \mu$ . Note that $\omega^\epsilon\sim \mu$ also, but obviously $\omega,\omega^\epsilon$ are not independent. Noise stability measures the magnitude of this dependence. The sequence of functions $(f_n)$ is said to be noise-sensitive if $S_\epsilon(f_n)\rightarrow 0$ as $n\rightarrow\infty$ .

A related concept is influence. This should be viewed as a local version of noise sensitivity, where we consider the likelihood that the function will change as a result of swapping a single fixed component of the state. Perhaps abusing standard notation, define $\omega^{(i)}$ to be the result of swapping the ith component of $\omega$ . Then the influence of the ith coordinate is

$I_i(f) := \mu(\{\omega\in\Omega: f(\omega)\ne f(\omega^{(i)})\}).$

Examples and Results

As in so many models, we are interested in the relationship between the local setting and the global setting. Benjamini, Kalai and Schramm (99) showed that, in the case of the uniform product measure,

$\sum_{i\in[n]} I_i(f_n)^2 \stackrel{n\rightarrow\infty}\rightarrow 0,$

is a sufficient condition for noise-sensitivity of $(f_n)$ . Note the converse is trivially false, by considering the function f(w) that records the parity of the number of 1s in w. Here, the influence is 1, since changing one component by definition changes the value of the function. But the function is noise sensitive, as changing a proportion $\epsilon$ of the components gives a roughly 1/2 probability for large n that the value of the function changes.

However, if we restrict to the class of monotone increasing functions, where changing a 0 to a 1 can never cause f to decrease, the converse is true. Outside the setting of uniform product measure, lots of versions of this theorem are open.

This perhaps seems counter-intuitive. After all, we would expect high global sensitivity to follow from high local sensitivity. I don’t have a good counter-intuition for why this should be true. The original authors themselves describe this as ‘paradoxical’ in [1].

It is natural to ask which component has the largest influence, and in particular whether we can guarantee the existence of a component with influence at least some particular value. Obviously, if the Boolean function is constant, all the influences are zero, and other examples, such as the indicator function of a specific state, will also have very small influences. But such functions also have small variance (under the uniform product measure), so we need to make comparison to this. We can show that

$\text{Var}(f)\le \frac14 \sum_{i\in[n]}I_i(f),$

which is a (discrete) example of a Poincare inequality, where deviations of a function from its mean on a particular space in $L^p$ are bounded in terms of the derivative of the function. Here, influence is a discrete analogue of derivative.

Proof: We observe first that if $\mathbb{P}(f(w)=1)=p$ , then $\mathbb{E}[f(w)]=p$ , and

$\text{Var}(f)=p(1-p)^2+(1-p)p^2=p(1-p)=\frac12 \mathbb{P}(f(w)\ne f(\bar w)),$

where $w,\bar w$ are independent realisations of the underlying measure. We move from $w\mapsto \bar w$ one component at a time, examining the influence at each step. Let $v^{(i)}\in \{0,1\}^n$ be given by the first i components of $\bar w$ and the final (n-i) components of $w$ . Then $v^{(0)}=w, v^{(n)}=\bar w$ . Finally, define

$J:=\{i:w_i\ne \bar w_i\}.$

We also say that a state is i-pivotal, if changing the ith component changes the value of the function. Note that if $f(w)\ne f(\bar w)$ , then there exists some i<n such that $f(v^{(i)})\ne f(v^{(i+1)})$ . In particular:

$\{f(w)\ne f(\bar w)\}\subset \{1\in J, v^{(0)}\text{ 1-pivotal}\}\cup$

$\{2\in J, v^{(1)}\text{ 2-pivotal}\}\cup\ldots\cup\{n\in J, v^{(n-1)}\text{ n-pivotal}\}.$

Note now that for any i<n, $v^{(i-1)}$ has uniform product measure on $\Omega$ , since it is an interpolation of sorts between independent realisations of the uniform product measure. Furthermore, since we haven’t interpolated at component i yet, it is independent of the event $\{i \in J\}$ . Thus

$\mathbb{P}(i\in J, v^{(i-1)}\text{ i-pivotal})=\frac12 I_i(f).$

Putting everything together with a union bound gives

$\text{Var}(f)=\frac12 \mathbb{P}(f(w)\ne f(\bar w))\le \frac14 \sum_{i\in [n]}I_i(f),$

as desired.

We might ask when this result is tight. It is certainly not tight if we during the interpolation procedure, the value of f changes lots of times. Since a consequence of this Poincare inequality is that there is some component i such that $I_i(f)\ge \frac{1}{4n}$ , we might conjecture that there is a better lower bound.

It turns out, as shown in [2], that we can add an extra logarithmic factor. Precisely, for some absolute constant c>0, there exists an i such that:

$I_i(f)\ge c \text{Var}(f)\frac{\log n}{n}.$

Indeed, there’s an example which shows that this is optimal. Consider partitioning the n components into groups of size roughly log n – log log n, all in base 2. Then the function is 1, if there exists at least one group, which we call tribes, where all the components are 1. So a particular component is pivotal precisely when all the other components in its tribe are already 1. Thus

$I_i(f)\approx \left(\frac{1}{2}\right)^{\log n - \log\log n}= \frac{\log n}{n}.$

One consequence of this is that by BKS, we learn that the function is noise-sensitive. Is this clear directly? Note that if $w$ contains a tribe of 1s, then with high probability $w^{(\epsilon)}$ for large n, roughly $\epsilon(\log n-\log \log n)$ of these get changed. In particular, it is very unlikely that the same tribe will be a tribe of 1s in $w^\epsilon$ . So heuristically, the presence of a tribe in $w^\epsilon$ feels almost independent of the presence of a tribe in $w$ . But because of the (approximate) symmetry of the setup, it is much easier to work with influences, and use BKS.

I will continue the discussion of the Fourier techniques used to derive some of these results in a new post soon.

References

[1] – Benjamini, Kalai, Schramm (1999) – Noise Sensitivity of Boolean Functions and Applications to Percolation. (arXiv)

[2] – Kahn, Kalai, Linial (1988) – The influence of variables on Boolean Functions. (link)

Garban, Steif – Noise sensitivity of Boolean functions and Percolation. (arXiv) I have borrowed heavily from these excellent notes. The discrete Poincare inequality appears in Section 1.2, with an outline of the solution in Exercise 1.5.

Random Maps 3 – Leaves and Geodesics in BCRT

Posted on August 11, 2014 by dominicyeo

Recall in the previous two posts, we’ve introduced some of the background to maps on various surfaces. In particular, we’ve introduced the remarkable Cori-Vauquelin-Schaeffer bijection which maps between plane trees labelled with uniform increments and quadrangulations of the sphere, up to some careful fiddling around with rooting and pointing an edge.

We are interested in the case where we choose uniformly a large element from these classes. We want to derive a scaling limit for the uniform planar quadrangulation, and we hope that we will be able to carry some properties of the scaling limit of the labelled trees, which may well be simpler, across the CVS bijection. It is convenient that the vertices of the plane tree become the vertices of the quadrangulation. We are looking to find some sort of metric limit, in the Gromov-Hausdorff sense, and so it will remain to deduce exactly how to use the labelling obtained from the tree to gain information about distances in the (limiting) quadrangulation.

Of course, all of this relies on the fact that there is a nice limit for the ordered plane trees in the first place. Unsurprisingly, it turns out that this is Aldous’s Brownian continuum random tree. The easiest way to see this is to consider the contour process of the ordered plane tree. This is chosen uniformly at random from the set of paths from (0,0) to (2n,0) with increments of size {-1,1} and which stay non-negative. It is thus precisely a simple random walk started at (0,0) conditioned to hit (2n,0) and to be non-negative. Since SRW suitably rescaled converges to Brownian motion, it is unsurprising (but not totally trivial) that this conditioned object converges to a Brownian excursion.

The Brownian excursion can be viewed as a continuous analogue of the contour process for the BCRT, but it is more natural to consider this convergence in the Gromov-Hausdorff topology. In this setting, we say that for a large value of n, the tree is ‘roughly isometric’ to the BCRT in distribution. Here, roughly isometric means the two metric spaces can be embedded isometrically into a common metric space such that they are close together, now in the sense of Hausdorff distance.

At this point, it is worth thinking about this interpretation of the BCRT. We have previously considered this as the scaling limit of a uniformly chosen Cayley tree, that is any unrooted tree on n labelled vertices. Essentially, we are now specifying that the BCRT can carry extra information, namely a root, and geometric information about the order of branches. The root is uncontroversial. Canonically, the root of the BCRT will be at the point associated with time 0 in the driving Brownian excursion. However, we can easily check that the distribution of a uniform rooted plane tree is invariant under re-rooting, and so any argument we have for convergence of the rooted trees to the BCRT will work with the root in a different place. Applying something like a tower law, we conclude that the convergence works when the root is chosen uniformly in the limit.

One potential problem to be discussed is what it means to choose a point uniformly in the limit. We have two possible approaches. One is to consider Lebesgue measure on any path in the BCRT, and glue these together. However, we have a uniform stick-breaking construction of the BCRT, and one consequence of the construction is that the total length of sticks required is infinite, so this won’t work.

The other option is to project Lebesgue measure on [0,1] via the same map that sends points on the Brownian excursion to points in the tree. Note that the so-called real tree is constructed from the excursion by identifying points s and t where f(s)=f(t), and f(x)>f(s) for x in (s,t). But then we might wonder whether this can really be said to be ‘uniform’, since different points in the BCRT will have a different number of pre-images in [0,1]. In fact though, it turns out that in this sense, projected-Leb[0,1]-almost all the points in the BCRT are leaves.

To prove this, naturally we first need to define a leaf, in the setting of these continuum trees. The degree of a vertex is an idea we might keep in mind, but we can’t use this, as we don’t have vertices any more. However, we have a continuous analogue of degree, given by counting the number of connected components remaining after removing a vertex. In particular, we can define the set of leaves as

$\mathcal{L}(\mathcal{T}):=\{x\in\mathcal{T}:\mathcal{T}\backslash \{x\}\text{ is connected}\}.$

We will give a sketch proof of this result about leaves shortly. First, we clarify some notation, and consider properties of geodesics (shortest-length paths) in the tree.

Define $\check{f}(u,v):=\min_{x\in[u\wedge v,u\vee v]} f(x)$ to be the minimum value attained by f between u and v. Consider the value x at which this minimum is attained. Then, projecting onto the tree, p(x) is the ‘most recent common ancestor’ of points u and v. We can make this a bit more precise by considering geodesics in the tree starting at the root. Analogous to the unique path property in a discrete tree, in this continuous setting there is a unique path from the root to any given point, along which the height is strictly increasing. This is not surprising. It follows from one of the definitions of a real tree that the length of the path from p(0) to p(s) should be f(s), and so there is a unique isometric embedding of [0,f(s)] into $\mathcal{T}_f$ which starts at 0 and ends at p(s). Anyway, under this $p(\check{f}(s,t))$ gives the point at which the geodesics from p(s) to p(0) and from p(t) to p(0) meet.

Furthermore, we can now describe the distance in the tree between p(s) and p(t). This is given by

$d_f(s,t):= f(s)+f(t)-2\check{f}(s,t),$

and with the geodesic picture, it is easy to see why. Consider the point x at which $\check{f}(s,t)$ achieves the minimum. As we have said, this lies on the geodesics from p(s) to 0 and p(t) to 0, and paths between points are unique, so removing point x disconnects p(s) and p(t) in the tree. So we need to concatenate the geodesic from p(s) to p(x) and from p(x) to p(t). But these are subsets of the two geodesics discussed, and their respective lengths are $f(s)-\check{f}(s,t)$ and $f(t)-\check{f}(s,t)$ .

We can now give a sketch proof the result that almost all the support of $\lambda_f$ , the projection on Lebesgue measure from [0,1] onto $\mathcal{T}_{f}$ is on $\mathcal{T}(\mathcal{T}_f)$ .

Given $s,t\in[0,1]$ , suppose we are removing p(s), and this separates p(t) from the root, which is canonically p(0). Without loss of generality, take t>s. Now suppose that $\check{f}(s,t)<f(s)$ , and that, as before, this infimum is attained at $x\in[s,t]$ . Then the geodesic from p(0) to p(t) will pass through p(x), but not through p(s), so in particular, removing p(s) cannot disconnect p(t) from the root.

Thus, p(s) is not a leaf if and only if there exists some small window [s,t] such that $f(s)\le f(x),\;\forall x\in[s,t]$ . By Blumenthal’s 0-1 law, for fixed x, this happens with probability 0 if f is Brownian motion. Here, f is not Brownian motion, but a Brownian excursion with length 1. However, Blumenthal’s 0-1 law depends on the instantaneous behaviour after time s, ie the sigma field $\mathcal{F}_s^+$ . So, for $s\in(0,1)$ , the value of a Brownian at time 1 is independent of this sigma field, so if we imagine Brownian excursion as a ‘conditioned’ Brownian motion, this conditioning should have no effect on the conclusion of this corollary to Blumenthal’s 0-1 law.

This is not a formal argument, but it sketches why with probability 1, p(s) is a leaf for each $s\in(0,1)$ , from which the result follows.

Random Maps 2 – The Schaeffer Bijection

Posted on August 3, 2014 by dominicyeo

As indicated at the end of the previous post, our aim is to find a natural bijection between the set of pointed, rooted quadrangulations with n faces, and some set of objects based on decorating rooted plane trees with n edges in some fashion. Unlike our previous example, the construction of this bijection is definitely not trivial. It seems like a foolish ambition to explain this without several pictures, so I’m going to focus on some aspects of the analysis which I found challenging, rather than the construction itself.

Anyway, we don’t yet know what the extended set of trees should be. We need an extra factor of $3^n$ , so it is natural to consider adding some sort of labelling of the tree, where for each non-root vertex in turn there are three options. So, given a rooted tree T, we label the vertices such that the root has label 0, and if a parent vertex has label k, any offspring has label k-1, k or k+1. Such a labelling is called admissable, and $\mathbb{T}_n$ is the set of rooted plane trees with n edges and an admissable labelling.

We now demonstrate how to construct an element of $\mathcal{Q}_n$ from an element of $\mathbb{T}_n$ . Various authors had considered this problem to various extents, and so what follows is known as the Cori-Vauquelin-Schaeffer bijection, at least in this course.

Consider a contour exploration of the tree. That is, start out at the root and at all times take first-edge you encounter going clockwise from your current direction. When you arrive at a leaf, you will indeed therefore immediately retrace your most recent step. The key property is that you traverse each edge exactly twice, and so we may think of the tree as having 2n oriented edges. It is more useful to think about corners. A corner is the directed arc (WLOG clockwise) between adjacent edges at a vertex. There is a natural bijection between corners and directed edges, by looking anti-clockwise from the tail of the edge. So the contour process explored the directed edges in some order, and hence explores the corners of the tree. One thing I found confusing initially was switching between considering vertices and corners. I feel in retrospect that the only reason we need the vertices themselves is to induce the labelling onto the corners. These are the only thing we will use in the construction.

As we trace out the contour process, naturally we see different labels. We define the successor of a corner with label k to be the next corner seen in the contour process (taken modulo 2n if necessary) with label k-1. Note that any corner on a vertex with minimal label will not have a successor. To counter this, we add a new vertex, suggestively called $v_*$ , with a single corner (ie no edges yet) and denote this corner to be the successor of the corners in the original tree with minimal label.

To construct our quadrangulation, we simply join up every corner with its successor corner. Note that if you are thinking of the successor of a corner as a vertex (rather than as a corner) you will get in trouble here, as it might be several ways to draw this arc.

The red arcs and vertex v* are added to form the quadrangulation. Note the blue angles indicate the three corners around the vertex labelled -1.

It is not obvious that it is possible to do this so that the arcs do not overlap. However, by considering the label process as you explore via the contour process, it becomes clear that you can discount the possibility of any overlaps one by one. This applies equally to pairs of new arcs overlapping, as well as new arcs overlapping with edges of the original tree. In any case, we remove the edges of the original tree to obtain the quadrangulation.

Note that when you move from any corner of a vertex with label k to its successor, then to the successor of its successor and so on, the labels are decreasing, so eventually you must end up at a corner with minimal label, and hence at $v_*$ . We conclude that the graph of arcs is connected. It remains to show that it is a quadrangulation.

This is rather fiddly to do without a diagram. Note first that whenever we have a directed edge in the tree going from label k to label k-1, then this edge essentially becomes an arc of the quadrangulation. We show that the edge oriented in the other direction, called say e, induces three further arcs of a quadrangle. So e goes from label k-1 to k. Consider the corners before and following e in the contour exploration, which is a corner around the vertex with label k. The successor of the corner after e is a corner with label k-1, and this has a successor with label k-2. By construction, this must also be the successor of the corner before e. Why? Well as we traverse the contour beyond e, the first appearance of label k-1 must happen before the first appearance of label k-2, as the increments can only be in {-1,0,1}. This gives us the three further arcs. Note also that the 2-colouring of the quadrangulation is given by the parity of the tree-labelling.

I was bothered about what happens if two vertices with label k-1 are in fact the same. This would happen if, for example, the vertex labelled k is a leaf. Then, at least two of the corners around the single vertex with label k-1 have the same corner as successor. A naïve attempt at drawing the resulting arcs did not give a quadrangle. The key observation is that you have to draw the arcs in the direction of the contour process. So in this case, the arc from the corner before edge e will loop all the way around the vertex with label k, so it contains the other two relevant arcs on its way to the vertex with label k-2, giving us the ‘pacman’ quadrangle discussed earlier.

The other case we have to check is when our base edge joins two vertices with label k. Then the other two vertices of the face will have label k-1. This is similar to the above, and slightly easier.

As a preliminary to checking that we can invert this construction, we observe that the vertices of the quadrangulation are the vertices of the original tree plus $v_*$ , and furthermore, the labels in the tree are given by the graph distance from $v_*$ in the quadrangulation, with a constant added uniformly so that the root vertex has label 0.

At this point, we observe that in the construction, we didn’t specify how to choose the rooted edge of the quadrangulation. Canonically, we take it to be the arc between the first corner of the root in the contour process, and its successor. However, we can orient it in either direction, giving us the extra factor of 2 we were looking for.

Returning to the inverse, it is clear what to do when we see a quadrangle corresponding to the second case above – namely put an edge between the two vertices with label k. In the case where the face has labels {k,k-1,k-1,k-2} it is less obvious. Note though that by starting at the first corner of the root, which is identified by the rooted edge in the quadrangulation, we can recover the contour process from the arcs of the quadrangulation, and the labels. So when we see such a face, we can use this information to choose which of the (k-1)-labelled vertices to join to the vertex with label k.

Anyway, now we are convinced that this bijection works, the next stage is to apply it to gain extra information about a uniformly-chosen large quadrangulation. We can view the vertices as being those of a large uniform plane tree, and the labels as given by a random walk along this large tree. We might expect to see this labelling structure converge to something that looks like Brownian motion indexed by a Brownian continuum random tree, in a sense to be made more precise. And the labelling is not merely a decoration in the quadrangulation, since it specifies the distance to the identified point $v_*$ . In particular, this gives a bound on the distance between any two vertices in the quadrangulation, eg two vertices chosen uniformly at random. In fact, by looking more carefully at the scaling limit of the uniform tree’s contour process, we can say rather more than that.

Random Maps 1 – Towards the Schaeffer Bijection

Posted on July 29, 2014 by dominicyeo

I have spent the past ten days in Saint Flour, an inaccessible but picturesque town in the rolling hills of Cantal, in the middle of France, and venue for perhaps the most notable summer school in probability. My highlight has been the course ‘Aspects of Random Maps’ delivered by Gregory Miermont, and I thought I should write a few posts about points of interest encountered during the lectures and private study.

A map is an embedding of a connected graph onto a surface. We typically do not care about the nature of this embedding up to homeomorphisms of the surface which preserve orientations of the map. One advantage for doing this is that the set of maps now might be countable, and the set of maps with n edges might be finite. This can be proved by considering a map to be obtained by glueing together polygonal faces. Some potential glueings are impossible, and some are equivalent, but for a fixed number of edges, the number of such sets of polygons and a possible glueing is finite. In fact we can be much more precise than this about how to describe precisely the legal glueing through a triple of permutations, but I won’t discuss this here.

I haven’t yet given a complete definition of a map. We want a typical large map, that is a map with a large number of vertices and edges, to be topologically roughly the same as the surface it is embedded into. In particular, the map needs to encode the geometric features of the surface. So a small triangle on the surface of a torus should not be considered a map. To rigorise this, we demand that any face of a map should be a topological disc, in particular, it should be simply connected. Since the torus itself is not simply connected, this excludes our triangle example. Note a single vertex on a torus is also excluded.

Although it goes against the usual order of definitions, it might be helpful to think of a map as an embedding which satisfies Euler’s formula: V – E + F = 2 -2g, where g is the genus of the surface. For a connected planar graph, induction is on the number of edges and vertices is the typical way to prove this result. The inductive step works the same on a more general surface, but it is less clear what the base case should be. Another consequence of the definition is that we should work on the sphere rather than the plane. From now on, this is our surface of interest.

We begin by considering $\mathcal{M}_n$ to be the family of rooted plane maps with n edges. The root is a distinguished oriented edge. Our aim is to count the size of this set.

Before doing this, we digress onto the topic of rooted plane trees. Note that any (rooted) tree in the classical sense is planar, but in a rooted plane tree, we also specify the geometric ordering of the offspring. For example, if the root has two offspring, of which one has precisely one offspring and the other has none, we consider these as two separate cases.

So now, if we denote by $a_k$ the number of plane trees with k edges, we can define a generating function via $A(z):=\sum_{k\ge 0} a_k z^k$ . If the root vertex v has no offspring, this gives one possibility corresponding to k=0. Otherwise, there is a well-defined left-most offspring of the root, called u. Then u and its descendents form a plane tree, and v and its descendents apart from those through u also form a plane tree. So after accounting for the edge between u and v, we obtain

$A(z)=1+zA(z)^2,$

whenever A(z) is defined. We now can apply whichever is our favourite method of showing that this is the generating function of the Catalan numbers, $a_k=\frac{1}{k+1}\binom{2k}{k}$ .

There is a more complicated version of this generating function argument due to Tutte that allows us to enumerate $\mathcal{M}_n$ . It is convenient to work with a second variable in the generating function that encodes the degree of the root face. The resulting equation of generating functions is less well-known but using the Lagrange inversion formula gives the explicit expression

$|\mathcal{M}_n|=\frac{2}{n+2}\cdot \frac{3^n}{n+1}\binom{2n}{n}.$

Although there are extra terms, this motivates seeking a bijection between maps, and some version of rooted plane trees, perhaps decorated with some extra information. As in many cases, this will turn out to be possible. The bijection we end up with will not just help us enumerate the maps, but will also allow us to control a lot more information about distances in the map, which will be particularly useful when we try to take limits.

The first observation is that given a map, we can construct a dual map, by placing fresh vertices somewhere in the middle of each face, and joining a pair of these if the corresponding faces in the original graph share an edge.

Alternatively, we can place the same fresh vertices in the middle of each face, then join each new vertex to an original vertex, if that original vertex lies on the face corresponding to the new vertex. If you focus in on an original edge, it is clear that it is now surrounded by a ‘diamond’ (if you’ve drawn the diagram in a natural way) of new edges. Removing the original edges thus leaves us with a quadrangulation. This procedure is called the ‘trivial bijection’ between $\mathcal{M}_n$ and $\mathcal{Q}_n$ , the family of rooted quadrangulations with n faces. Note that the root in such a quadrangulation is an identified directed edge, rather than a vertex. We haven’t yet specified how to describe the root of the resulting quadrangulation. It suffices to take the first new edge which lies clockwise of the root edge in the original graph, seen from the ‘tail’ of the root, which is of course oriented.

In this, and the bijections which follow, the natural questions to ask are: a) is the inverse obvious? and b) what happens to self-loops and isthmuses? Here, the inverse really is obvious. Any quadrangulation is bipartite, hence two-colourable, so we need to fix one colour and join the two vertices of that colour within each face to recover the original graph. The root tells us which colour we need to take. As for the second question, first we should say that an isthmus is an edge which has the same face on both sides. This causes no problems in this particular bijection. For the self-loops, we get a sort of Pacman-like quadrangle, with two ‘outer-edges’ between the same two vertices, and an edge between one of the outer vertices and some internal vertex. This edge contributes twice to the degree of the face.

The upshot of this is that for a simple enumeration, it suffices to prove that $|\mathcal{Q}_n|=\frac{2}{n+2}\cdot \frac{3^n}{n+1}\binom{2n}{n}$ . This may not look like we have achieved much, but we can now apply Euler’s formula to any quadrangulation in this set to deduce that the number of vertices present is n+2. If we consider the set $\mathcal{Q}_n^*$ , where now we identify a particular vertex $v_*$ in the quadrangulation, it suffices to prove that $|\mathcal{Q}_n^*|=2.3^n \cdot a_n$ , where $a_n$ is the nth Catalan number as before. Now we have the most efficient setup to look for a bijection with some type of decorated plane tree as discussed before.

IMO 2014 – Part Four – Coordination and Close

Posted on July 14, 2014 by dominicyeo

Thursday 10th July

At last year’s IMO, a discussion arose concerning which of the seven members of the UK delegation at lunch was most likely to be the deputy leader. I placed rather low down the list. Despite the fresh-faced nature of the 2014 team, I’m taking no chances this year and now have a fairly full beard. However, today we have the first of our meetings with the coordinators to agree the UK team’s marks, and it may be necessary for Geoff and I to play good cop/bad cop. I prefer to play bad cop and feel this is a role best approached clean-shaven. In any case, there is a clash of timings so after signing for a vector of zeros on Q6, I end up playing solo cop on Q2.

We start with Frank, who has tried to prove something more general in one place, which is unfortunately false, but would be true in the special case. He then uses this in the second part of the problem, referencing the false bit, but using only the bit which is actually true. His habit of putting bold circles round sections he thinks are dubious is heart-warmingly honest, but I wonder whether it might have made more sense to use the time at the end of the exam to un-dubify them, rather than operating a series of nested post scripts? In any case, rather by an accident of the markscheme, we are offered 4, which is what I was hoping for, but definitely more than I was expecting. We also agree a 7 on Warren’s solution, and after coordinator Robert dramatically waves a diagram of a common counterexample to Harvey’s final argument at me, we agree a 5 for him.

The others are more tricky. Joe has done both parts of the problem fundamentally correctly, but has written down the final answer incorrectly. Since this step is genuinely trivial, it seems harsh to dock it a mark. Especially since the coordinators didn’t notice until we pointed it out to them. Hopefully this should be squashed overnight, though ultimately it is likely that several students will have done this, so consistency is all one can ask for. In any case, I regret my cavalier assurance straight after the exam. Freddie is offered 7, but also has a tiny mistake that they have not noticed. In fairness to them, this is very hard to spot, with the construction of an extra point in an extremal argument failing only in the case (2,2) out of $[1,n]\times [1,n]$ , but they insist it has to be a 6. Coordinator Santiago reminds me that a proof is not a proof if it contains a mistake. This is a true statement. We will reconvene tomorrow.

The team have got back from their own excursion to Cape Point and seem to have enjoyed themselves, even the extended musical lunch. It would be nice to be able to give them more information about their marks, but they will have to bide their time. Perhaps in preparation for IMO 2015 in Chiang Mai, we return for a fifth visit to the Thai Cafe in Rondenbosch where both sides give a fuller exposition of their activities during the day. Afterwards, I see the team appropriating one of the giant Google cubes that have appeared round the site. They reassure me that they are still taking the medication for kleptomania, and in fact they intend to use it to distribute the UKMT playing cards as gifts to the other contestants.

Friday 11th July

Again I spend much of the night wading through slicks of combinatorial vomit, now including Q5, perhaps ambitiously described as Number Theory. After Geoff gets exactly what we want on Q1 and Q4, I’m raring to go for an early fourth session on Q2. The French leaders have a student in a similar position to Joe and have threatened to take his case to the jury. They get the extra mark, and in the spirit of Agincourt and Trafalgar I’m only too happy to coast in on their wave. Gabriel, from whom there were plans to drop two separate marks for the same mistake, gets his 6, and after successfully countering yesterday’s counterexample, so does Harvey. Freddie’s appears to be still under discussion, and I find myself saying “With respect…” several times, before it transpires that actually they are trying to offer 7, which of course we take. While it’s easy to criticise, I should emphasise that this question a) was an absolute nightmare; b) had a harsh markscheme, but this was certainly consistently enforced; and c) ultimately if the students hadn’t made mistakes none of this would have been relevant. Our coordinators knew the scripts well, were reasonable and fair, and I can only imagine how difficult it must be to do it all over again in Uzbek.

Question 5 proceeds much more smoothly, starting with our observation that Warren’s script looks identical to the official solution, including the location of the page break. He and Harvey get 7s with no real debate, and after a brief examination of the Chinese characters in Frank’s rough it turns out we are in agreement on the other four marks too. This was a very well-constructed markscheme for part marks. It is sensible to be both generous and sub-additive and it felt like there was not much room for ambiguity, though I’m glad we didn’t have any almost-complete solutions.

We are finished rather earlier than expected, with a nice bunch of scores between 20 and 28, and a team score of 142 looking likely to place the UK in the high teens. This is a strong team performance. The ‘easy’ (of course, this is relative) questions 1 and 4 have been dispatched and we have scored well compared to other similar countries on the medium questions. This is what we train for, and it is excellent to see it bringing rewards. Our younger students will have more practice and experience and will earn more marks on the hard questions in years to come. In any case, Geoff and I are very pleased. I am thus able to join the team for a second, sunnier attempt at Table Mountain. I arrive in time to see the end of the team’s latest instalment of ‘play a round of bridge in unusual places’, and even get to see a group of dassies sunning themselves on the cliff edge. Some of the group are tired or nervous about medal boundaries, but the remainder head for a walk to Maclean’s Beacon, the highest point on the summit. It goes without saying that the views were beyond comparison.

After seeing the eland on Wednesday, I feel obliged to branch out and try one of their steaks, but in fact the kudu was marginally nicer. Marginals are up for grabs after dinner, as it’s time for the final jury meeting, featuring the confirmation of UK as host of IMO 2019, and the all-important medal boundaries. First there is discussion of various administrative matters, and thanking various people involved in the five official languages. There are long delays while the microphone is carried round the room. Geoff makes several speeches. For these the lack of microphone proves no problem. Eventually the flashy software brings up the crucial bar charts, and the boundaries are decided. A decision has to be made about whether to award medals to 47% or 53% of contestants. Either way, the boundaries are lower than I had expected, leaving us with 4 silvers and 2 bronzes. It is a shame for Frank and Freddie to miss out so narrowly, and perhaps a surprise for Warren that he ends up only one mark off a gold, but of course these things will happen, and it is no reason not to enjoy the festivities into the night.

Saturday 12th July

While the previous night featured slicks of mathematical vomit, last night offered a digression onto genuine vomit. No hard feelings Joe. We’re now even given that I hit him over the head with a punt paddle the first time we met. I have too many spotty socks anyway, and certainly couldn’t have dealt with another night of combinatorics. While he sleeps off whatever it is he’s caught, Jill and I get mildly stressed, and the team head off on an excursion to the Waterfront. Free entrance to the aquarium is by some margin the best feature, with a remarkable collection from both the oceans that converge on the Cape Peninsula. The team debate whether the Coriolis effect or some form of social self-reinforcement process is responsible for all the fish swimming clockwise, while they play yet another round of bridge (four clubs in case you were wondering) in front of the shark tank. Geoff makes the mistake of offering to wait for us while we obtain lunch, in a further demonstration that South Africa doesn’t really understand the first word in the term ‘fast food’, while Gabriel wants me to verify that a watch he’s planning to buy is genuine. I feel there do exist things which fall outside the deputy leader remit.

I’m definitely catching Joe’s affliction, so I sleep while the team get ready for the closing ceremony. By the time I wake up, the Google cube is already dressed in the Union Jack, filled with the fetching playing cards, and providing everyone with a good core workout as they manoeuvre it onto the bus. I enjoy what I see of the closing ceremony, in particular the excellent and strident youth choir. No mewling Anglican tenors on show here. A traditional ‘praise singer’ comes onstage and shouts about maths for about three minutes, which is less impressive, but equally entertaining. Our master of ceremonies returns, wearing the exact chromatic inverse of his outfit at the opening ceremony, and guides the medal presenters and recipients through their steps. Initially this is tricky, as there are substantially more bronze medal presenters than room on the stage.

The UK team are consummate professionals of course, managing the task (found tricky by many of their competitors) of getting the medal in front of the flag, and orienting the latter correctly. Harvey positions himself well so gets his medal presented by Geoff. Gabriel does not position himself well, so disrupts the linear ordering to get his medal presented by Geoff. Photos are taken in huge quantities. The team’s plan to distribute the cards to contestants as they leave the stage is to my astonishment a) working and b) not hugely annoying the organisers.

I make a brief run down the mountain to check on our sleeping silver medallist. On returning it seems the organisers are grateful for his absence, as they ran out following the unexpected boundaries, evinced by Warren’s prize, which does indeed appear to be a spray-painted bronze. I have missed Geoff being presented with a vuvuzela in recognition of his maximally numerous contributions to the jury. Like a toddler on Christmas morning, I suspect his new toy may ‘get broken’ at some point fairly soon. This is more of a reception than the usual sit-down affair, and the remainder of our team seem to be happily mingling, so there is time to say all the requisite goodbyes, and reflect on an excellent competition. Gabriel chooses 12.45am as the moment to ask US leader Po-Shen the question about probabilistic combinatorics he’s been brewing all week. Let it never be said that social convention stood in the way of good mathematics.

Sunday 13th July and Conclusion

I need to be in France, and Frank needs to be in North-East China, so we are leaving earlier than the rest of the group. Joe appears to be operational again, and receives his silver medal in front of a small but adoring crowd at breakfast. Muffins are again served with grated cheese, goodbyes are said, the final Rand are changed back, and we are off.

My journey to Paris via Dubai was highly unpleasant, and my view of the Emirates was mainly through the bottom of a paper bag, so I won’t dwell on that at all.

What I should dwell on is what an enjoyable year and an excellent IMO we’ve experienced together. I understand why peers and colleagues might well ask why I choose to come to the olympiad rather than take a conventional holiday, but this was a great event to be a part of, and a great group of people to travel with. I hope I’ve given a flavour of the students’ enthusiasm for problems in this report. It was entirely infectious, and we of course enjoyed all the other possibilities which two weeks in Cape Town offered us.

For me, there was a particularly pleasing cyclicity to lead a team at the IMO including Freddie and Gabriel, who were junior students at the first summer school I taught at, and though they are perhaps disappointed not to have made a bigger splash in the competition, they and Frank have been entirely excellent people to know over the past few years, proving exemplary models to their younger colleagues both mathematically and generally. We will miss them as students, but equally look forward to working with them as colleagues in the future, should they wish. While we missed the starry heights of 2013, this was nonetheless an excellent team performance, and with young team members, young reserves, and plenty of talented and keen students getting involved at all levels, the future seems bright for UK maths. I hope that our activities through the year to come will be as enriching for everyone as it has been in 2014.

IMO 2014 – Part Three – Opening Ceremony and Exams

Posted on July 10, 2014 by dominicyeo

Monday 7th July

It’s the day of the opening ceremony, and there seems not to be much going on for the students around the accommodation sites, so rather than sit around feeling nervous, we decide to tackle another mountain. I remain unconvinced that the so-called Lion’s Head looks like its name, no matter how much further the analogy is taken by references to Signal Hill, home of the famous midday cannon blast, as the flank and tail and so on. Led by Joe and his freshly acquired Duke of Edinburgh Bronze award skills, this climb is extremely pleasant. The panoramic views from the top over the peninsula, the bays on both sides and Robben Island more than reward our final rocky exertions and make up for the disappointment of the cloudy visit to Table Mountain last week.

Reinvigorated, it’s time for sitting around and listening to speeches as we are transported en masse to the upper campus for the opening ceremony. While no-one could accuse the Minister for Education of including insufficient detail in her address, and a bit less amplification for the drum troupe and the operatic tenor singing the national anthem might have improved both, this was excellent by comparison with the norm. The decision to hire a professional compere was a wise one, as he riffed effortlessly through what might have otherwise been awkward moments, including the heckling of the vice-chancellor’s speech from the chandeliers by a small flock of starlings.

Also novel was the plan to dispatch the procession of teams based on the order in which they first competed at the IMO. For once this meant the UK got the chance to catch the eye early in proceedings. As the first team to throw gifts into the audience (surplus IMOK 2013 keyrings before you ask) along with Gabriel’s second year in a row of successfully bearing another team member round the stage on his shoulders, this was a triumph in every regard. Breaking up the procession at the halfway mark with a circus performance also worked very well, though one could feel the visceral clenching of 1200 buttocks when it became clear the mime artist was indeed going to choose a pair of contestants for audience participation. Geoff gives the team a cheerful wave from the upper balcony. This is initially misinterpreted as a triangle, leading to confusion about whether this is a Masonic greeting or merely a hint for the geometry component of the exam.

Tuesday 8th July

The team avoid the nervous chaos of a mass bus ride, and instead opt to walk up the hill to the sports hall which will be the site of the exams. Spirits seem high and there is evidently no need for a rousing team talk. After all, if you’re not feeling up for the IMO at the start of the first paper, at least you have 4.5 hours to increase your enthusiasm. Other countries seem to be having grave difficulties finding their desks but the UNKs are giving off confident signals by passing this first task, even though Warren and Frank’s desks are not labelled. As a pleasant novelty, the guides and deputy leaders are allowed to sit in the tiered spectator seating and observe the lead-up to the start of the exam. As a less pleasant novelty, they are allowed to stay there even after the start of the exam, though some people are openly chatting within a few metres of the contestants. Eventually the call to act like adults and leave in silence is made, and the serious business can begin.

It becomes apparent that the deputy leaders are not going to be given copies of the paper. Some take this opportunity to become extremely angry indeed, but it seems like less effort to go for a run up the mountain to the King’s Blockhouse, an old armoury and cannon installation towards the top of Devil’s Peak. On the way back, I pass by the exam hall again and count at least three unlocked side doors into the gallery. Of course this is being patrolled intermittently by invigilators so poses no real security risk, but I can nonetheless see some of the UK team, and they are indeed wearing all the layers which Jill and I had previously nagged them to bring.

Afterwards, I have the luxury of a 30 second glance at Freddie’s paper before starting our informal debriefs. Everyone reports the same outcome: a) it was really cold and b) they thought Questions 1 and 2 were really easy and couldn’t make progress on Q3. There is discussion of whether a floor symbol in the wrong place is likely to be heavily penalised. I reassure them that it obviously will not.

Rather than soak up the purgatorial air of the student residence all afternoon, we head off to the nearby Kirstenbosch Botanical Gardens. Highlights include the Protea plantation, a roosting pair of lesser spotted owls, and the canopy walkway, though Jill’s enthusiasm visibly dampens when a group of American tourists match step and kickstart some interesting resonance phenomena. 18-year-old Gabriel particularly enjoys the sign banning children from chasing the resident guinea fowl. He finds a guinea fowl and pursues it. He then finds a whole flock of guinea fowl and encourages 15-year-old Joe to join him in chasing them, before chastising his protege for flouting the rules. Gabriel is available for birthday parties, weddings, Bar Mitzvahs, and combinations thereof.

Three guys try to commandeer our taxi home, and awkwardness follows when it becomes apparent that they are coordinators, whom we definitely should not be meeting until after the exams. In any case, we keep our taxi and arrive back in time for a lengthy discussion predicting the composition of tomorrow’s second paper. The team suggest that every IMO must include a functional equation, but the stronger statement that every set must include a functional equation remains open.

Wednesday 9th July

We repeat yesterday’s operation, sending the team up the hill with best wishes, but today I diverge for the deputy leaders’ excursion to Cape Point, organised at the last-minute by our relentlessly energetic senior guides Robyn and Justin. Highlights of the trip include seeing a herd of eland and a baboon in the national park and the walk down to the lighthouse marking the southernmost point in Africa. Well, in fact it turns out that Cape Agulhas, about 50 miles away, holds that title but that doesn’t diminish the experience. All the while, our guide Rhonda holds everyone’s attention with the account of her family’s life through recent South African history on the Cape Peninsula.

It becomes apparent that some of the other DLs do that share the constraint that we need to return in time for the end of the exam, as had been promised before departure. A battle of wills develops regarding whether to stop at the Cape of Good Hope for a photograph. My will wins. Nonetheless, by the time some members of the delegation have finished smoking and purchasing postcards, we are against time, and I end up having to catch up the UK team walking home across the rugby fields. They have enjoyed the geometry Q4, and have a mixed take on Q5. The range of speculative noises being offered suggests I may have a long night ahead.

Meanwhile, Geoff returns from the top secret leaders’ hotel, the location of which was revealed merely three times this year. We exchange news then proceed to a preliminary glance at the scripts. Some things seem good, some things seem unconventional. After dinner, I brave the frozen wastelands of my room and start a more detailed analysis. Q2 is going to be a fight. I really need to talk to Harvey, and not just to let him know that there’s no ‘D’ in ‘Pigeonhole Principle’. Anyway, he and the rest of the team are stuck behind about 400 contestants watching the World Cup on a small TV, but I bide my time and catch the moment when Holland miss the first time to snake through and perform my interrogation. A few minutes later, we confirm that Harvey’s coin has indeed been wrong about the outcome of the past eleven matches. The Germans and Argentinians will be queueing up for a viewing faster than you can say ‘independent and identically distributed’.

IMO 2014 – Part Two – Training Continues

Posted on July 8, 2014 by dominicyeo

Thursday 3rd July

Now that there is less compulsion to be rushing away, we decide to start the exam at the more civilised hour of 8.30am. Angelo, the Australian leader, decides it will be minimally confusing to set the giant clock in our exam room to start at 9am, as it would in the IMO proper. The UK team have spent some time over the past few days discussing when and whether various functions attain their minima, and I feel this may not be a good example. Anyhow, Q1 is found rather easy, Q2 is found very difficult, and only Gabriel has the courage to cut his losses and move on, and provides a beautiful proof of the combinatorial Q3. The prize for most effortless solution to the inequality goes to Frank. Warren wins the prize for geometry rough work closest to getting a pity mark, but does not in fact win a pity mark.

At least it makes grading rather straightforward, leaving time to accompany some of the UK and Australian team on a walk beyond the university up the side of Devil’s Peak. Jethro the hotel’s German Shepherd, described in the guidebook as ‘a teddy bear with boundary issues,’ has taken a strong liking to Joe, and seems reluctant to allow him to leave and roam loose on the mean streets of Rondenbosch. Once we’ve negotiated this amusing (to everyone else) hurdle, all goes smoothly, and the glowing pink sunset on the trek down is more than worth the energy expended. I make arrangements so that the team can watch France-Germany over dinner, and in fairness they are unfailingly polite in letting me know that the match is not in fact until tomorrow. I feel I am ill-qualified to choose toppings for a set of twelve takeaway pizzas, but am reassured by everyone that the decision to avoid Bacon and Banana is a wise one.

Friday 4th July

To introduce some novelty into the daily routine, today the UK team has chosen three questions for the Australians to attempt, and vice versa. They will then have to mark the solutions, and co-ordinate these marks with Andrew, the Australian deputy, and myself. The first round is straightforward enough, once we have found a room for the task that is not playing host to an angle grinder. The Brits have chosen questions which will be easy to mark, so perhaps they do not get as much out of the exercise as they might have done, but it is nonetheless useful to see how other people like to write up ideas, and also to feel what level of rigour is easiest to follow critically. There are more difficulties with the reciprocal arrangement, as the questions are more fiddly, or at least have more cases, and some of our students seem to have relished the opportunity to add elements of mystery to their solutions wherever possible.

Meanwhile it has been pouring with rain outside all afternoon. It is nice to learn from the ITV commentators that not only is it 35C in Rio but that the weather is also lovely all across Northern Europe. All is well though: we have tea.

Saturday 5th July

If this were the Ashes proper, the swing bowlers would be licking their lips in anticipation of starting soon after an early lunch. In the Mathematical Ashes, no such quarter is given to the weather, and both Australian and UK teams brave the pouring rain up the hill to start our final training exam on time. Of course, this exam has extra bite, as the results will be published on Joseph Myers’ website and to the winner will be the spoils. In this case, it’s a brass urn filled with the charred remains of some geometry circa 2008 from my second IMO in Madrid. As a sign of colonial arrogance, or perhaps because BA has an upper bound on baggage mass, we haven’t brought the trophy this year from UKMT towers in Leeds, so the team have the added pressure of avoiding an embarrassing and expensive (in postage terms) turnaround.

I’ve decided to rewrite Q2, which features a ‘crazy scientist’ investigating something which looks almost exactly in everything except name like a finite simple graph. It seems simpler to call it a finite simple graph, and give a name to the crazy scientist. In any case, I have to mark this question, and it turns out to be the deal-breaker, with beautiful solutions from Joe, Warren and Harvey taking the UK to 59 points to Australia’s 50, despite an outstanding 21/21 from AUS1 Alex Gunning. A small wager once again rides on how long will elapse between emailing Joseph Myers, and the result appearing on the BMOS website. Standards are slipping clearly, as the interval is greater than five minutes this year, though substantially less than ten. Rather than basking in their success, the UK team are keen to spend more time discussing esoteric Euclidean geometry. The hotel’s blackboard proclaims the proverb of the day as “Wanting to be someone else is a waste of the person you are,” but it seems that the over-arching thought for the day here is “no famous triangle centre lives on the inner Soddy circle.” Famous last words.

Sunday 6th July

The UK IMO delegation has a rich history of incompetence regarding accommodation, and it is reassuring to learn this morning that these traditions continue to flourish. Harvey and Frank learn the hard way that 15 minutes before check-out time is the maximally inconvenient time to lose your room key. I await with keen anticipation the email from reception telling us they found it down the back of someone else’s sofa. Today we are moving from our guesthouse to the IMO itself, a 400m walk down Rondenbosch Main Road. A patch of pavement along the way described by Geoff as ‘literally impossible for suitcases’ turns out to be literally possible for suitcases, but otherwise this is an uneventful final leg of our journey, at least relative to the dozens of teams flying into Cape Town from all over the world this morning.

Once at the UCT towers of accommodation everyone receives a goodie bag of programmes, umbrellas and IMO stationery, and a room. Apart from Frank, who merely gets a goodie bag. This is a hugely stressful day for the IMO organisers, and this one was definitely by far the most efficient of the four I’ve experienced, but the difference between our levels of concern and their levels of concern on this matter is mildly concerning. In the end everyone gets a bed on which to relax and examine their loot. I’ve got the sub-warden’s room, which appears to mean nothing apart from having a kitchen sink rather than a bathroom version, and having a view inwards rather than towards the mountain like the students on the other side of the building, which, incidentally, is shaped rather like the emblem of the Isle of Man.

It also becomes clear that this is going to be the week of the thousand sleeveless sweaters, which given the temperature in the rooms may be getting more use than planned. We see the signs reminding resident undergraduates to bring a heater and laugh coldly. Our guide appears to be indisposed, so senior guide Julian offers to take us for a short tour through part of central Cape Town. Highlights include the exotic trees and attention-seeking squirrels in the Company Gardens, and a market mainly featuring African curios, selling more exorcist masks than you could shake a stick at.

I go for a run round the campus, and fall down a very small flight of steps after being distracted by a flock of ibis and Egyptian geese. They continue to cackle at my misfortune, but I nonetheless return in time for the essential tour of the dining area. Frank and Gabriel seem highly enthused by the volumes of mayonnaise available. No other enthusiasm is visible except for the end of the Wimbledon final, and the possibility for several rounds of bridge, alternating with attacks on past shortlist problems. Gabriel’s and my bidding patterns might charitably be described as unconventional, but seem to work surprisingly well together. More relevant intellectual challenges await though, so it is an early night all round.

IMO 2014 – Part One – Introduction and Arrival

Posted on July 3, 2014 by dominicyeo

Introduction

The International Mathematical Olympiad is a competition held every year in July, welcoming school students from over 100 countries. Tempting though it is to picture a drawn-out global version of the ‘mathletics’ scene at the end of Mean Girls, it actually revolves around two 4.5 hour exams, each with three questions from various areas in elementary pure mathematics. A handful of the ~500 contestants will make serious progress on the ‘hard’ question each day. Medals are then awarded to roughly half of the participants.

Each team has a leader, who arrives early to help set the papers, and also assesses their team’s scripts, presenting their marks for approval by a board of co-ordinators supplied by the host country. Each team also has a deputy leader, who stays with the team initially, then joins the leader for this marking process. This is the second year that I will be the UK deputy leader.

As well as the competitive side, the olympiad is a great opportunity to meet other young mathematicians from all around the world. Certainly I am still in touch with many of the people I met when I was lucky enough to compete in Vietnam and Madrid (2007, 2008 respectively). As the competition moves country every year, it’s also a great chance to see some exciting places. Last year we visited Santa Marta, on Colombia’s Caribbean coast. My report on IMO 2013 starts here (or as a pdf without pictures here). This year we will be guests of the University of Cape Town in South Africa. As in recent years, the UK team arrives early to train with the Australian team, spending a week tackling practice papers and discussing problems of interest.

Anyway, on with the report.

Sunday 29th June

This year’s IMO delegation gathers at Heathrow Terminal 5. Freddie and I have booked a cab from Oxford, for ease of moving the boxes of team uniform, this year all lovingly adorned with the logo of our new sponsors, Oxford Asset Management. In any case, the M40 is unprecedentedly rapid and we are embarrassingly early. Fortunately, everyone else has also erred on the side of caution and we are able to saunter through security with plenty of time. My bag is pulled aside to be searched. I am asked to demonstrate the use of a tuning fork. I don’t know how this item ended up there, but I perform the task with relish. It’s been a long day, so opt for 220 rather than 440Hz. Worcester College Choir, starting a recording of contemporary Christmas carols today, will I’m sure vouch that this is preferable for the general public’s aural welfare. We learn that though some of the team lack virtuosic chopstick skills, they are unfussy, and able to make it to gate B35 without the slightest danger of passport loss. All bodes well for an excellent trip.

Monday 30th June

The flight proceeds smoothly. For complicated reasons I am registered on a different booking so am sitting slightly apart from Geoff, Jill and the team, so am not involved in the discussion of past IMO shortlist problems and unusual sleeping positions. Everyone seems fairly refreshed as we negotiate customs and are met by a small group with smiles and IMO 2014 welcome boards. Our journey through town affords glimpses of the contrast in wealth across Cape Town, but our guesthouse in Rondebosch is extremely pleasant, both for the inviting beds and its picturesque setting at the foot of Table Mountain. The Australians have arrived just before us; old friendships are renewed and new introductions made.

The Hussar Bistro at the corner of the street promises the best steaks in Cape Town from 2012, and the party of 22 dines for less than £70. Everything is indeed excellent, and comes with unprecedented volumes of creamed spinach. Feeling the need for exercise, the teams climb the 160-odd steps to the maths department at the University of Cape Town, past what is probably the most attractive campus facade in the world, before heading further uphill to the memorial to Cecil Rhodes, which in its neo-Grecian extravagance bears a noticeable resemblance to Rhodes House in Oxford. Undoubtedly a man who still divides opinion, but the views through the columns down towards the city, the distant mountains, and two oceans are stunning.

Dinner at a nearby Thai restaurant offers similarly remarkable value. My penance for joining an adults table is to be referred to as ‘the young man’ by all the staff. I regret asking for my Pad Thai to be hot. I can barely feel my lips. Lesson learned.

Tuesday 1st July

Yesterday’s balmy 23C conditions had lulled us towards a false sense of security. It is very much winter here, evinced by our walk through the darkness to start our first training exam at 8am up at the maths department. No-one takes advantage of the chance to ask silly questions. Perhaps they are saving it for the IMO proper? My mind gets on with some writing while my body recovers from last night’s chilli-induced trauma.

The UK team have made a promising start. The first question exposes their inexperience with undergraduate-level analysis, but there’s some particularly good stuff from Joe and Freddie on the hard second and third questions. We had planned a trip up Table Mountain, but the weather has turned, and with the prospect of gales and zero visibility, unsurprisingly the cable cars are not running. Instead Geoff and I wait at an imaginary bus stop, later transferring to the real version across the road, before getting down to some serious marking.

A debrief with the team follows, where outstanding arguments are praised, and questionable logic is ridiculed beside the pool. While it is easy to jest about such matters, at the actual IMO, the coordinators will not have much time to look at each script, so it is very much to the candidate’s advantage to make it as intelligible as possible. Later, perhaps in homage to Euler, the team develop a very strong attachment to Switzerland, and are thus gutted when Argentina score with 3 minutes left in extra time. They too have learned their lesson, and vow to reserve their energies for affairs of the mind.

Wednesday 2nd July

An early start for our second exam morning. Geoff says goodbye before he is whisked off to a mystery location to join the other leaders and start the important task of selecting from the shortlist of problems. This leaves time to transfer across the city to Tafelberg Road, and the cable car station serving Table Mountain. Even during this short and uneventful journey – standards of taxi driving are evidently much higher here than last year in Colombia – the weather turns, and the wires disappear shortly above the base into the thick cloud, known for obvious reasons as the ‘tablecloth’. As a result, the view from the summit is rather disappointing, reminiscent more of Victorian London than the glorious vista promised by the postcards.

At least there is a option of a bracing walk around the plateau. While it certainly isn’t precipitous, anyone coming up with an image of a pancake-flat summit is in for a surprise. The fetching and distinctive rugby shirts are useful for identifying the UK group wending their way between the rocks through the mist. The team discuss how close to the edge is too close to the edge. There is, after all, no injury that a pocket first aid kit cannot fix. Even on a cloudy day, one can still see the ‘dassies’ – essentially glorified rats (and slightly more suitable for representing as stuffed toys) that live on the plateau. Mike Clapper announces the implausible fact that they are most closely related to the African elephant and various eyes are rolled. Shortly afterwards we see several information boards announcing this same fact and the eyes are unrolled, though we do not in fact see any dassies.

In fact today’s South African wildlife experience is entirely gastronomic, as in the middle of an evening/night marking session I get a chance to try Kudu. Leaving aside my short-lived embarassment at having inadvertently asked for Kobo, this is excellent, with the game quality of venison but the rich tenderness of beef. Marking even Harvey’s elegant but mysteriously multi-coloured solution to the twisty Q2 is much more tolerable afterwards, and when I finish at 10.30 the team demand an instant debrief and discussion of the problems they want to set the Australians. I just hope this enthusiasm is not entirely a function of the rest day in Brazil…

Eventually Almost Everywhere

A blog about probability and olympiads by Dominic Yeo

Skorohod Representation Theorem

Ornstein-Uhlenbeck Process

Noise Sensitivity and Influence 1

Random Maps 3 – Leaves and Geodesics in BCRT

Random Maps 2 – The Schaeffer Bijection

Random Maps 1 – Towards the Schaeffer Bijection

IMO 2014 – Part Four – Coordination and Close

IMO 2014 – Part Three – Opening Ceremony and Exams

IMO 2014 – Part Two – Training Continues

IMO 2014 – Part One – Introduction and Arrival

Related articles

Related articles

Related articles

Related articles