Birthday Coincidences and Poisson Approximations

Posted on September 11, 2015 by dominicyeo

This morning, Facebook was extremely keen to remind me via every available medium that four of my friends celebrate their birthday today. My first thought was that I hope they all enjoy their day, and my second thought was to ask what the chance of this was. I have about 200 Facebook friends, and so this struck me as an unlikely occurrence. But this problem has form, and it felt worthwhile to try some calculations to see if my intuition was well-founded.

Siméon Denis Poisson celebrated his 234th birthday on 21st June this year.

The classical birthday problem

The starting point is the question: how many friends do you have to have before you expect to start seeing anyone sharing a birthday? There are a ridiculous number of articles about this on the web already, so I will say little, except that I don’t want to call this the ‘birthday paradox’, because it’s not a paradox at all. At best it might be counter-intuitive, but then the moral should be to change our intuition for this type of problem.

Throughout, let’s discount February 29^th, as this doesn’t add much. So then, to guarantee having a shared pair of birthdays, you need to have 366 friends. But if you have a mere 23 friends, then the probability of having some pair that share a birthday is slightly greater than a half. The disparity between these two numbers leads to the counter-intuition. Some people might find it helpful to think that instead of counting friends, we should instead be counting pairs of friends, but I don’t personally find this especially helpful.

For me, thinking about the calculation in very slightly more generality is helpful. Here, and throughout, let’s instead take N to be the number of days in a year, and K the number of friends, or kids in the class if you prefer. Then, as usual, it is easier to calculate the probability that no two share a birthday (that is, that all the birthdays are distinct) than the probability that some two share a birthday. We could think of the number of ways to pick the set of birthdays, or we could look at the kids one-at-a-time, and demand that their birthday is not one of those we’ve already seen. Naturally, we get the same answer, that is

$\frac{^N P_K}{N^K} = 1\cdot \frac{N-1}{N}\cdot\ldots \frac{N-K+1}{N}.$

We’ve assumed here that all birthdates are equally likely. We’ll come back to this assumption right at the end. For now, let’s assume that both N and K are large, and we’ll try to decide roughly how large K has to be in relation to N for this answer to be away from 0 and 1. If we pair opposite terms up, we might approximate this by

$(\frac{N-\frac{K}{2}}{N})^K = (1-\frac{K}{2N})^K\approx e^{-K^2/2N}.$

In fact, AM-GM says that this is an overestimate, and a bit more care can be used to show that this is a good-approximation to first order. So we see that if $K=\Theta(\sqrt{N})$ for large N, we get a non-trivial limit.

Challenges for four-way shared birthdays

So the original problem I posed is harder, because there isn’t (unless I’m missing something) a natural way to choose birthdays one-at-a-time, or describe the set of suitable birthday sets. There are two major obstacles in a calculation such as this. Firstly, the overlap of people, that is we might have five or more birthdays overlapping; secondly, the overlap of days, that is we might have several days with four (or more) birthdays. We’ll end up worrying more about the second situation.

We start by eliminating both problems, by asking for the probability that exactly four friends are born on January 1^st. The general form of this probability is $\frac{\binom{K}{4} }{N^4} \cdot (\frac{N-1}{N})^{K-4}$ . Now, if $K\ll N$ , this final term should not be significant. Removing this is not exactly the same as specifying the probability that at least four birthdays are on January 1^st. But in fact this removal turns a lower bound (because {exactly four}<{at least four}) into an upper (in fact a union) bound. So if the factor being removed is very close to one, we can use whichever expression is more convenient.

In the real life case of N=365, K=200, this term is not negligible. But accounting for this, we get that the probability of exactly four birthdays on 1^st January is ~0.0021. Our upper bound on the probability of at least four is ~0.0036.

But now that we know the probability for a given day, can we calculate $(1-0.0021)^{365}$ to estimate the probability that we never have four-overlap? When we did our previous iterative calculation, we were using independence of the different kids’ birthdays. But the event that we have four-overlap on January 1^st is not quite independent of the event that we have four-overlap on January 2^nd. Why? Well if we know at least four people were born on January 1^st, there are fewer people left (potentially) to be born on January 2^nd. But maybe this dependence is mild enough that we can ignore it?

We can, however, use some moment estimates. The expected number of days with four-overlap is $365\cdot 0.0021 \approx 0.77$ . So the probability that there is at least one day with four-overlap is at most ~0.77.

But we really want a lower bound. So, maybe we can borrow exactly the second-moment argument we tried (there for isolated vertices in the random graph) in the previous post? Here, the probability that both January 1^st and January 2^nd are four-overlapping is

$\frac{\binom{K}{4}\binom{K-4}{4}}{N^8}\cdot (\frac{N-2}{N})^{K-8}\approx 4.3\times 10^{-6}.$

From this, we can evaluate the expectation of the square of the number of days with four-overlap, and thus find that the variance is ~0.74. So we use Chebyshev, calling this number of days #D for now:

$\mathbb{P}(\# D=0)\le \mathbb{P}(|\#D - \mathbb{E}\# D|^2 \ge (\mathbb{E}\# D)^2 ) \le \frac{\mathrm{Var} \# D}{(\mathbb{E} \#D)^2}.$

In our case, this unfortunately gives us an upper bound greater than 1 on this probability, and thus a lower bound of zero on the probability that there is at least one day with four-overlap. Which isn’t especially interesting…

Fairly recently, I spoke about the Lovasz Local Lemma, which can be used to find lower bounds on the probabilities of intersections of events, many of which are independent (in a particular precise sense). Perhaps this might be useful here? The natural choice of ‘bad event’ is that particular 4-sets of people share a birthday. There are $\binom{K}{4}$ such events, and each is independent of the collection of $\binom{K-4}{4}$ disjoint events. Thus we can consider using LLL if $e\cdot (\binom{K}{4}-\binom{K-4}{4})\cdot 0.0021 \le 1$ . Unfortunately, this difference of binomial coefficients is large in our example, and so in fact the LHS has order $10^3$ .

Random number of friends – coupling to a Poisson Process

All of these methods failed because without independence we had to use estimates which were really not tight at all. But we can re-introduce independence if we remove the constraints on the model. Suppose instead of demanding I have K friends, I instead demand that I have a random number of friends, with distribution Poisson(K). Now it is reasonable to assume that for each day, I have a Poisson(K/365) friends with that birthday, independently for each day.

If we end up having exactly K friends with this random choice, then the distribution of the number of 4-overlap days is exactly the same as in the original setup. However, crucially, if we end up having at most K friends with this random choice, the distribution of the number of 4-overlap days is stochastically dominated by the original distribution. So instead let’s assume we have Poisson(L) friends, where L<K, and see how well we can do. For definiteness, we’ll go back to N=365, K=200 now. Let’s say X is the distribution of birthdays in the original model, and $\Xi$ for the distribution of birthdays in the model with a random number of friends

Then

$\mathbb{P}(\exists \ge 4\text{-overlap in }\Xi) = 1- \mathbb{P}(\mathrm{Po}(L/365)\le 3)^365.$ (*)

Now we can write the crucial domination relation as

$\mathbb{P}(\exists \ge 4\text{-overlap in }X)\ge \mathbb{P}( \exists \ge 4\text{-overlap in }\Xi \,|\, |\Xi|\le 200),$

and then use an inequality version of the law of total probability to bound further as

$\ge \frac{ \mathbb{P}(\exists \ge 4\text{-overlap in }\Xi) - \mathbb{P}(|\Xi|>200)}{\mathbb{P}(|\Xi|\le 200)}.$

This is a function of L, and in principle we could find its maximum, perhaps as $N\rightarrow\infty$ . Here, though, let’s just take L=365/2 and see what happens. For (*) we get ~0.472.

To estimate $\mathbb{P}(\mathrm{Po}(365/2)>200)$ , observe that this event corresponds to 1.4 standard deviations above the mean, so we can approximate using quantiles of the normal distribution, via the CLT. (Obviously this isn’t completely precise, but it could be made precise if we really wanted.) I looked up a table, and this probability is, conveniently for calculations, roughly 0.1. Thus we obtain a lower bound of $\frac{0.472-0.1}{0.9}$ . Allowing for the fairly weak estimates at various points, we still get a lower bound of around 0.4. Which is good, because it shows that my intuition wasn’t right, but that I was in the right ball-park for it being a ‘middle-probability event’.

Remarks and References

– The reason for doing the upper bound for the probability of exact 4-overlap is that the same argument for at-least-4-overlap would have given an upper bound of 1. However, this Poisson Process coupling is also a much better method for obtaining an upper bound on either event.

– Birthdays are not uniformly distributed through the year. The deviation is strong enough that even from the set of birth frequencies (rather than the sequence of birth frequencies), we can reject a null hypothesis of uniformity. Early September is pretty close to the maximum. Two comments: 1) this is the time of year where small variations in birth date have a big effect on education, especially in primary school; 2) we are 37 weeks into the year…

– It is known that 187 friends is the first time the probability of having at-least-4-overlap is greater than ½. You can find the full sequence on OEIS as A014088. I used to have about 650 Facebook friends, before I decided that I’d prefer instead the pleasant surprise of finding out what old acquaintances were up to when I next spoke to them. In this case, the median of the distribution of the largest number sharing a birthday would be seven.

– Eric Weisstein’s article on Mathworld is, in my opinion, the best resource for a mathematician on the first two pages of Google hits by at least two orders of magnitude. In the notation of this article, we were calculating $P_4(n=200,d=365)$ . There are also some good general asymptotics, or at least recipes for asymptotics, in equations (17) and (18).

– The paper Methods for Studying Coincidences by Diaconis and Mosteller is, as one might expect, extremely readable, and summarises many results and applications, including several generalisations.

Isolated Vertices and the Second-Moment Method

Posted on September 4, 2015 by dominicyeo

It’s back-to-school day or week for much of the UK. I’m sure for many, this brings resolutions of better work habits, and while I could always use some of those too as I try to finish my thesis, I also want to start blogging again when possible.

Right now, I’m in Haifa for the Mostly Markov Mixing summer school and workshop hosted at the Technion. The talks have been interesting so far, and the environment stimulating both for the discussion of new problems, and getting work done on existing research.

I wrote much of this post a while ago, after some of the UK olympiad students asked me to tell them about second-moment methods and I politely declined. I was reminded of this by an interesting problem introduced by Elchanan Mossel in the first lecture of his series. I’ll start with this.

Suppose we consider a symmetric inhomogeneous random graph with two types. That is, we divide the vertices into two equally-sized classes, and we connect vertices in the same class with probability p, and vertices in different classes with probability q, all independently. The question is: if we can see the resulting graph structure, with what accuracy can we recover the class division? [Note: this setup with symmetry between the types can be called the block model.]

This is a hard problem, and got us all thinking a great deal. In the most relevant regime, even the most sophisticated techniques do not allow us to identify the partition perfectly with high probability as the number of vertices goes to infinity. For now, though, I only want to use the most uninteresting regime as a starting point for the rest of this post. EM asked: what happens if we take sparse scaling, that is $p,q=\Theta(1/N)$ , where N is the number of vertices? Do we have a chance to identify the classes correctly?

Well in this case the answer is easy, because it is ‘no’, and the reason is that in sparse random graphs, there is a positive proportion of isolated vertices. In particular, there is a positive proportion of isolated vertices of each type. And so, when we see an isolated vertex, for large N we can specify accurately the distribution of each type given this extra information, but in doing so, we admit that we certainly cannot partition the isolated vertices into their classes. So for the rest of the talk, EM focused on the regime where the random graph is connected with high probability.

There are two ideas with worthwhile and simple content here. Firstly, the fact that such a random graph has a positive proportion of isolated vertices. I am finishing off a result in a model where the base structure is the inhomogeneous random graph, and have just now proved a short lemma showing exactly this in a slightly more complicated context. It’s a good example of the second-moment method. Secondly, implicit in the final statement of the previous paragraph is that the absence of isolated vertices and connectivity are roughly equivalent in a random graph. This is something I’ve talked about briefly before, and in the interests of keeping the resolution and actually finishing this post, I won’t talk about it here.

Earlier this year, I gave a short talk by request to the UK olympiad students about first-moment methods. In particular, they were hoping that they might occasionally want to apply such approaches to the sort of combinatorics problems you encounter in olympiads. Typically, the best examples in this setting involve demonstrating the existence of a set without certain bad properties, by showing that the probability that all bad properties hold simultaneously is strictly less than one.

The students asked why I wasn’t talking about second-moment methods. Firstly, the models (such as this one) which are the best examples are less familiar to the students, and are really rooted in the randomness. They can’t easily be turned into a combinatorics problem. Secondly, looking for lower bounds in probability suggests we are aiming for convergence in probability, rather than convergence in expectation, and this is a distinction that is unlikely to be appreciated before some undergraduate probability courses have been taken.

Anyway, we want to show that the proportion of isolated vertices in $G(n,c/n)$ is bounded below in probability as $n\rightarrow\infty$ . All the content of the argument is seen in this classical Erdos-Renyi setting. Any inhomogeneous example will merely demand extra notation.

So, first we deal with the expected number of isolated vertices. The event that a given vertex v is isolated demands that the n-1 edges potentially incident to v do not appear. The probability of this is $(1-\frac{c}{n})^{n-1} \rightarrow e^{-c}$ . Thus the expected number of such vertices is $ne^{-c}$ . We now want to show that the fluctuations (standard deviation if you will) of this quantity are small relative to its mean. To bound the variance, we look at pairs of vertices, v and w. Note that the events {v isolated} and {w isolated} are not independent, since knowing that v is isolated tells us that the edge from v to w is not present, which slightly increases the chance of w being isolated. (For a very concrete example, think of the case n=2.)

However, in a large graph, the events are almost independent. That’s a statement which we feel is true, but we need to quantify, so we ask for the probability that {v and w isolated}. This happens precisely if none of the edges incident to either v or w are present. There are 2n-3 such edges, and so the probability of this is $(1-\frac{c}{n})^{2n-3}\rightarrow e^{-2c}$ . So now we can write

$\mathbb{E}\left[ \mathbf{1}(1\text{ isolated})+\ldots+\mathbf{1}(n\text{ isolated})\right]^2= \sum_{k=1}^n \mathbb{E}\mathbf{1}(k\text{ isolated})^2 + 2\sum_{j\ne k} \mathbb{E}\mathbf{1}(j,k\text{ isolated}).$

An indicator function takes the values 0 and 1, and so in the first sum we can remove the square sign to leave us with the expected number of isolated vertices. Secondly, the vertices are exchangeable and so we can replace each summand with the value we have already established for v and w. We can now calculate the variance of the number of isolated vertices, and we see that it is $o(n^2)$ . With a little bit more care about the limits in n, we can check it is actually O(n). In particular, the variance of the proportion of isolated vertices is tends to zero.

For explicit lower bounds in probability on the proportion of isolated vertices we could appeal to Chebyshev’s inequality. However, since the variance vanishes, we have convergence in distribution to a constant, and thus convergence in probability.

Finally, a word on the end of EM’s talk. Having said that the sparse phase is not interesting because it is impossible, we might ask about the dense phase, where p and q are fixed. Just a for concrete example, suppose the probability of connection within the class is ½, and between classes is 1/3. Thus between any pair of vertices in the same class we expect to see roughly N/8+N/18= 13N/72 paths of length 2. The summands correspond to the middle vertex of the path in the same class, and in the opposite class respectively. However, between any pair of vertices in different classes, we expect to see roughly N/6 paths of length 2 for similar reasons. Both of these quantities will be highly concentrated on their means: consider the second-moment as the existence of each possible path is independent. Indeed, the chance that we see a proportion of paths closer to N/6 when it should be 13N/72 is a large deviations event, and so has exponential decay. As a result, the chance that we get the relative positions of any pair of vertices wrong with this method vanishes for large N.

In fact, the condition that (for p<q),

$N \mathbb{P}(\text{Bin}(N-1,p)\ge \text{Bin}(N-1,q)) \rightarrow 0$

should be enough to identify the partition with high probability, and indeed this is proved by several authors including EM. Note that the dense regime comfortable satisfies this condition, since it holds even without the factor of N. (The sparse regime, completely fails as the probability is roughly constant.) Even closer to the connectivity threshold remains interesting!

IMO 2015 Diary – Part Four

Posted on July 20, 2015 by dominicyeo

Sunday 12th July

I spend many hours reading the students’ scripts for the medium questions 2 and 5. Psychologically, this solitude is quite a sudden shift after so many days of constant group interaction. Although only one of the twelve solutions is complete, I’m really pleased with how everyone has presented their progress. We’ve spoken a lot at the camps during the year about how to write up maths under various kinds of pressure so that it is intelligible to other human beings. All the boys have been very clear this year, so they should get plenty of marks and coordinating won’t cause much drama.

By comparison with the student site, the leaders’ hotel has slightly better views, slightly better food, and an even more appalling lift availability algorithm. When the work is done for the day, I meet Jill and the students at the night market, where Lawrence is sharing round a packet of fried giant crickets. They have enjoyed their excursion, especially the visit to an umbrella and other handicraft factory, where it seems they did their best to re-inflate the Thai economy. Neel has a three foot wide fan, hand-painted in a style evoking My Little Pony. While it doesn’t quite conjure the demure grace of, say, Callas as Madam Butterfly, it does induce a billowing wind tunnel effect, which is appreciated in the back of our taxi.

Monday 13th July

Today is the main day of coordination, when Geoff and I meet local markers to agree the UK students’ scores. Over breakfast we decide to ask for a solitary 1 for Joe’s hastily-written summary of Q6 in our first meeting. After some not especially thrilling wrangling about the meaning of the phrases ‘combinatorial description’ and ‘non-trivial progress’, we get what we want without having to deploy my carefully-worded speech.

This will turn out to be by some margin the most challenging meeting. On Q2, they have already decided to forgive Warren’s microscopic omission, and the mark schemes are extremely precise, especially for the middle problems which normally cause the most trouble. Everyone seems to be interpreting them sensibly and similarly so there are no delays, and we are able to bring forward the easier geometry meeting, and confirm all our marks by 5pm. We have {10,17,19,19,19,25}, which is certainly respectable, even if it does mean, to Geoff’s infinite chagrin after his boasts at breakfast, that we are beaten by France.

We’ve been keeping the students up to date via text while they’ve been petting elephants and dipping their feet in hot springs. We meet them for dinner, where they are disappointed at the lack of dramatic gossip about the process, but pleased with their scores, especially the efficient accumulation of part marks on the harder questions. It remains to be seen tomorrow what colour of medals all of this will generate.

Tuesday 14th July

While the UK is done, and I find some more obscure temples in town, other countries continue their final coordinations. It looks like Australia will have its best ever performance, with at least two students sure to receive gold medals, and the rumour is snowballing that USA has won, for the first time since the mid 90s. The students have been attending the IMO lectures this morning, and it seems that Ravi Vakil’s talk on `The Mathematics of Doodling’ has really got the UK boys thinking about space and the meaning of orientation.

Tiring of the comical lift process, I investigate the hotel’s external fire exit, disturbing a flock of pigeons, and a rat the size of a small dachshund. In pursuit of more interesting wildlife, Jill suggests we take the students to Chiang Mai Zoo for the afternoon. Sam and Harvey enjoy the real-life version of Hungry Hippos, and we find an enclosure with a large (ie at least 9), odd number of tortoises, of which precisely one is feeling rather, ahem, left out. The main attraction though is the giant panda Chaung Chaung, who we get to see eating his bamboo with the satisfied langour of a chubby toddler.

We diverge again so I can attend the final jury meeting, where after some brief admin, we pass rapidly to the medal boundaries. There is a new protocol in place this year, which I will leave for Geoff to explain, but the only non-trivial decision to be made is whether the gold cut-off should be rather higher than ideal or slightly lower than ideal. I disagree very strongly with some of the baffling comments which are made on both sides, but only the leaders have a say in this, and the end result is a narrow victory for the higher cutoff*. The UK upshot is that our triumvirate scoring 19 scrape into the silvers, while Warren unfortunately misses out on gold by one point for the third competition in a row. It’s hard to know what to say in these circumstances, but at least by meeting up with the Australian and American teams, we find other students in similar positions, and the feelings of elation and disappointment can be more widely shared.

[*As a result, about 1/15 rather than the statuted 1/12 students get the top award. The other option would have been 1/10.5. So all those leaders concerned about the ‘de-evaluation of the gold’ etc can sleep easy. So can any of their current and past gold-winning students, who had been so worried about retrospective reappraisal of their abilities. You’re right – this was ludicrous.]

Wednesday 15th July

I’ve got the rest of my life to lie in, so decide to cycle to the temple at the top of Doi Suthep. I rent the fanciest bike I can find, for B300, and, to the astonishment of everyone, a helmet for B200. Given the standard of driving, which is at times even worse than Colombia, this seems an absolute bargain. The ride itself though is more exertive than enjoyable, with no real views except the temple at the top, which is more extensive and more gold than the others in town, but also far more busy, which rather spoils the effect.

The real business of the day is the closing ceremony, held through the afternoon in the giant theatre within the student hotel. There’s an excellent drumming and dancing ensemble, and a beautifully-edited video of the IMO activities, which one probably ought to describe as comprehensive rather than a vignette. After about an hour, the medals are awarded, with a great deal more efficiency than normal. The idea to go in decreasing order of score within increasing order of medal is unusual, but does mean that our 19-ers receive their silvers together. Warren and Michael from USA compete for who can get their flag in the premier position. There are a few speeches, and a preview of IMO 2016 in Hong Kong, before we are released for more photographs and an early dinner.

The notion of having an indoor food market as part of the closing banquet is a good one, though it is a struggle to decide whether items are sweet or savoury. Lawrence, Joe and Sam get the chance to show off just how far their chopstick abilities have improved with tricky numbers like ribs and fruit salad. Then the live music starts, and whoever did the soundcheck has some questions to answer, as we can genuinely feel the bass vibrating through our chairs. We retire to the lobby which is, despite the continuing efforts of Elvis, much quieter. As various teams gather, and the students loiter to make final use of the games in the recreation room, this year’s IMO draws to a close.

Thursday 16th July

My flight to Mandalay is not until later, but I join Geoff to meet the rest of the UK group at Chiang Mai airport at 7am. Some of our students are looking rather rough round the edges, for a mixture of illness- and fatigue-related reasons, and there is enthusiasm only for a final round of anti-nausea medication. I’m sure it will be a fun 36 hours for everyone. In any case, soon they are off for a 12 hour layover in KL then home, and I have several hours to ponder.

My only negative thought about this year’s IMO was that the difficulty of the papers reduced the number of students who could feel the satisfaction of completing a medium or hard problem. Earning silver medals based on the easiest problems and part marks is not, in my opinion, entirely the idea, but of course it is the same for everyone. It’s probably also a good reflection on our training programme that the majority of our students feel they wanted to do much better, while we nonetheless came 22nd, with an entirely respectable medal haul. Certainly any disappointment felt about this result should not negate the value of everything they’ve learned by solving problems, and from discussions with each other and the staff during our training. In all other regards this IMO seemed a triumph. Students from all countries seem to have enjoyed themselves, and I’ve had a good time too.

Our camp for new students will be held in Oxford in just a few weeks’ time, and five of this team are eligible for Hong Kong next year. There’s plenty of interesting mathematics just around the corner. But right now, I’ve got to board the world’s most questionable aircraft, so consider it announced that I might have solved the Riemann hypothesis, and we’ll let fate run its course.

Final Words

Training a UK team and taking them to the IMO requires a huge amount of effort from a large number of people. Thanks are particularly due to:

All the academic and pastoral staff at our camps this year in Oxford, Hungary, Cambridge and Tonbridge, and the UKMT office, especially Bev, who ensured everything ran smoothly. Also everyone who helped set just about enough problems to sate the voracious appetites of our students.
Alison, Lina, Mun, and the other staff at Nexus International School, where our stay was pleasant and conducive to good mathematics.
Everyone involved with IMO 2015 who ran a competition which was, from the angles I saw at least, almost faultless. In particular, our guide, Korn, who couldn’t have been more helpful. We all wish him the best as he moves to Columbia next month.
Paul Janssen, the inventor of Imodium, without whose contribution to science many moments of this trip would have been much less comfortable for the protagonists.
Geoff and Jill, who were excellent colleagues in every sense through the challenging and the joyous moments of this year’s trip.
Our team, comprising Joe, Lawrence, Sam, Warren, Neel and Harvey, who are all thoroughly nice people. It’s been a pleasure to watch them improve together through the past few months, and I’m sure they will go far in whatever mathematical or non-mathematical avenues they choose over the years to come.

IMO 2015 Diary – Part Three

Posted on July 15, 2015 by dominicyeo

Wednesday 8th July

Because of my complicated post-IMO itinerary, AirAsia will be a major feature of my life over the coming weeks, so perhaps I should be careful what I say. First impressions are not good. The online check-in software would have been out-of-date in the late 90s, and within an at the time completely empty plane, the algorithm assigns us seats 23A, 23B, 23C, 23D, 23E, 23F, 24A and 8F. Still, you get what you pay for, and we did not pay a lot at all. What we get is a flight to Thailand, during which we meet the Malaysian team, and our own students attempt one of the hardest outstanding problems from last year’s shortlist.

We arrive in Chiang Mai, and find an impressive greeting party from the IMO, who seem organised, keen to present us with garlands, and even more enthusiastic about taking photos than me. Our guide, Korn, leads us onwards to the Lotus Hotel, where the students will be staying for the duration of the competition. Our initial impression is that the rooms are lovely, the lobby is full of familiar faces, and the dessert is bright blue jelly. So far seems an excellent venue choice.

I’ve been in touch with BBC World about a live interview tomorrow morning. There’s been some confusion with photographs, so they are particularly keen to talk to Neel about his experiences as a girl attending international maths camps. Even in the event of finding an alternative narrative arc, the arrival of 600 technophile teenagers is putting strain on the hotel’s wifi. Skype seems a distant possibility, given the difficulty even in following an exciting first day of the (original) Ashes, featuring our second favourite prodigious Joe, via text. The Anglophone viewers of SE Asia will have to contain their excitement for now.

Thursday 9th July

We are up painfully early, in order to arrive painfully early at the opening ceremony. We have our first experience of songthaew, the ubiquitous red taxi minibuses. Though rather reminiscent of a police van, at least it’s a chance to get to know each other better. The team have brought their flags and brushed up smartly, and seem keen to pose with everyone who asks. Security is very tight – we are scanned repeatedly and our temperatures taken. We have a three hour wait, the giant hall is very stuffy, and it’s not clear whether we will be allowed to leave in a medical emergency. Five of the team work on C8, while Joe continues his quest to experience the first aid facilities at every IMO he attends. The room is very well-equipped, and the staff seem keen to use as much of the equipment as possible on Joe, but eventually they are persuaded that a horizontal surface and a glass of water will more than suffice in this instance. I find this gently air-conditioned room by some margin the most pleasant place in Chiang Mai so far.

All of this endeavour is for the benefit and protection of the princess, who as an enthusiastic supporter of STEM and enrichment is guest of honour. Her throne is suitably gold, and her entrance suitably Sheba-esque. Because of the presence of royalty, we are informed that our team procession across the stage must be formal – no projectile key rings this year. She departs with commensurate fanfare at the end of a remarkably short ceremony with a tragic lack of folkloric dancing, then there is the opportunity for more spontaneity, and an infinite number of photographs. The trend of the past two years that UK team members should carry others on their shoulders at such events seems to have become firmly established, to the chagrin of risk assessment form writers everywhere, though Sam and Warren appear reliable chariots this time. I try to ask as many of the officials as possible what their medals are for, but it’s tough getting many replies. I guess Thais are uniformly very heroic.

The afternoon stretches out somewhat, so we visit the Suan Dok temple, where everything is gold or brilliant marble. Apparently anyone who rings all of the many bells and gongs that line the perimeter will become famous, and some of our team gleefully test this hypothesis, to the annoyance of the many feral dogs who had been enjoying a mid-afternoon snooze in the grounds.

The students are keen for an early night, but not before a dance-off to some Thai music videos. While channel-hopping, they find coverage of the opening ceremony on the news, including a brief clip of our sashay and bow across the stage. We were not together. At all. Jill and I retire to the lobby, where no-one seems to have the heart to tell the hapless Elvis impersonator that he has forgotten to turn on his microphone.

Friday 10th July

The students are up fairly early for the first paper. They are allowed to take in a ‘talisman’ small enough to fit in their hand, and a kedondong each, lovingly rescued from Malaysia, seems the perfect choice. There is a mixture of nerves and excitement, but the algorithm for getting 500 contestants into 500 desks seems sensible, and so there is little for me to do except offer best wishes.

During the exam itself, the deputy leaders were whisked off to visit an elephant sanctuary. I remain ambivalent about the principle of teaching animals to perform tricks, but at least this show was tasteful, with a penalty shootout building to a triumphant climax unfamiliar to England fans, and a sequence of live paintings that were genuinely remarkable. I also take the chance for a short ride. It is clear that going uphill is a great deal more comfortable than lurching downhill, especially when steps are involved. It was a memorable experience to see these magnificent animals up close, and I hope the existence of such places helps towards conservation in the wild too.

We return to meet the students directly after the exam. Warren seems unimpressed by Q2, despite having solved it, while the others’ moods range from disappointed to bitterly disappointed. We move on though, especially since it will turn out that many comparable countries have a similar reaction to this question, for which the crucial division into cases is more tedious than one might hope for under competition time pressure.

Mindful that the hotel is likely to be rife with unhelpful gossip all afternoon, the UK team and Luke from Ireland head off for the old walled city in the centre of Chiang Mai. First a museum of the region’s cultural heritage, with plenty of information about basket-weaving, and some answers to Neel et al’s further questions about karma, such as whether it is a universal conserved quantity. The Lan Chang temple offers further sleeping dogs, gilded dragons and the chance to meditate on the fact that there’s more to life than technical number theory problems. We go again tomorrow.

Saturday 11th July

The second paper dawns. Neel and Joe seem to be competing to see who can wear the team polo shirt for the most days consecutively, so again we watch our mostly turquoise band file through the various entrances into the exam hall. The deputies have nothing to do this morning, so John from USA and James from Canada and I attempt to go walking up the lower reaches of the Doi Suthep mountain. Despite about 600,000 hits on Google for ‘Chiang Mai hike’, both our guides and the hotel staff tell us this is literally impossible, but recommend walking along the side of the three-lane highway instead.

The hikes mentioned online turn out to be literally entirely possible. I briefly slip flat on my back, and now have the exact imprint of a bottle cap in the middle of my spine, but otherwise it is entirely enjoyable. Lunch at a nearby restaurant offering North-Eastern Thai food is incredible, and it’s lucky the exam is finishing soon, otherwise I would have happily eaten twice my body weight.

We return to find the lobby overwhelmed with the news that today’s paper was hurriedly rewritten last night, after the original version was revealed accidentally to some DLs yesterday. The British students are again unhappy. It’s been a long year of enjoyable mathematics and worthwhile training, and no one likes to see it end in tears of frustration. But maths competitions are exciting precisely because sometimes even strong students struggle, and it doesn’t reduce the value of the mathematics they have experienced together during preparation.

While that might hold in abstract, in practice it seems sensible to find more active immediate distraction. We find a path to the bottom of a waterfall, then a trail to the top of the same waterfall through the jungle. Lawrence enjoys using a leaf almost as long as himself as a fan, and Warren, leading our march, regularly shakes a particularly luscious tree besides the path, to induce a refreshing shower onto those bringing up the rear. By the end, we are all sweatier, but I hope also more grounded about the cosmic importance (or not) of making the most shrewd substitutions in a functional equation.

Geoff is now allowed to see the students, and we enjoy a relief from rice with a rare Western meal, before I transfer to the leaders’ hotel, where we will be working hard at the scripts over the next few days.

Lovasz Local Lemma

Posted on July 9, 2015 by dominicyeo

At our training and selection camp in Tonbridge in May, I gave a session about the use of probabilistic methods to solve olympiad combinatorics questions. Such an approach will normally be relevant to a problem where it is required to show the existence of a structure satisfying a particular property. We might consider constructing a structure randomly, and then try to show that the probability that our construction has the required property is non-zero.

There are several possible approaches to this, but often for the property we seek, we can describe a family of ‘bad events’ $A_1,\ldots,A_n$ , and then we have the property if none of the bad events hold. That is, we are looking for general conditions under which we can show that $\mathbb{P}(\Cap_{i=1}^n A_i^c)>0$ .

We have two cases where this is easy to do.

1) If all the $A_i$ s are independent, then so long as all $\mathbb{P}(A_i)<1$ , we have our result.

2) If the probability of the bad events have sum less than 1, then we can use a union bound

$\mathbb{P}(\cup A_i)\le \sum_{i=1}^n \mathbb{P}(A_i) <1,$

to conclude what we want.

In Tonbridge we also discussed first-moment methods, where we show that the expected number of bad events is less than 1, meaning there must be some elements of the probability space where the number of bad events is zero. In this article, we’re looking in a different direction. We’ll try to interpolate between situation 1) and 2), to make some concrete comment on the situation where the probabilities of the bad events are small, but not small enough to use the union bound, and where the events are not quite independent, but are in some sense almost independent.

The first thing we need to do is think about what it means for a family of events to be independent. Suppose we toss a fair coin twice, and consider the events:

A:= {first coin is H}, B:={second coin is T}, C:={exactly one H}.

So, it is easy to see that each pair of events is independent, but if we know that A and B hold, then also C holds (and indeed this stays true under cyclic re-ordering). So C is not independent of the family of events {A,B}. Rather than give a formal definition, I’ll say instead that an event B is said to be independent of the family of events $\{A_1,\ldots,A_5\}$ if it is independent of

– $A_3$

– $A_1\cap A_2$

– $A_3\cap A_4^c\cap A_5^c$ ,

and so on. I hope it’s clear from this what I mean. Slogan: no knowledge about which of the $A_i$ do or don’t hold gives information about B.

Now we return to our original setup. We want that each $A_i$ is independent of lots of the rest, and so we choose for each $i\in[n]$ a dependency set $D_i\subset [n]$ of indices, such that $A_i$ is independent of the family of events $\{A_j: j\in [n]\backslash D_i\}$ . It is tempting to interpret this immediately as saying that $A_i$ depends on each event with index in $D_i$ . This will normally be fine in practice, but we should emphasise that there is a lot of freedom to choose $D_i$ , and the genuinely important condition is that $A_i$ is independent of the family given by the rest of the indices.

[*Health warning*: The language I am using seems sensible for anyone learning about this for the first time, but is very slightly non-standard. Instead of dependency sets, the classical notation is to consider a dependency digraph on [n], with an edge i->j whenever $j\in D_i$ .]

The symmetric version of the Lovasz Local Lemma says: suppose $\mathbb{P}(A_i)\le p$ and we can choose $D_i$ as described so that $|D_i|\le d$ for each I. Then, if $epd\le 1$ , we may conclude $\mathbb{P}(\Cap_{i=1}^n A_i^c)>0$ .

We’ll come back to the proof, which is best seen in a slightly more general formulation. First, let’s get to grips with the notation, by reassuring ourselves that this really does lie between the union bound and the independence case.

If the events are independent, then clearly we may take $D_i=\{i\}$ for each i, that is d=1, so we may draw the desired conclusion so long as $p\le 1/e$ , which is fine, but a lot less convincing than p<1. Similarly, for the union bound, we have said nothing about the dependency relationships, and so we have to take $D_i=[n]$ for each i. So we may draw the desired conclusion provided $p\le 1/ne$ , which is obviously again a factor of e less than what we would have had with a union bound itself.

Now we’ll see how this might be useful when applied, for example, to a probabilistic construction for the lower bound on the Ramsey number R(k). From Erdos’s argument, we know $R(k)\ge (1+o(1)) 2^{k/2}$ , and we will earn an extra factor of $k\sqrt{2}/e$ . An extra factor of k/e can also be obtained by an alteration argument, but this extra factor of $\sqrt{2}$ makes this LLL method one of the strongest available for this problem.

Recall that for a lower bound, we are trying to find examples of 2-edge-colourings of a large complete graph $K_n$ , such that there is no monochromatic copy of a $K_k$ . We consider the uniform independent random edge-colouring. It makes sense that a bad event $A_S$ should be the presence of a monochromatic complete graph induced on a set $S\subset [n]$ , of size k. Since there are two potential colours for the monochromatic induced $K_k$ , we have $\mathbb{P}(A_S)=2^{1-\binom{k}{2}}$ . Then we take the dependency set $D_S$ of $A_S$ to include all those k-sets which share an edge with S, that is $|S\cap T|\ge 2$ . We think about which vertices might contribute to the shared edge, and which make up the remainder to conclude $|D_S|\le \binom{k}{2}\binom{n-2}{k-2}$ .

So now, whenever $e\cdot 2^{1-\binom{k}{2}}\binom{k}{2}\binom{n-2}{k-2}\le 1$ , as a consequence of LLL we can conclude that with positive probability the random colouring gives a suitable example, that is $R(k)>n$ . After fiddling around with Stirling’s formula in a fashion that isn’t hugely interesting, we can conclude $R(k)\ge (1+o(1)) \frac{k\sqrt{2}}{2} 2^{k/2}$ .

The prompt for this article was a discussion during our Malaysian training camp of methods applicable to IMO 2014 Q6. If you want to know just how applicable LLL is, I suggest you have a think yourself. It’s not a direct application – so some thought is involved. Maybe as an appetiser, here are some more elementary exercises, which I’ve borrowed from examples on Po-Shen Loh’s olympiad handouts, and Wikipedia, though I doubt the latter is the original source:

1) 11n points on a circle are coloured with n colours, such that each colour is used exactly 11 times. Show that it’s possible to choose one point of each colour such that no pair are adjacent.

2) A finite graph is given, and all degrees are between 50 and 100. Find some finite C such that you can always colour the vertices of such a graph so that the neighbourhood of any vertex includes at least 20 colours.

Finally, we discuss the more general statement of LLL, and explain how the proof works.

General Lovasz Local Lemma: Suppose there exist $x_i\in [0,1)$ such that $\mathbb{P}(A_i)\le x_i \prod_{j\in D_i\backslash\{i\}} (1-x_j)$ (*). Then $\mathbb{P}(\Cap A_i^c)\ge \prod (1-x_i)>0$ .

Deducing the symmetric form from the general form is not hard. Condition (*) is motivated by the proof. We want to be able to say that no matter which other events and their unions, complements etc we condition on, we still have an upper bound for the probability of $A_i$ . This bound will be $x_i$ . In particular, we want to show that the probability of bad event $A_i$ does not get too high, even if we know that lots of other bad events have not occurred.

The proof proceeds by showing $\mathbb{P}(A_i | \Cap_{j\in S}A_j^c)\le x_i$ for all i, by induction on $|S|$ . For the inductive step, you split $S=S_1\cup S_2$ where $S_1=S\cap D_i$ , $S_2=S\cap D_i^c$ . If $S_1=\varnothing$ , you are done straight away, by the assumption (*) and independence of $A_i$ and the events not indexed by $D_i$ . Otherwise, you can use the inductive hypothesis on $S_2$ , and repeated Bayes’ theorem to show what you want in a series of steps that have a lot of notation, but aren’t hugely difficult.

IMO 2015 Diary – Part Two

Posted on July 8, 2015 by dominicyeo

Saturday 4th July

The morning brings double embarrassment. My weekend alarm is still on UK time, so I arrive at the practice exam a) late; and b) to discover that I’d already set a question from today’s paper for one of our selection tests in May. Andrew and I scramble to find a suitable replacement in the knowledge that this day can only get better.

The end of the exam brings news from the UK, in the form of an article about Joe in the Guardian, featuring punditry from Geoff, and a cameo quotation from Warren, quashing some of the more ludicrous claims in another recent account, which, though entertaining, is about as reliable as the Sunday Sport. Neel spends much of the rest day standing in front of a blackboard staring slightly off to the left into a strategically-placed desk lamp, practising for when his own moment of fame, and accompanying photoshoot comes about.

The UK students have lived up to their star billing, producing some stylish solutions to an algebra question, and marking is pain-free. After a slightly questionable Indonesian meal, Jill and I try to find the fruit our team have requested as exam refreshments. The closest thing I can find to grapes are kedondong, and these turn out to be almost entirely unlike grapes, with a hard leathery outside covering a hard woody inside. Harvey is unimpressed.

Sunday 5th July

These exams are not supposed to be especially comfortable, but those among us who sampled the chilli and peanut sauce last night now have 4.5 painful hours to ponder the consequences of our decisions. Today’s scripts are also rather bloated, with a set of competent but vague combinatorics essays to wade through. If Wagner wrote mathematical arguments, they would be like this: impressive length, with occasional dramatic conclusions separated by long passages where nothing of any importance really happens.

Wanting a break from the eternal air conditioning, Sam, Lawrence and I head for a walk through the suitably steamy path leading up the hill through the jungle behind the school. It doesn’t really lead anywhere except a radio mast, so we soon find ourselves back in the diplomatic precinct. This poses a map-reading challenge since every street is called ‘Diplomatic Street’. Furthermore, one cannot rely on landmarks since, despite the Malaysian government’s prompts, only Iraq has actually got round to building an embassy here.

I am pleased to see that our students are eating the kedondong, if only as the bankruptcy forfeit for their endless poker game, which I’m also pleased to see has displaced some of the more inane traditional maths camp card games.

Monday 6th July

To mix things up, today the UK students have chosen an exam paper for the Australians, which they mark in the early afternoon, and vice versa. The point of this exercise is to force the students to learn first-hand what makes written work easy to understand, or otherwise. Warren and Lawrence have a number of subtle ‘case bashes’ to check, but Australians Jeremy and Seyoon have the short straw, with another set of UK essays, this time about moving dominos around. However, they’ve really engaged with what our students have and haven’t done, so when Andrew and I check that everything is in order, there are no major surprises. This leaves time for me to give a short talk on the Lovasz Local Lemma, which is fairly well-received, though everyone seems surprised that so much extra machinery gets you only an extra factor of $\sqrt{2}$ on the lower bound for Ramsey numbers.

As we have a bit more free time, Jill and I take the opportunity to visit Putrajaya’s two giant mosques. Jill’s efforts to dress appropriately ‘decently’ are in vain, as she is compelled to wear a giant burgundy hooded coverall for the duration. The stark ‘iron mosque’ includes a shopping arcade, and its main prayer room can fit 25,000 worshippers, who are I’m sure grateful for the air-conditioning hidden, our guide tells us, in the pillars. The Putra Mosque is just as pink on the inside, leaving Worcester College’s chapel green with envy.

Tuesday 7th July

It’s the final practise exam, deemed to be the Mathematical Ashes, which for the second time in three years finds itself well-timed in relation to its cricket counterpart. There is a both a trophy and an urn full of charred (mostly British) mathematics, which were only found hidden in a cupboard in Leeds last week, so they are not with us. Naturally, this has been interpreted as a sign of our confidence in retaining the title, and typical colonial arrogance.

It appears initially that no-one will be earning the title, as we are locked out of our usual classroom, and the alternative has plenty of sofas, but neither tables nor chairs. All is resolved quickly, and before too long, it’s time for another marathon bout of marking. About five hours later, Andrew and I have met to agree our marks and are able to make the dramatic announcement that this year we have a tie, on 84 points apiece. And no, we didn’t fiddle it. If nothing else, I’m definitely not good enough at addition to track these sorts of sums in my head.

And so the spoils, and the celebrations are shared. Our final Malaysian meal involves multi-coloured dim sum by the far side of Putrajaya Lake. Almost certainly the most greens some of the team have eaten all week…

IMO 2015 Diary – Part One

Posted on July 4, 2015 by dominicyeo

The International Mathematical Olympiad is the original and most prestigious competition for school-aged mathematicians, now in its 56th year. About a hundred countries send teams of up to six contestants. I was fortunate to have the chance to take part when I was at school, and this year I’ve been leading the training for the UK team to take part in the IMO in Chiang Mai, Thailand. The following report, which tries to offer a light-hearted account of the range of things which happen at this sort of competition and during the final stages of our preparation.

Tuesday 30th June

It’s the hottest day of the year in the UK. Transporting 25kg of blazers and polo shirts through central London lives up to my expectations, but at least there is news of the ‘wrong type of heat’ for the rails of the Heathrow Connect to provide comic relief. Our flight to Kuala Lumpur is surprisingly cold, but uneventful. Something’s not working with my screen, so I watch the second half of The Imitation Game, and then the first half, before giving in to my end-of-term sleep debt for far longer than planned, probably infuriating those members of the group unable to find rest on flights.

Wednesday 1st July

Confusingly in equal measure to those who have slept and those who haven’t, it’s evening in humid Malaysia. The nine members of our group are met by a minibus designed for six people. Jill and Lawrence act as human suitcase barriers while Joe has to squeeze around the gear-stick, a device not frequently required in the KL rush hour. Our home for the next week is Putrajaya, a planned city between KL and the airport, characterised by stalled construction projects, and giant but under-used snaking highways. The endless roundabouts and rumble strips evoke fond memories of journeys on the X5 through Milton Keynes. This is one of the cheapest places in the world for five-star hotels, on account of a perhaps predictable disparity between optimistic supply and negligible demand.

Our initial impressions of the international school are much more positive, with beautiful grounds, and a well-equipped boarding block, with an absurd abundance of giant beanbags. Alison, the headteacher, welcomes us and directs us towards a Malaysian restaurant where the satay is generous, and the curry laksa fiery enough even for Geoff’s exacting taste. The students seem to have exhausted their mathematical appetites with trig exercises on the plane, so content themselves with cards and the school’s interesting (and nostalgic for some) collection of late-90s video games, while trying to guess how bad their jetlag will be tomorrow.

Thursday 2nd July

The UK adults seem to have slept for about four hours combined, so the theme of the day is coffee. After a leisurely start, we’re off for a tour of Putrajaya, a city of pink mosques and white elephants. While we wait, some of the team try to do the entire geometry section of the 2000 IMO shortlist using areal co-ordinates. I side with Warren regarding contempt for such methods, but it passes the time, though Sam and Neel also take the opportunity to make friends with a parrot, following Geoff’s extensive introduction to Asian ornithology.

Our boat trip around the man-made lake features an inaudible commentary about the waterside buildings, whose architecture combines Space Age with classical Islamic style very strikingly. The sequence of not-quite-complete bridges is crying out to be turned into an Euler-esque networks problem. After an infinite volume of Chinese seafood, the team leave Geoff and Jill to digest and explore further on foot. We do finally find the giant cenotaph-like sundial at the centre of the botanical gardens but even among this sizeable group of mathematicians, only Harvey is able to work out how to interpret it correctly.

Geoff concludes the afternoon by delivering a session on ‘the power of Power of a Point’, though wastes the opportunity for a triple pun by using the whiteboard rather than Powerpoint. Meanwhile, the Australians have arrived, and shortly there are new faces to meet and lots of catching up to attend to.

Friday 3rd July

We’re up early for the start of business proper, our first practice exam. The IMO takes place over two days, and on each day the students sit an exam lasting 4.5 hours with three questions. The first question each day should be accessible to all the contestants, while the third question is supposed to be very taxing, and normally at most a handful of the several hundred students achieve a full score. For the next five days, our two teams will be tackling a paper of this kind each morning.

4.5 hours is a long time, and we’ve arranged for refreshments. A curious bright green cake arrives, along with apple and aloe vera juice, for those who like the fresh taste of fruit to be accompanied by the fresh aroma of baby wipes. Meanwhile Geoff heads off to Thailand to join the other leaders and begin the process of setting this year’s IMO papers.

So I have an afternoon of solo marking lined up, which isn’t as bad as it might sound, since the UK team are off to an excellent start, in particular offering a delightful range of classical, inversive and trigonometric solutions to a geometry problem. Most of them have enough time to make substantial progress through the final question concerning polynomials and cope fine with the analytic aspects, despite the fact that they won’t meet any of this material properly until university. We only need a brief discussion of each other’s solutions before dinner, which rather descends into a contest to eat the largest number of ribs. Australian Alex Gunning already has two IMO gold medals, but I’m sure he relishes equally earning the victor ludorum title here too.

ISL14 N6 – Sums of Squares of Intervals

Posted on May 27, 2015 by dominicyeo

I wasn’t able to post this at the time because of the embargo on discussing this particular question until the end of IMO 2015.

I’m currently enjoying the slow descent into summer in the delightful surroundings of Tonbridge School where we are holding our final camp to select the UK team for this year’s IMO. The mechanism for this selection is a series of four exams following the format of the IMO itself. We take many of the questions for these tests from the shortlist of questions proposed but not used at the previous year’s competition. In this post, I’m going to talk about one of these questions. Obviously, since lots of other countries do the same thing, there is an embargo on publication or public-facing discussion of these problems until after the next competition, so this won’t appear for a couple of months.

The statement of the problem is the following:

IMO Shortlist 2014, N6: Let $a_1<a_2<\ldots<a_n$ be pairwise coprime positive integers with $a_1$ a prime at least $n+2$ . On the segment $I=[0,a_1a_2\ldots a_n]$ of the real line, mark all integers that are divisible by at least one of the numbers $a_1,\ldots,a_n$ . These points split I into a number of smaller segments. Prove that the sum of the squares of the lengths of these segments is divisible by $a_1$ .

I marked our students’ attempts at this problem and spoke to them about it afterwards. In particular, the official solution we were provided with, and which we photocopied and gave to our students contains some good theory and some magic. On closer inspection, the magic turns out to be unnecessary, and actually distracts a little from the theory. Anyway, this is my guided tour of the problem.

We begin with two items from the rough work that some students submitted. Someone treated the case n=2, which is not quite trivial, but not hard at all, and remarked, sensibly, that n=3 seemed to have become hard. Packaged with this was the implicit observation that for the purpose of the question posed, $a_1$ plays a completely different role to the other quantities. While this seems obvious when presented in isolation, it’s a good thing to say explicitly so that we avoid wasting time imagining symmetries which are definitely not present later. We’ll sometimes refer to $a_1$ as $p$ , whenever we are using its primality rather than its other roles.

The second idea coming out of rough work was to consider what happens when an interval gets broken into two by a ‘new point’, whatever that means. In particular, what happens to the sum of the squares of the interval lengths modulo p? The way the student had set up this procedure suggested that the calculations would be easy in the case where the point being added was a multiple of $p=a_1$ . This ended up being a red herring, because there’s no real reason why we would want to add the multiples of $a_1$ at the end.

It does, however, suggest an inductive argument, if instead you add the points which are multiples of $a_n$ , but not of any of $\{a_1,\ldots,a_{n-1}\}$ , because the latter would already be present. It might seem like induction is illegal, since there is the condition $a_1\ge n+2$ already present in the statement. However, once $a_1$ is fixed, if the condition holds for a particular n, then clearly it holds for all smaller n (!), and so we can use induction to build up to the value of n required in the statement.

Now we are happy this might work in principle, let’s do it in practice. We are adding all these multiples of $a_n$ so we want to have some way to index them. One choice is to use their actual values, or the quotient by $a_n$ , ie all the integers up to $\prod_{i=1}^{n-1}a_i$ which are coprime to $a_n$ . But maybe after thinking about it, there will be a more helpful way to index them.

We are only interested in non-trivial splittings of intervals. We might initially be concerned that an existing interval might be split into more than two sub-intervals by the addition of the multiples of $a_n$ , but the ordering suggested in the statement means this can’t happen. In general, let the initial size of the interval be K, and the sizes of the two sub-intervals be x and y for reasons which will become clear. Then the change in contribution to the total sum of interval lengths squared is given by

$K^2 \quad \mapsto \quad x^2+y^2= K^2 - 2xy,$

using that $K=x+y$ . So the total change when we add all the multiples of $a_{n}$ will be the sum of $2xy$ over all the intervals which get divided into two.

Now we have the challenge of evaluating this sum, or at least showing that it is divisible by p. Given a multiple $a$ of $a_1$ , what will x be?

Well, on the left of $a$ , the distance to the nearest multiple of $a_k$ is the remainder $r_k$ of $a$ on division by $a_k$ , essentially by definition. So x will be the minimal such remainder as k varies. Similarly, y will be $\min_k (a_k-r_k)$ . We forget about the minus sign and the factor of 2 forever, since it doesn’t make any difference unless p=2, in which case we are already done, and so we now have our sum:

$\sum_{a\text{ a new multiples of }a_n} \left( \min_i(r_i)\right) \left[ \min_j(a_j-r_j) \right].$

Now we return to the question of how to index the new multiples of $a_n$ . But the question’s easier now as we have some clues as to what might be useful. Each of the summands involves the remainders modulo the smaller $a_i$ s, so can we use these as part of the indexing?

Yes, of course we can. There’s a bijection between the possible sequences of remainders, and the new multiples of $a_n$ . This is basically the statement of the Chinese Remainder Theorem. Our index set should then be

$r_1,\ldots,r_{n-1} \in [1,a_1-1]\times\ldots\times [1,a_{n-1}-1].$

Remember that the fact that they are not allowed to be zero is because we only care now about new points being added.

Even now though, it’s not obvious how to compute this sum, so the natural thing to try is to invert our view of what we are summing over. That is, to consider how many of the index sequences result in particular values of x and y. Given x and y at least one, each remainder $r_k$ must lie in $[x,a_k-y]$ , ie there are $a_i-(x+y)+1$ values it is allowed to take. So our guess for the number of such indices might be $\prod_{i=1}^{n-1} (a_i-(x+y)+1)$ , which is indeed what I wrote up on the board before Neel pointed out that some of the sequences I’ve allowed do not actually attain this minimum.

Fortunately this is easily fixed. If the minimum for x is not attained, we know that $r_k\in[x+1,a_k-y],$ and similarly for y. So we can apply the inclusion-exclusion principle to depth two to say that the number we actually want is

$\prod_{i=1}^{n-1} (a_i-(x+y)+1) - 2\prod_{i=1}^{n-1} (a_i-(x+y)) + \prod_{i=1}^{n-1} (a_i-(x+y)-1).$

This is a polynomial in (x+y), so we’ll call in P(x+y). We’ll come back to this expression. We still need to tidy up our overall sum, in particular by deciding what bounds we want on x and y. Thinking about the intervals of width p, it is clear that the bounds should be $1\le x,y$ and $x+y\le p$ . So we currently have our sum as

$\sum_{1\le x,y,\,x+y\le p} xy P(x+y),.$

If you’ve got to this stage, I hope you would feel that this seems really promising. You’ve got to show that some sum of polynomial-like things over a reasonably well-behaved index set is divisible by p. If you don’t know general theorems that might confirm that this is true, once you’ve got statements like this, you might well guess then verify their existence.

First though, we need to split up this xy term, since our sum is really now all about x+y, which we’ll call z.

$\sum_{2\le z\le p} P(z) \sum_{x+y=z,x,y\ge 1} xy.$

Once we’ve had our thought that we mainly care about polynomials mod p at this stage, we might even save ourselves some work and just observe that $\sum_{x+y=z}xy$ is a cubic in z. This is definitely not hard to check, using the formulae for triangle numbers and sums of squares. It’s also reasonable to conclude that the value of this is 0 for z=1, so we can change the indices on the sum so it doesn’t look like we’re missing a term. So we have

$\sum_{z=1}^p P(z) Q(z),$

where Q is some cubic, which we could work out if we really wanted to. But what’s the degree of P? P is made of a sum of 3 polynomials whose degree is clear because they are a product of linear factors. So each of these has degree (n-1), but in fact we can clearly see that the leading term cancels, and also with a tiny bit more care that the second order terms cancel too, so P has degree at most n-3.

[Tangent: students might well ask why it is convention to take the degree of the identically zero polynomial to be $-\infty$ rather than zero. The fact that the above statement is true even when n=2 is a good justification for this.]

[Tangent 2: In my initially erroneous evaluation of the number of remainder sequences, without the inclusion-exclusion argument, I indeed ended up with P having degree n-1. I also worked out Q as being quadratic though, so my overall necessary condition was only one off from what was required, showing that two wrongs are not as good as two rights, but marginally better than only one wrong.]

Anyway, we are taking a sum of polynomials of degree at most $n \le p-2$ . This is the point where one might get confused if you have been specifying everything in too much detail. The fact that I’ve said nothing about the polynomials apart from their degree is predicated on the fact that I now know I only need to only their degrees for what I want, but even if you had tracked everything very explicitly, you might still guess what to do at this stage.

It’s presented as a lemma in the official solution that if you have a polynomial of degree at most p-2, then $\sum_{z=1}^p P(z)\equiv 0$ modulo p. There are several ways to see this, of which a proof by induction is easiest to believe, but probably least intuitive. It’s clear what goes wrong for degree p-1 by FLT, so you probably want to look at the set $\{z^k: z\in[1,p-1]\}$ modulo p. It won’t necessarily be all the residues modulo p, but thinking about primitive roots, or the roots of unity makes it fairly clear why this would be true. [Essentially any argument that turns multiplication into addition in a well-behaved way clears this up.]

The most important point is that this lemma is a) easy-ish and b) a natural thing to try given where you might have got in the question at this stage. From here you’re now basically done.

I don’t think this is an easy question at all, since even with lots of guiding through the steps there are a lot of tangents one might get drawn down, especially investigating exact forms of polynomials which it turns out we only need vague information about. Nonetheless, there are lots of lessons to be learned from the argument, which definitely makes it a good question at this level in my opinion.

EGMO 2015

Posted on April 21, 2015 by dominicyeo

It’s been a while since I last wrote anything substantial. There have been some posts in the pipeline, but mainly I’ve been working hard on technical things that don’t translate very well into blog posts, and when I haven’t been working on those, have felt like doing non-maths.

Anyway, among other things which happened recently were the UK’s IMO selection camp in Cambridge during the last week of March, and the fourth European Girls’ Mathematical Olympiad in Belarus this past weekend. At the former, I was quite busy organising various things, and so gave a session based on some of my favourite problems about points and lines that I’ve used in the past. My hope was that with each problem in turn the students would actively invest time in thinking about whether the ideas each other were having seemed likely to be profitable. The aim was that being critical about your approach is a necessary skill once you start having lots of ideas for approaches.

This is hard to practise at school just by reading around, whether regarding competition material or generally. In the competition world, official solutions often contain unmotivated magic. This is reasonable, since they are supposed to be a minimal elementary demonstration of the problem’s validity. Motivation is a luxury which space and time sometimes doesn’t permit. And the solutions you find on, for example, Mathlinks often give the impression that the solvers know how to do 25,000 specific types of problem, and the sole task is to identify which type the latest one belongs to. Relating problems to ones you’ve seen before is important, but can hide, or at least dilute the actual ideas in some cases. Knowing that a specific inequality is a special case of a big machine allows you to claim a ‘solution’ but doesn’t help you identify the relevant ideas.

Later in the camp, a conversation arose concerning to what extent the younger staff found these elementary methods and problems easier now that they had experienced various levels of higher education in mathematics than when they were at school. It’s a complicated question, and I don’t think there’s a simple answer. I think the students might suspect that doing a university degree teaches you ‘advanced techniques’ which immediately simplify some of these problems. In rare examples this can be the case, but the majority of the time, I personally feel the only advantage I have is perhaps better instincts for whether something is or isn’t going to work.

Probably a good test would be Euclidean geometry. Adult olympiad staff typically come in two flavours: those who used to be good at geometry and feel out of practice; and those who weren’t good at geometry and certainly had no inclination to remedy this after they left school. I’m probably closer to the first category and I definitely feel out of practice, but also have minimal inclination to remedy this. Nonetheless, on the rare occasions I try these questions (and it’s not going to be for 4.5 hours at this stage…) my progress rate is probably comparable to when I was in sixth form. I’ve no idea how to turn this into a more concrete assessment, but there must be something about doing abstract maths all the time that prevents you forgetting how to do this, so presumably it should be at least as helpful in the types of problem with non-zero overlap with things I actually do. I won’t discuss geometry in the rest of this post, but I did also enjoy the geometry questions – it’s simply that I feel anything I have to say about them would be less useful than saying nothing.

In any case, I enjoyed trying the problems from Belarus in between bouts of typing, and thought I would write some brief comments about how I decided whether my ideas were good or not. To achieve this, I’ve looked at my rough, and will tell you the ideas which didn’t work, as well as some of the ones which did. I’ve paraphrased the statements slightly to avoid having too many LaTeX tags.

WARNING: what follows will spoil questions {2,4,5} if you haven’t already looked at them, but would like to.

Question 2 – A domino is a 2 × 1 or 1 × 2 tile. Determine in how many ways exactly n^2 dominoes can be placed without overlapping on a 2n × 2n chessboard so that every 2 × 2 square contains at least two uncovered unit squares which lie in the same row or column.

The wording of the question prompted me to consider splitting the board naturally into n^2 2 x 2 squares. I then thought about this ‘at least’ in the question, and concluded that for these 2 x 2 squares, it should be ‘exactly’.

I tried doing an unusual colouring, when I coloured half the black squares green, and half blue and tried to show that either only greens or only blues were covered, but this was clearly not true, or fixable. I then tried to do something similar for the other set of 2 x 2 squares (those whose vertices have (odd, odd) coordinates). Roughly speaking, if too few of the outer cells on the original board are covered, you can’t achieve the bounds on these odd inner squares. But this didn’t really give any useful information.

However, it did get me thinking about how what happens in the far top-left affects the rest of the board, and from there most of the ideas came quickly. I described a 2 x 2 square as N, E, S, W depending on which ‘half’ of the square was covered. Then if a square is N, all the squares directly above it must be also be N (*).

I then made two mistakes, and if we’re looking for reasons where experience is helpful, it was probably here, as I spotted them fairly quickly, rather than wasting ages and ages.

First, I decided that either all squares were {N,E} or all were {S,W} which seemed plausible when I had been focusing on the top-left. This gave an answer of $2 \binom{2n}{n}$ , but after a bit more thought is clearly not symmetric enough.

Second, I thought condition (*) might be the only constraint, along with similar ones for E, S, W naturally too. I tried to count these using a similar method of enumerating lines between these regions, and I realised I didn’t know how to do these sensibly, for example if it looked like this:

This led to another bit of meta-maths that I probably wouldn’t have considered if I was 16. Namely, that the idea of counting these monotone lines across the 2n x 2n grid was too nice not to be useful. Also, if I couldn’t see a way to adapt it for this more complicated setup, my setup was probably wrong. This thought was useful, and then by thinking about the interface between {N,E} and {S,W}, then the other way round, it made sense that the configuration could be parameterised by two monotone lines between different pairs of corners, giving an answer of $\binom{2n}{n}^2$ .

So, if it’s possible to give a reason why I could do this, it’s probably because I had an arsenal of ways to check an answer for plausibility, which saved wasting time on something wrong, and also because I trusted that the answer would be nice, which saved wasting time on something which was also wrong, and would probably have been very complicated to resolve.

Question 4 – Determine whether there exists an infinite sequence $a_1,a_2,\ldots$ of positive integers satisfying $a_{n+2}=a_{n+1}+\sqrt{a_{n+1}+a_n}$ .

So, my first reaction was ‘no way’. Why? Because everything’s determined by the first two terms, and I couldn’t think of any reason why a cool choice of the first two terms would force all of the sums $a_{n+1}+a_n$ to be perfect squares. It seemed just about possible that we could arbitrarily large finite sequences with this property. (Though this also turns out to be impossible.)

I imagine many contestants might have felt similarly and spent a while playing round with quadratic residues to get a sense for exactly how hard it is to make this work for the initial terms. But I was suspicious of the form of the recurrence. We know that if it had been defined linearly, then the terms would grow exponentially, but it’s natural to ask roughly how fast they grow in this example, even relaxing the restriction that the terms be integers.

The first observation was that they are indeed (strictly) growing! But how fast? Are there actually enough squares that every $a_{n+1}+a_n$ can be a different one? Note that the squares themselves satisfy a similar recurrence relation $(N+1)^2 = N^2 + 2\sqrt{N^2} + 1 > N^2 + \sqrt{ N^2 + N^2}$ . So this seemed like a very good idea, and my instinct was that this should work, and I felt glad that I hadn’t pursued the quadratic residues approach.

From here we were basically home. I asked whether the sequence grows faster than the sequence $(\frac{n^2}{2})$ , and the answer was no as

$a_{n+2}\le a_{n+1}+ \sqrt{2 a_{n+1}} \le (\sqrt{a_{n=1}} + \frac{1}{\sqrt 2})^2,$

so if (after translating indices) $a_n = \frac{x^2}{2}$ , we have $a_{n+1}\le \frac{(x+1)^2}{2}$ . This is clearly a problem or at best a very tight constraint if all the $\{a_n+a_{n+1}\}$ have to be perfect squares, so even though we aren’t completely finished, I am confident I can be in one or two lines, with a bit of care. Fiddling with small values of n looked like it would work, or showing that looking at a large enough initial subsequence that the effect of the first two terms dissipated, we must by the pigeonhole principle have $a_{n+2}+a_{n+1}=(k+1)^2,\, a_{n+1}+a_n=k^2$ , which is enough by a parity argument, using the original statement.

This final bit looks and feels a bit messy, but by this stage it really is just finding any argument to justify why a sequence which grows at most as fast as $n^2$ can’t actually be $n^2$ eventually.

Probably the reason I did this quickly was because I trusted my instinct for ‘no’, and also because there seemed a quick way to qualify *roughly* how this sequence grew. Sensibly approximating things, and deciding whether it’s appropriate to approximate them is definitely something I feel I’ve got better at during my PhD, so I guess this was helpful, then just try and throw back the important condition that the elements were integers at the very end.

Question 5 – Anastasia partitions the integers [1,2m] into pairs. Boris tries to choose one integer from each pair so that the sum is n. Given n and m, prove Anastasia can select pairs so that Boris can’t succeed.

So I wasted some thought time by imagining that n was fixed and trying to come up with ideas for the choice of pairs which might avoid n. It struck me that there was no reason why a a typical (uniformly chosen) pairing should avoid any particular n unless this value was particularly big or small.

How big or how small? Well Boris can always choose the bigger element of a pair, so the way to make the minimum maximum is to pair as (1,2), (3,4), … , (2m-1,2m). Conveniently, this also achieves the maximum minimum. These can be calculated as $m^2,m(m+1)$ respectively. Suddenly this seems great, because we’ve actually solved the problem for a huge range of n, ie everything not within between these extrema.

The key step here was to start considering special pairings, chosen to give a reduced set of possible sums. Once we’ve had this idea, it makes sense to consider other different special pairings. The reason we got a small set of possible sums is that there’s lots of overlap. We can achieve lots of overlap by looking at the difference between elements in a pair, and making as many of these the same as possible. For, consider pairs (a,a+d), (b,b+d). Then it’s the same to take a and b+d as to take a+d and b, so we get the same sums in lots of different ways.

The other way to have as many differences the same as possible is to go for (1,m+1), (2,m+2), … , (m,2m). Conveniently, we can parameterise the sums now because at each choice, we decide whether to add an extra m or not, so the sum must be 1+2+…+m, plus some multiple of m. So we can defeat Boris, except when n is $\binom{m}{2}+km$ .

This is a good point to stop because what followed was basically book-keeping. We only have to consider a couple of specific cases when m is odd, and one when m is even, that happen not to fall into either of the categories we can now deal with. It wasn’t too hard to corrupt the examples we already have to deal with these.

The key here was responding to initial failure by trying to find any control at all over n. Perhaps given enough time I would have started trying special pairings? Equally, I might have tried small examples, which would not really have been hugely helpful for this question. In any case, trying to eliminate very small or very large n luckily worked well, as a) I didn’t need to use the word ‘very’ twice in the end; and b) the idea of looking at choices of pairings to minimise the number of sums quickly gave other useful deductions.

I also really enjoyed Question 3, though was suspicious that I’d used a bound a great deal weaker than one in the question. Along the way, I was trying something confusing and not especially useful that led me into some interesting theory about Latin squares, which I might write something about later in the week.

Sharpness of Phase Transition in Percolation

Posted on March 15, 2015 by dominicyeo

On the flight to Romania a couple of weeks ago, I read this very nice paper by Duminil-Copin and Tassion in which, as a corollary to a more general result in a companion paper, they provide a short proof of a result about percolation on $\mathbb{Z}^d$ . Mitch talked about this paper at our final Junior Probability Seminar of this term yesterday, so it seemed appropriate to write up something about this nice argument. I must confess I know relatively little about these problems, and in particular know nothing about how the original authors, Aizenmann + Barsky (1987), and Menshikov (1986) approached this problem, but experts have said that this is substantially easier to digest.

Rather than reference the first paper repeatedly, I remark now that everything which follows comes from there.

We consider conventional bond percolation on the edges of $\mathbb{Z}^d$ , for $d\ge 2$ , and are interested in whether the the origin percolates with positive probability. That is, that zero is contained in an infinite component. As usual we define $p_c=\sup\{p: \mathbb{P}_p(0\leftrightarrow\infty)=0\}$ to be the critical probability above which percolation happens with positive probability. Defining $\theta(p)=\mathbb{P}_p(0\leftrightarrow\infty)$ , we do not know whether $\theta(p_c)=0$ for some values of d, notably d=3.

If the origin is connected to infinity, it is by definition connected to the boundary of every $\Lambda_n:=[-n,n]^d$ . The number of distinct paths from the origin to $\partial \Lambda_n$ is bounded by the number of self-avoiding walks on the lattice of length n starting from 0, which grows at most as fast as $(2d-1)^n$ . In particular, we know that $p_c\ge \frac{1}{2d-1}$ , but also, for any $p<\frac{1}{2d-1}$ , the probability $\mathbb{P}_p[0\leftrightarrow \partial\Lambda_n]$ decays exponentially in n. We would expect this in fact to hold for all $p<p_c$ , and this is something that the authors prove, called Item 1. They also show that the percolation probability grows at least linearly beyond $p_c$ , specifically (called Item 2)

$\theta(p)\ge \frac{p-p_c}{p(1-p_c)}.$

The proof here proceeds by considering the function of subsets S which contain the origin:

$\varphi_p(S):= p\sum_{(x,y)\in\Delta S} \mathbb{P}_p[0\stackrel{S}{\leftrightarrow} x],\quad S\subset \mathbb{Z}^d$ .

In words, this gives the expected number of edges across the boundary which are connected to the origin by a path within S. So this gives a measure of how likely we are to escape S, and in particular, an upper bound on the probability that an open path exists from 0 to outside S. The authors then define the alternative critical probability

$\tilde p_c := \sup_\{p\text{ s.t. }\exists\text{ finite }0\in S\text{ with }\varphi_p(S)<1\}.$

They will show that $\tilde p_c$ satisfies the statements of both Item 1 and Item 2. Item 2 for $\tilde p_c$ implies $\tilde p_c\le p_c$ , and Item 1 for $\tilde p_c$ implies $p_c\le \tilde p_c$ , so this is exactly what we need.

They show Item 1 first. We consider this set S for which $\varphi_p(S)<1$ , and take some box $\Lambda_L$ which strictly contains S. Now we consider the probability of escaping from a box of size kL. The reason why considering this definition of S works really nicely is that it makes it possible to split this event of escaping from $\Lambda_{kL}$ into an event involving subjects of various disjoint sets of edges being open, so we can use independence.

We decompose the path from 0 to $\partial\Lambda_{kL}$ based on the first time it leaves S. We are mindful that there might be lots of paths from from 0 to this boundary. The way we are bounding means it doesn’t matter if we have lots of suitable paths, but they should all spend a maximal number of steps in S, in the sense that whenever the path re-enters S, say to vertex z, there is no open path from 0 to z contained in S. Let the vertex on $\partial S$ we leave from for the first time be x. Then, for all vertices y later in the path, $0\stackrel{S}{\not\leftrightarrow}y$ .

So under any suitable path, now take y to be the vertex directly following x, hence $(x,y)\in\Delta S$ . If we take $\mathcal{C}$ to be the set of vertices z for which $0\stackrel{S}{\leftrightarrow}z$ , we can split the expression based on S to obtain:

$\mathbb{P}_p[0\leftrightarrow \partial \Lambda_{kL}]\le p \sum_{(x,y)\in\Delta S}\sum_{C\subset S} \mathbb{P}_p[0\stackrel{S}{\leftrightarrow} x,\mathcal{C}=C] \mathbb{P}_p[y\stackrel{\mathbb{Z}^d\backslash C}{\leftrightarrow}\partial\Lambda_{kL}].$

Splitting based on C gives us independence between all of these sets of edges, but then we immediately forget about it. Irrespective of choice of y (recall, $y\in S\subset \Lambda_L$ ), this final probability is definitely bounded by $\mathbb{P}_p[0\leftrightarrow \partial \Lambda_{(k-1)L}]$ , while the p and the first term can be summed over C to give $\varphi_p(S)$ . They obtain:

$\mathbb{P}_p[0\leftrightarrow \partial \Lambda_{kL}] \le \varphi_p(S)\mathbb{P}_p[y\leftrightarrow \partial \Lambda_{(k-1)L}] \le \varphi_p(S)^{k-1},$

where the final relation holds by induction, and clearly gives exponential decay as required.

For Item 2 we use Russo’s formula. Here we have a slightly simpler example than the most general version, since the event under consideration $A_n=\{0\leftrightarrow \partial\Lambda_n\}$ is increasing with respect to adding edges. It is also a function of a finite number of edges. Then we can consider $\frac{d}{dp}\mathbb{P}_p[A]$ under the coupling which adds each edge independently as a Poisson process with (locally) rate $\frac{1}{1-t}$ . (We take this to be the rate to avoid having to reparameterise exponentially between time and probability. Here t=p.)

Just for ease, we only consider the right-derivative at p. Then with $\mathbb{P}$ as the law of the coupled process:

$\frac{d}{dp}\mathbb{P}_p[A] \approx \frac{1}{\epsilon} \mathbb{P}[A\text{ holds at }p+\epsilon,\text{ but not at }p]$

$= \frac{1}{\epsilon} \sum_{e\in E}\mathbb{P}[e\text{ added between }p,p+\epsilon\text{ and }e\text{ completes event }A]$

$+ \frac{1}{\epsilon}\mathbb{P}[\text{two or more edges relevant to }A\text{ added}].$

Since the number of edges whose states determine A is finite, this second term vanishes as $\epsilon\rightarrow 0$ . So

$=\frac{1}{\epsilon}\sum \frac{\epsilon}{1-p} \mathbb{P}(A \text{ doesn't hold at p, and edge }e\text{ pivotal at p}).$

Taking the limit in $\epsilon$ in this example gives

$\frac{d}{dp}\mathbb{P}_p[0\leftrightarrow \partial\Lambda_n] = \frac{1}{1-p} \sum_{e\in\Lambda_n} \mathbb{P}_p[e\text{ pivotal, }0\not\leftrightarrow \partial \Lambda_n].$

The argument then proceeds in a similar way to Item 1, decomposing $\{0\not\leftrightarrow \partial \Lambda_n\}$ by conditioning on the set of vertices $\mathcal{S}$ from which it is not possible to get to $\partial \Lambda_n$ . In particular, this set is an excellent candidate to view as S, since on this event it contains 0 by definition. Once we have specified $\mathcal{S}$ we know which edges might be pivotal, namely those across the boundary of $\mathcal{S}$ . Crucially, the event $\{\mathcal{S}=S\}$ only depends on those edges between the boundary of S and $\partial \Lambda_n$ , so is independent of the event $\{0\stackrel{S}{\leftrightarrow}x\}$ whenever $x\in\partial \mathcal{S}$ . So applying this version of Russo gives

$\frac{d}{dp}\mathbb{P}_p[0\leftrightarrow \partial\Lambda_n] = \frac{1}{1-p}\sum_{0\in S\subset \Lambda_n} \sum_{(x,y)\in\Delta S} \mathbb{P}_p[0\stackrel{S}{\leftrightarrow} x]\mathbb{P}_p[\mathcal{S}=S].$

It is clear where $\varphi_p(S)$ might turn up within the sum (after removing a factor of p), so for a bound we can take $\inf_S \varphi_p(S)$ outside the sum, and arrive at

$\frac{d}{dp}\mathbb{P}_p[0\leftrightarrow \partial\Lambda_n] \ge \frac{1}{p(1-p)}\inf_{0\in S\subset \Lambda_n} (1-\mathbb{P}_p[0\leftrightarrow \partial \Lambda_n].$

It wasn’t immediately clear to me immediately that this implied the given form of Item 2 (though it certainly is consistent). I think perhaps I was trying to be too complicated and thinking about Gronwall’s lemma when in fact everything really follows from bounding $\inf \varphi_p(S)$ below by 1 (since we have assumed $p>\tilde p_c$ here), then integrating the differential inequality

$\frac{d}{dp}\left[ \frac{p}{1-p}f(p) \right] = \frac{p}{1-p}f'(p)+\frac{1}{(1-p)^2}f(p) \ge \frac{1}{(1-p)^2}.$

I include this not because it’s an interesting part of the argument (I don’t think it is really) but because I struggled to digest it first time round.

What is interesting is how well this choice to consider $\varphi_p(S)$ works out. In both parts of the argument, sets which work well for splitting the crossing probabilities into disjoint edge events mesh nicely with considering this function after conditioning on sub- or super-criticality with respect to $\tilde p_c$ .

Eventually Almost Everywhere

A blog about probability and olympiads by Dominic Yeo