RMM 2017 – UK Team Blog

This is the customary and slightly frivolous account of a trip to Bucharest for the ninth edition of the Romanian Master of Mathematics, an annual competition for school students, widely recognised as the hardest of its kind.

I discuss the problems in two previous posts (here and here), and there is also a pdf with fewer pictures, which includes both the discussion and this diary, as well as some more formal comments about the competition itself, the results, and thanks.

Wednesday 22 February

Did you know that trains in Moldova use different width tracks to trains in Romania? Well, I didn’t know either, but I found out at 1am today, as my wagon lit from Chisinau was painstakingly jacked up to allow the transfer from ex-Soviet gauge to Western gauge. Outside, a man in a smart uniform and epaulettes shouted loudly and continuously at a group of men in smart uniforms without epaulattes. When their task was done, four sets of border and custom checks remained before the opportunity for another visit to the samovar, and finally a chance to sleep.

All of which is to say that I have arrived at maths competitions in better mental shape than 6am today at Gara de Nord. The UK students have a more conventional itinerary, but their flight from Luton doesn’t arrive until mid-afternoon. After my first Haifa ‘winter’, I’m craving pork and snow, and find both in the mountain town of Sinaia, an hour away by train in Transylvania. I also find a bear. The bear seems very scared.

I return in time to meet the UK students as well as James and MT. Some of our contestants are now into their fourth year of attending international competitions, and the labour of finding them fresh material resembles Hercules against the hydra, but some problems on combinatorial geometry with convexity seem to have kept everyone entertained on the flight. Dinner is at the Moxa campus of the University of Economics, and features chicken with one of two possible carbohydrates, as in fact do the next six meals. However, today is Thomas’s 18th birthday, and so his parents have arranged a delicious cake, which elicits considerably more enthusiasm. On the short walk back to our meeting, we notice it is possible both to buy fireworks and get a tattoo among other options, so Thomas is spoiled for choice about how to take advantage of his majority.

The team’s activities remain a mystery to James and me though, as we have to join the other leaders for the first meeting, to receive the proposed problems. We spend some time thinking about them separately then together, and our initial impression is that it’s a very suitable paper, that hopefully our team will enjoy.

Thursday 23 February

The leaders meet to finalise the choice and statement of the problems. With a bit more time this morning, I’ve solved Q1, Q2, Q5, and proved Q3 once I’d looked up the correct bound. James eats conics for breakfast and shows me a glorious range of interpretations of Q4. We feel happy that our students will have a chance at all of these, while Q6 may prove more restricting. Either way, it’s clearly an appropriate set for this competition, and is approved quickly. So it’s time to finalise the English version of the paper, or finalize the American version. Many alternatives to the word sieve are proposed. Andrea from Italy is clearly already craving home comforts, but his suggestion of cheese grater is not taken up. This time I’m sorting the LaTeX, so get to settle the commas, but also take the blame for inconsistently spacing the rubric between the two papers. I’m sure everyone noticed.

While all this has been happening, the students have been at a lecture by Sergiu Moroianu at the Institute of Mathematics. Joe Benton gives an account of what they learned in the longer pdf version of this report.

For all the charms of Chipping Norton, I sense MT is enjoying the grittier nature of Bucharest Sector 1, and has been shepherding the students round various sites in between attempts at practice problems. I join them for a brief visit to a geology museum. I am very cynical, but it slightly exceeds my expectations, and is infinitely better than the nearby Museum of the Romanian Peasant, which currently ties with the Hanoi Ethnology Museum as my least favourite olympiad excursion of all time.

The opening ceremony is held in the grand hall of the university, and includes several welcoming and thoughtful speeches from the Mayor of Bucharest and the headteacher of Tudor Vianu, the school which hosts this competition every year. Each team briefly presents themselves on stage. Joe and Neel have accumulated a large collection of UK flags from previous competitions, and should hereby consider themselves publicly shamed for forgetting their promise to bring them. It is over soon, and while the students enjoy a quiet evening and an early night, the leaders have to finalise markschemes for all the problems. The walk back takes us through Victory Square, and past the protesters whose fires and slogans have been on front pages around the world in the past months. It’s an interesting time, and the atmosphere of this city feels very different from my first visit, for the inaugural edition of this competition in 2008.

Friday 24 February

The first day of the contest starts at 9am. The British students seem fairly relaxed, and hopefully are aiming high. Contestants may ask questions of clarification during the first 30 minutes. Rosie does this, and I send my reply to her two queries back via the courier. Five minutes later it is returned to me with the explanation that the student does not understand the answer. Even under competition pressure this seems unlikely, given that my answers are, respectively ‘yes’, and putting a ring around one of three options she has listed. It turns out that actually the student courier did not understand what to do with the answer, and the situation is quickly corrected.

We approve more markschemes. The US deputy leader Po-Shen and I share our views on the challenge of correctly finding the bound in Q3, and our suggestion that this instead be worth 2 points is upheld. Various further discussions fill the morning, and we return just in time to meet the students at the end of the exam. Harvey claims all three problems with a relaxed grin, while Joe claims all three problems with the haunted look of a man whose twelfth espresso of the day has just worn off. Alexander and Thomas say that they spent most of the time making sure their solutions to Q1 were totally watertight, which, given the intricacy of the arguments, was clearly a very sensible strategy.

To provide a distraction, if not actually a break from time-pressured problem-solving, I’ve booked a pair of escape rooms for the UK students later in the afternoon. Bucharest is the home of these games, where the aim is to solve themed puzzles as part of a story in time to escape a locked room. I join one of the rooms, where there are some theatrical reveals involving wrenches, and clues hidden in combination-locked cabinets, where ability to add three-digit numbers proves useful. Someone’s carrying voice means we get to enjoy some of the drama and twists of the other room too. Anyway, this proved an ideal way to avoid useless post-mortems, and I highly recommend Vlad and his pair of rooms.

Later, James and I get to look at the students’ work from this morning. Their assessments are pretty accurate. Harvey’s solutions to everything are beautiful, while Neel’s bounding argument in Q2 is certainly the most vulgar (and, in fact, unnecessary) calculation of the year so far. Joe’s solution to Q3 bears such obvious resemblence to an official solution that his uncharacteristic abundance of small errors probably won’t matter, including the memorable set A_i\backslash\{i\}, where the two is mean different things. Some of the team might reflect that a moment of casualness in checking the n=2 case on Q2 is a frustrating way to lose a potential mark, but when I compare notes with James, it sounds like the slow and steady approach to Q1 has indeed paid off for everyone, so hopefully it will not be too painful to agree the scores tomorrow.

Saturday 25 February

It’s the second day of the competition, and the UK team look bright-eyed and positive at breakfast. They aren’t the only ones under pressure this morning, as James and I must settle the scores from yesterday’s questions with local markers, known as coordinators. It’s hard to guess in how much detail one will have to explain your contestants’ scripts, so it is safer to prepare almost line-by-line. On this occasion though, perhaps we have over-prepared, as every meeting ends quickly with offers of 7/7 exactly where we were hoping, and indeed in a couple of places where we were not hoping. The markschemes are very clear about certain omissions which carry a point deduction, so to ensure fairness and consistency, we insist that two scores are moved down. I’m confident that any British student would prefer an honourable 41/42 than an accidental 42/42.

No-one’s going to be scoring 41 nor 42 unless they solve the extremely challenging geometry Q6, and as we meet our students afterwards, it turns out they have not managed any progress there. However, they claim an almost full set of solutions to Questions 4 and 5, which, if accurate, is a very good return. Everyone is in a good mood, and after I explain a couple of approaches to Q6, no-one seems too disappointed that they didn’t spot these.

There are various schedules floating around, listing multiple locations and times for lunch, but our space-time trajectory intersects none of them, so we follow the Chinese team to a recommended cheap Szechuan restaurant round the corner. Various circle theorems are explored via the Lazy Susan, and there is a grand reveal of the marks we’ve recently confirmed. There’s time for another pair of escape rooms while the second day scripts arrive. As Rosie remarks, two in two days can lead to excessive outside-the-box thinking. Sometimes a radiator really isn’t a sinister prop, a device for encoding five-digit numbers, or a clue to a Templar tunnel; it’s just a radiator. Otherwise we’d be cold.

When the scripts arrive, as expected the cupboard is pretty bare on Q6. If there were marks for quantity, Neel might get some, and if there were marks for most uses of esoteric theory in a single page, Alexander might get one. No set of scripts for an international-level medium combinatorics problem will ever be perfect, but our Q5s come close. It’s therefore not a long evening, and we can join the students for dinner with the American team. For most of them it’s their first visit to Europe, and there’s much comparing of culture and maths training programmes. There’s also a long discussion of whether it’s sensible to teach maths in primary school. Those present who have small children or younger siblings weigh in on the mysteries of the ‘grid method’, and whether toddlers implicitly understand commutativity, even if they can’t spell it.

Sunday 26 February

The UK leaders gather early in the ‘philosophical anti-cafe’ opposite Vianu school, to ponder the final scripts with a coffee and a view of an artfully-arranged folio of Spinoza. James has a loyalty card here. Unfortunately two of our students have clear algebraic errors in Q4, but apart from that everything is very straightforward. Though following last night’s conversation, we note that maybe a revision clinic on mathematical spelling might prove useful. Anonymous student X thinks there’s one L in ‘ellipse’, counterbalanced by anonymous student Y who thinks there are two in ‘column’. The word ‘parallel’ comes in many disguises.

Of course, the coordinators couldn’t care less about that, and they don’t even mind Neel’s two-cases-at-once inductive step, so again we get what we ask for on Q5 immediately, and on Q4 in the time it takes James to draw a lozenge tiling representing Thomas’s shearing argument. For Q6, it turns out there clearly is a mark for most uses of esoteric theory in a single page, so Alexander gets it. They show us a diagram with over a hundred lines which suggests that the exotic equivalence he claims is actually true. There we go. Overall, the quality of our written solutions has been extremely high. It feels like I say this every time now, but it isn’t idle propaganda. We remember the horrors that used to emerge occasionally, and the effort to make this improvement permanent feels well worth it.

Meanwhile, to fill the day, the students have gone to Sinaia. Two of their guides went with them to help with tickets at the station, apparently under the impression that never having taken a train before wouldn’t be an obstacle to this role. Either way, they made it, and following my request for material for this report, I receive a trickle of presentable photos, though there is talk afterwards of some rather more informal versions which are apparently not suitable. The Transylvanian winter is thawing, but slowly and messily, and Harvey reports that several of the group spent more time horizontal than vertical. Irrespective of their preferred axis, there’s no comment on whether they saw my bear, or any other bear. But since my bear was scared of me, one wonders what it would make of MT’s telling-off face? (Last seen by me during the notorious ‘balcony incident’ at a summer school in 2005, but hardly forgotten.)

The students return in time for confirmation of the results and their medals. As so often, there is pleasure that we have done so well collectively, mixed with mild disappointment for those who ended up just short of a boundary, and that the UK was so close to placing first. Because of the strength of the invited countries, earning a medal of any colour is a very worthwhile achievement, and so Rosie is impressively sanguine about missing out so narrowly in such an unfortunate manner. Alexander was closer than it appears, and could have two more opportunities to take part.

The closing ceremony at Vianu school proceeds rapidly. There is the usual challenge of photographing the students receiving their prizes, but this time is easy. Thomas is about a foot taller than everyone else on the stage, while Neel is flanked by almost the entire Russian team, but his chutzpah trumps their numerical advantage, with laughter all round. Joe claims this year’s gold medal is substantially weightier. He hasn’t brought his previous pair, so the chance to verify this and recreate a Mark Spitz moment goes begging.

It’s 7pm, and UK student enthusiasm for the closing disco (not my words) is about as high as MT’s enthusiasm to chaperone the closing disco. Instead we find a Middle Eastern restaurant, and it’s refreshing to eat hummus in a place which doesn’t claim to be the ‘best in Israel’ though I don’t think Abu Said in Akko will be rushing to steal the recipe. Po-Shen outlines his vision of a year-long maths camp. I think present company are tired enough after five days here. Some are interested to view, if not actually participate in, the protests in Victory Square, but it seems tonight is a quiet one and nothing is being burned, so late-night cards and a perusal of each others’ scripts will have to do.

Monday 27th February

The rest of the group have a flight back to London later today which apparently cost 99p per person before tax. I don’t know how much less the 5am option was, but I think it’s probably worth it. My own flight is truly at 5am tomorrow and I plan to stay up all night. The students return to school tomorrow, doubtless to receive a glorious mix of adulation and apathy. Harvey requests whether next year this trip can be timed differently so that he can miss the whole of his local Eisteddfod, rather than just one day. I promise to ask the organisers, say goodbye, then head for the hills on a train journey long enough to write the entirety of this report.

3am at Bucharest airport, and thoughts can now turn to the future. Many of us will meet in five weeks’ for another round of mathematics in the more tranquil setting of Cambridge. Meanwhile, I certainly enjoyed, admittedly through red eyes, the entertainment of a flight to Israel where baggage size regulations are actually enforced at the boarding gate, and apparently everyone else made it back safely too.

RMM 2017 – Problems 1, 4 and 5

I’ve recently taken a UK team to the 2017 edition of the Romanian Master of Mathematics competition in Bucharest. The British students did extremely well and we all enjoyed ourselves mathematically and generally. The customary diary may appear shortly, but this time I want to focus mainly on the questions, since that is after all the main point of these competitions! I hope that what follows is interesting, and at slightly education to potential future students.

I’ve split this into two posts based on my opinion on difficulty, which is subjective but probably correlates fairly positively with most people’s. The account of Q1 is guest-written by two British students, based on their solutions during the competition.

Problem 1

a) Prove that every positive integer n can be written uniquely in the form

n = \sum_{j=1}^{2k+1} (-1)^{j-1} 2^{m_j},

where k\geq 0 and 0 \leq m_1 < m_2 < \cdots < m_{2k+1} are integers. This number k is called the weight of n.

b) Find (in closed form) the difference between the number of positive integers at most 2^{2017} with even weight and the number of positive integers at most 2^{2017} with odd weight.

Rosie Cates and Neel Nanda:

a) We are trying to express n in terms of powers of 2, so it seems sensible to write in binary. As 2^{m_1} is the smallest power of 2, this term is responsible for the last 1 in the binary representation of n. Let $letx x = n – 2^{m_1}$ (ie n with the last 1 removed from its binary expansion). Now if we pair up terms in the sum to get

x = (2^{m_{2k}+1} - 2^{m_{2k}}) + \ldots + (2^{m_3} - 2^{m_2}),

we can see that each bracket looks like 11…100…0 when written in binary. Also, the condition that m_i < m_{i+1} is equivalent to ensuring that we do not break any strings of consecutive 1s that were in the binary expansion of x (so for example 111110 = 110000 +1110 is not allowed). So writing x in the desired form is the same as writing it as the sum of numbers of the form 11…100\ldots 0 without breaking any strings of 1s. For example

1110100110 = 1110000000 + 100000 + 110.

Clearly there is exactly one way of doing this for every x, so (as each n has exactly one x) there is exactly one way to do it for each n as well.

This approach allows k to be understood differently. Write n in binary and remove the last 1; now count the number of groups of consecutive 1s. This is equal to k.

b) The second half of the problem becomes a lot simpler with the observation that n\leq 2^{m_{2k+1}}, as

n=2^{m_{2k+1}}-(2^{m_{2k}}-2^{m_{2k-1}})-\ldots-(2^{m_2}-2^{m_1}),

and the sequence m_n is increasing, so each bracket is positive. As each sequence of (m_n)s corresponds uniquely to an integer, this means we just want to count sequences of (m_n)s with greatest term at most 2017. The sequence is increasing, so each sequence corresponds to a subset of {0, 1, …, 2017} of size (2k+1). There are \binom{2018}{2k+1} subsets of size (2k+1), so the question reduces to finding a closed form for \sum_{k=0}^{1008} (-1)^k {{2018}\choose{2k+1}}.

This is reminiscent of a classic problem in combinatorics: using the binomial theorem to evaluate sums of binomial coefficients weighted by powers. The best example is

\sum_{k=0}^n (-1)^k \binom{n}{k} =(1-1)^n=0,

but here rather than (-1) we want something whose square is $(-1)$, so we consider the complex number i. Using the same ideas, we get that

\sum_{r=0}^{2018} i^r \binom{2018}{r}=(1+i)^{2018},

which contains what we want, but also binomial coefficients with even r. But if r is even, i^r is real, and if r is odd, i^r is imaginary. So the sum we want appears as the imaginary part, that is

\mathrm{Im}\left((1+i)^{2018}\right)=\mathrm{Im}\left((\sqrt{2} \cdot e^{\frac{i\pi}{4}})^{2018}\right)=2^{1009}.

Dominic: note that in both parts, the respective authors find slightly more than what they were required to. That is, respectively, the interpretation of k, and a bound on m_{2k+1}. The latter is an excellent example of the general notion that sometimes it is better to use a stronger statement than what you actually require in an induction argument (here for existence). The stronger statement (which you guess from playing with examples) makes the inductive step easier, as it’s then clear that the new term you get is distinct from the terms you already have.

Problem 4

In the Cartesian plane, let \mathcal G_1, \mathcal G_2 be the graphs of the quadratic functions f_1(x) = p_1x^2 + q_1x + r_1, f_2(x) = p_2x^2 + q_2x + r_2, where p_1 > 0 > p_2. The graphs \mathcal G_1, \mathcal G_2 cross at distinct points A and B. The four tangents to \mathcal G_1, \mathcal G_2 at~A and B form a convex quadrilateral which has an inscribed circle. Prove that the graphs \mathcal{G}_1 and \mathcal{G}_2 have the same axis of symmetry.

This question is quite unusual for an olympiad of this kind, and I was initially skeptical, but then it grew on me. Ultimately, I was unsurprised that many contestants attacked entirely with coordinate calculations. If you use this strategy, you will definitely get there in the end, but you have to accept that you aren’t allowed to make any mistakes. And because of the amount of symmetry in the configuration, even if you make a mistake, you might still get the required answer, and so not notice that you’ve made a mistake. But I decided I liked it because various levels of geometric insight either reduced or removed the nastier calculations.

Typically, one could gain geometric insight by carefully observing an accurate diagram, but an accurate parabola is hard to draw. However, even from a vague diagram, we might guess the key intermediate property of the configuration, which is that the line joining the other two points in the quadrilateral is parallel to the y-axis. This means that they have the same x-coordinate, and indeed this x-coordinate must in fact be the same for any parabola through A and B, so it is reasonable to guess that it is \frac{x_A+x_B}{2}, the mean of the x-coordinates of A and B.

Since you know this is the goal, it’s not too bad to calculate the equations of the tangent lines directly, and demonstrate this algebraically. But I was determined to use the focus-directrix definition of a parabola. Either recall, or digest the interesting new fact that a parabola may be defined as the locus of points which are the same distance from a fixed point P (the focus), and a fixed line \ell (the directrix). Naturally, the distance to the line is perpendicular distance.

To ensure the form given in the statement where y is a quadratic function of x, in this setting the directrix should be parallel to the x-axis. To define the tangent to the parabola at A, let A’ be the foot of the perpendicular from A onto \ell, so AA’=PA. I claim that the tangent at A is given by the perpendicular bisector of A’P. Certainly this passes through A, and it is easy to convince yourself that it can’t pass through any other point B on the parabola, since BA’> PB, as A’ is on \ell but is not the foot of the perpendicular form B to \ell. This final observation is truly a lot more obvious if you’re looking at a diagram.

We now want to finish geometrically too. In our quadrilateral, one diagonal is parallel to the y-axis, and it will suffice to show that the existence of an incircle implies that A and B must have the same y-coordinate. We have just shown A and B are the same (horizontal) distance from the other diagonal. So certainly if they have the same y-coordinate, then the quadrilateral is a kite, and the sums of opposite sides are equal, which is equivalent to the existence of an incircle. One could then finish by arguing that this ceases to be true if you move one of A and B in either direction, or by some short explicit calculation if such a perturbation argument leaves you ill at ease.

Question 5

Fix an integer n \geq 2. An n x n  sieve is an n x n array with n cells removed so that exactly one cell is removed from every row and every column. A stick is a 1 x k or k x 1 array for any positive integer k. For any sieve A, let m(A) be the minimal number of sticks required to partition A. Find all possible values of m(A), as A varies over all possible n x n sieves.

This is a fairly classic competition problem, and while in my opinion the statement isn’t particularly fascinating, it’s interesting that it admits such a wide range of approaches.

As ever, you need to start by playing around with the setup, and guessing that the answer is 2n-2, and not thinking `it can’t possibly be the same answer as Q3??’ Then think about reasons why you couldn’t do better than 2n-2. My very vague reason was that if you only use horizontal sticks, the answer is clearly 2n-2, and the same if you only use vertical sticks. But it feels like you can only make life harder for yourself if you try to use both directions of sticks in lots of places. Note that some sort of argument involving averaging over stick lengths is definitely doomed to fail unless it takes into account the Latin square nature of the location of holes! For example, if you were allowed to put all the holes in the first row, m(A) would be n-1.

Induction is tempting. That is, you remove some number of sticks, probably those corresponding to a given hole, to reduce the board to an (n-1)x(n-1) configuration. If you do this, you need to be clear about why you can remove what you want to remove (in particular, the number of sticks you want to remove), and whether it’s qualitatively different if the hole in question lies on the border of the board. In all of these settings, you want to be careful about 1×1 sticks, which it’s easy inadvertently to count as both horizontal and vertical. This is unlikely to affect the validity of any argument (just picking either an arbitrary or a canonical direction if it’s 1×1 should be fine) but does make it much harder to check the validity.

Joe exhibited directly a construction of 2n-2 cells which must be covered by different sticks. This approach lives or dies by the quality of the written argument. It must look general, even though any diagram you draw must, almost by definition, correspond to some particular case. Alternatively, since the problem is set on a grid, the cells correspond naturally to edges of a bipartite graph, where classes correspond to rows and columns. The holes form a perfect matching on this bipartite graph. But, as Harvey observed, if you split the rows and columns in two, on either side of the relevant hole (or not in the 2+2 cases where the hole is at the border), you have a (2n-2)+(2n-2) bipartite graph, and a perfect matching here corresponds to a set of cells which must be covered by different sticks. This is an ingenious idea, and if you’ve recently met Hall’s Marriage Theorem, which gives a verifiable criterion for the existence of such a perfect matching, there are few better uses of your next ten minutes than to check whether Hall’s condition a) should hold; b) can be proven to hold in this setting.

BMO1 2016 – the non-geometry

Here’s a link to yesterday’s BMO1 paper, and the video solutions for all the problems. I gave the video solution to the geometric Q5, and discuss aspects of this at some length in the previous post.

In these videos, for obvious educational reasons, there’s a requirement to avoid referencing theory and ideas that aren’t standard on the school curriculum or relatively obvious directly from first principles. Here, I’ve written down some of my own thoughts on the other problems in a way that might add further value for those students who are already have some experience at olympiads and these types of problems. In particular, on problems you can do, it’s worth asking what you can learn from how you did them that might be applicable generally, and obviously for some of the harder problems, it’s worth knowing about solutions that do use a little bit of theory. Anyway, I hope it’s of interest to someone.

bmo1-2016-q1Obviously we aren’t going to write out the whole list, but there’s a trade-off in time between coming up with neat ideas involving symmetry, and just listing and counting things. Any idea is going to formalise somehow the intuitive statement ‘roughly half the digits are odd’. The neat ideas involve formalising the statement ‘if we add leading zeros, then roughly half the digits are odd’. The level of roughness required is less in the first statement than the second statement.

Then there’s the trade-off. Trying to come up with the perfect general statement that is useful and true might lead to something like the following:

‘If we write the numbers from 0000 to N, with leading zeros, and all digits of N+1 are even, then half the total digits, ie 2N of them, are odd.’

This is false, and maybe the first three such things you try along these lines are also false. What you really want to do is control the numbers from 0000 to 1999, for which an argument by matching is clear, and gives you 2000 x 4 / 2 = 4000 odd digits. You can exploit the symmetry by matching k with 1999-k, or do it directly first with the units, then with the tens and so on.

The rest (that is, 2000 to 2016) can be treated by listing and counting. Of course, the question wants an actual answer, so we should be wary of getting it wrong by plus or minus one in some step. A classic error of this kind is that the number of integers between 2000 and 2016 inclusive is 17, not 16. I don’t know why the memory is so vivid, but I recall being upset in Year 2 about erring on a problem of this kind involving fences and fenceposts.

bmo1-2016-q2As with so many new types of equation, the recipe is to reduce to a type of equation you already know how to solve. Here, because {x} has a different form on different ranges, it makes sense to consider the three ranges

x\in[0,1/25],\, x\in[1/25,1/8],\, x\in [1/8,\infty),

as for each of these ranges, we can rewrite 5y\{8y\}\{25y\} in terms of standard functions without this bracket notation. On each range we can solve the corresponding equation. We then have to check that each solution does actually lie in the appropriate range, and in two cases it does, and in one case it doesn’t.

bmo1-2016-q3Adding an appropriately-chosen value to each side allows you to factorise the quadratics. This might be very useful. But is it an invitation to do number theory and look at coprime factors and so on, or is a softer approach more helpful?

The general idea is that the set of values taken by any quadratic sequence with integer coefficients and leading coefficient one looks from a distance like the set of squares, or the set \{m(m+1), \,m\in\mathbb{N}\}, which you might think of as ‘half-squares’ or ‘double triangle numbers’ as you wish. And by, ‘from a distance’ I mean ‘up to an additive constant’. If you care about limiting behaviour, then of course this additive constant might well not matter, but if you care about all solutions, you probably do care. To see why this holds, note that

n^2+2n = (n+1)^2 - 1,

so indeed up to an additive constant, the quadratic on the LHS gives the squares, and similarly

n^2 - 7n = (n-4)(n-3)-12,

and so on. To solve the equation n^2=m^2+6, over the integers, one can factorise, but another approach is to argue that the distance between adjacent squares is much more than 6 in the majority of cases, which leaves only a handful of candidates for n and m to check.

The same applies at this question. Adding on 9 gives

n^2-6n+9 = m^2 + m -1,

which is of course the same as

(n-3)^2 = m(m+1)-1.

Now, since we now that adjacent squares and ‘half-squares’ are more than one apart in all but a couple of cases, we know why there should only be a small number of solutions. I would call a method of this kind square-sandwiching, but I don’t see much evidence from Google that this term is generally used, except on this blog.

Of course, we have to be formal in an actual solution, and the easiest way to achieve this is to sandwich m(m+1)-1 between adjacent squares m^2 and (m+1)^2, since it is very much clear-cut that the only squares which differ by one are zero and one itself.

bmo1-2016-q4I really don’t have much to say about this. It’s not on the school curriculum so the official solutions are not allowed to say this, but you have to use that all integers except those which are 2 modulo 4 can be written as a difference of two squares. The easiest way to show this is by explicitly writing down the appropriate squares, treating the cases of odds and multiples of four separately.

So you lose if after your turn the running total is 2 modulo 4. At this point, the combinatorics isn’t too hard, though as in Q1 one has to be mindful that making an odd number of small mistakes will lead to the wrong answer! As in all such problems, it’s best to try and give a concrete strategy for Naomi. And it’s best if there’s something inherent in the strategy which makes it clear that it’s actually possible to implement. (Eg, if you claim she should choose a particular number, ideally it’s obvious that number is available to choose.)

One strategy might be: Naomi starts by choosing a multiple of four. Then there are an even number of multiples of four, so Naomi’s strategy is:

  • whenever Tom chooses a multiple of four, Naomi may choose another multiple of four;
  • whenever Tom chooses a number which is one (respectively three) modulo 4, Naomi may choose another which is three (respectively one) modulo 4.

Note that Naomi may always choose another multiple of four precisely because we’ve also specified the second condition. If sometimes Tom chooses an odd number and Naomi responds with a multiple of four out an idle and illogical sense of caprice, then the first bullet point would not be true. One can avoid this problem by being more specific about exactly what the algorithm is, though there’s a danger that statements like ‘whenever Tom chooses k, Naomi should choose 100-k’ can introduce problems about avoiding the case k=50.

bmo1-2016-q6I started this at the train station in Balatonfured with no paper and so I decided to focus on the case of just m, m+1 and n, n+2. This wasn’t a good idea in my opinion because it was awkward but guessable, and so didn’t give too much insight into actual methods. Also, it didn’t feel like inducting on the size of the sequences in question was likely to be successful.

If we know about the Chinese Remainder Theorem, we should know that we definitely want to use it here in some form. Here are some clearly-written notes about CRT with exercises and hard problems which a) I think are good; b) cite this blog in the abstract. (I make no comment on correlation or causality between a) and b)…)

CRT is about solutions to sets of congruence equations modulo various bases. There are two aspects to this , and it feels to me like a theorem where students often remember one aspect, and forget the other one, in some order. Firstly, the theorem says that subject to conditions on the values modulo any non-coprime bases, there exist solutions. In many constructive problems, especially when the congruences are not explicit, this is useful enough by itself.

But secondly, the theorem tells us what all the solutions are. There are two stages to this: finding the smallest solution, then finding all the solutions. Three comments: 1) the second of these is easy – we just add on all multiples of the LCM of the bases; 2) we don’t need to find the smallest solution – any solution will do; 3) if you understand CRT, you might well comment that the previous two comments are essentially the same. Anyway, finding the smallest solution, or any solution is often hard. When you give students an exercise sheet on CRT, finding an integer which is 3 mod 5, 1 mod 7 and 12 mod 13 is the hard part. Even if you’re given the recipe for the algorithm, it’s the kind of computation that’s more appealing if you are an actual computer.

Ok, so returning to this problem, the key step is to phrase everything in a way which makes the application of CRT easy. We observe that taking n=2m satisfies the statement – the only problem of course is that 2m is not odd. But CRT then tells us what all solutions for n are, and it’s clear that 2m is the smallest, so we only need to add on the LCM (which is odd) to obtain the smallest odd solution.

DGFF 3 – Gibbs-Markov property for entropic repulsion

In the previous post, we saw that it isn’t much extra effort to define the DGFF with non-zero boundary conditions, by adding onto the zero-BC DGFF the unique (deterministic) harmonic function which extends the boundary values into the domain. We also saw how a Gibbs-Markov property applies, whereby the values taken by the field on some sub-region A\subset D depend on the values taken on D\backslash A only through values taken on \partial A.

In this post, we look at how this property and some other methods are applied by Deuschel [1] to study the probability that the DGFF on a large box in \mathbb{Z}^d is positive ‘everywhere’. This event can be interpreted in a couple of ways, all of which are referred to there as entropic repulsion. Everything which follows is either taken directly or paraphrased directly from [1]. I have tried to phrase this in a way which avoids repeating most of the calculations, instead focusing on the methods and the motivation for using them.

Fix dimension d\ge 2 throughout. We let P^0_N be the law of the DGFF on V_N:=[-N,N]^d\subset \mathbb{Z}^d with zero boundary conditions. Then for any subset A\subset \mathbb{Z}^d, in an intuitively-clear abuse of notation, we let

\Omega^+(A):= \{ h_x\ge 0, x\in A\},

be the event that some random field h takes only non-negative values on A. The goal is to determine P^0_N ( \Omega^+(V_N)). But for the purposes of this post, we will focus on showing bounds on the probability that the field is non-negative on a thin annulus near the boundary of V_N, since this is a self-contained step in the argument which contains a blog-friendly number of ideas.

We set (L_N) to be a sequence of integers greater than one (to avoid dividing by zero in the statement), for which \frac{L_N}{N}\rightarrow 0. We now define for each N, the annulus

W_N = \{v\in V_N: L_N\le d_{\mathbb{Z}^d}(v, V_N^c)\le 2L_N \}

with radius L_N set a distance L_N inside the box V_N. We aim to control P^N_0 (\Omega^+(W_N)). This forms middle steps of Deuschel’s Propositions 2.5 and 2.9, which discuss P^N_0(\Omega^+(V_{N-L_N})). Clearly there is the upper bound

P^N_0(\Omega^+(V_{N-L_N})) \le P^N_0(\Omega^+(W_N)) (1)

and a lower bound on P^N_0(\Omega^+(V_{N-L_N})) is obtained in the second proposition by considering the box as a union of annuli then combining the bounds on each annulus using the FKG inequality.

Upper bound via odds and evens

After removing step (1), this is Proposition 2.5:

\limsup_{N\rightarrow \infty} \frac{L_N}{N^{d-1} \log L_N} \log P^N_0(\Omega^+(W_N)) < 0. (2)

This is giving a limiting upper bound on the probability of the form L_N^{-CN^{d-1}/L_N}, though as with all LDP estimates, the form given at (2) is more instructive.

Morally, the reason why it is unlikely that the field should be non-negative everywhere within the annulus is that the distribution at each location is centred, and even though any pair of values are positively correlated, this correlation is not strong enough to avoid this event being unlikely. But this is hard to corral into an upper bound argument directly. In many circumstances, we want to prove upper bounds for complicated multivariate systems by projecting to get an unlikely event for a one-dimensional random variable, or a family of independent variables, even if we have to throw away some probability. We have plenty of tools for tail probabilities in both of these settings. Since the DGFF is normal, a one-dimensional RV that is a linear combination (eg the sum) of all the field heights is a natural candidate. But in this case we would have thrown away too much probability, since the only way we could dominate is to demand that the sum \sum_{x\in W_N}h^N_x\ge 0, which obviously has probability 1/2 by symmetry. (3)

So Deuschel splits W_N into W_N^o,W_N^e, where the former includes all vertices with odd total parity in W_N and the latter includes all the vertices with even total parity in the interior of W_N. (Recall that \mathbb{Z}^d is bipartite in exactly this fashion). The idea is to condition on h^N\big|_{W^o_N}. But obviously each even vertex is exactly surrounded by odd vertices. So by the Gibbs-Markov property, conditional on the odd vertices, the values of the field at the even vertices are independent. Indeed, if for each v\in W_N^e we define \bar h_v to be the average of its neighbours (which is measurable w.r.t to the sigma-algebra generated by the odd vertices), then

\{h_v: v\in W_N^e \,\big|\, \sigma(h_w: w\in W_N^o)\},

is a collection of independent normals with variance one, and where the mean of h_v is \bar h_v.

To start finding bounds, we fix some threshold m=m_N\gg 1 to be determined later, and consider the odd-measurable event A_N that at most half of the even vertices v have \bar h_v\ge m. So A_N^c\cap \Omega^+(W_N) says that all the odd vertices are non-negative and many are quite large. This certainly feels like a low-probability event, and unlike at (3), we might be able to obtain good tail bounds by projection into one dimension.

In the other case, conditional on A_N, there are a large number of even vertices with conditional mean at most m, and so we can control the probability that at least one is negative as a product

(1-\varphi(m))^{\frac12 |W_N^e|}. (4)

Note that for this upper bound, we can completely ignore the other even vertices (those with conditional mean greater than m).

So we’ll go back to A_N^c \cap \Omega^+(W_N). For computations, the easiest one-dimensional variable to work with is probably the mean of the \bar h_vs across v\in W_N^e, since on A_N^c\cap \Omega^+(W_N) this is at least \frac{m}{2}. Rather than focus on the calculations themselves involving

\bar S^e_N:= \frac{1}{|W_N^e|} \sum\limits_{v\in W_N^e} \bar h_v,

let us remark that it is certainly normal and centered, and so there are many methods to bound its tail, for example

P^0_N \left( \bar S^e_N \ge \frac{m}{2} \right) \le \exp\left( \frac{-m^2}{8\mathrm{Var}(\bar S^e_N)} \right), (5)

as used by Deuschel just follows from an easy comparison argument within the integral of the pdf. We can tackle the variance using the Green’s function for the random walk (recall the first post in this set). But before that, it’s worth making an observation which is general and useful, namely that \bar S^e_N is the expectation of

S^e_N:= \sum{1}{|W_N^e|}\sum\limits_{v\in W_N^e} h_v

conditional on the odds. Directly from the law of total variance, the variance of any random variable X is always larger than the variance of \mathbb{E}[X|Y].

So in this case, we can replace \mathrm{Var}(\bar S^e_N) in (5) with \mathrm{Var}(S^e_N), which can be controlled via the Green’s function calculation.

Finally, we choose m_N so that the probability at (4) matches the probability at (5) in scale, and this choice leads directly to (2).

In summary, we decomposed the event that everything is non-negative into two parts: either there are lots of unlikely local events in the field between an even vertex and its odd neighbours, or the field has to be atypically large at the odd sites. Tuning the parameter m_N allows us to control both of these probabilities in the sense required.

Lower bound via a sparse sub-lattice

To get a lower bound on the probability that the field is non-negative on the annulus, we need to exploit the positive correlations in the field. We use a similar idea to the upper bound. If we know the field is positive and fairly large in many places, then it is increasingly likely that it is positive everywhere. The question is how many places to choose?

We are going to consider a sub-lattice that lives in a slightly larger region than W_N itself, and condition the field to be larger than m=m_N everywhere on this lattice. We want the lattice to be sparse enough that even if we ignore positive correlations, the chance of this happening is not too small. But we also want the lattice to be dense enough that, conditional on this event, the chance that the field is actually non-negative everywhere in W_N is not too small either.

To achieve this, Deuschel chooses a sub-lattice of width \lfloor\epsilon L_N^{2/d}\rfloor, and sets \Lambda_N(\epsilon) to be the intersection of this with the annulus with radii [N-\frac{5}{2}L_N, N-\frac{1}{2}L_N], to ensure it lives in a slightly larger region than W_N itself. The scaling of this sub-lattice density is such that when a random walk is started at any v\in W_N, the probability that the RW hits \Lambda_N(\epsilon) before \partial V_N is asymptotically in (0,1). (Ie, not asymptotically zero or one – this requires some definitely non-trivial calculations.) In particular, for appropriate (ie large enough) choice of \epsilon, this probability is at least 1/2 for all v\in W_N. This means that after conditioning on event B_N:=\{h_v\ge m : v\in \Lambda_N(\epsilon)\}, the conditional expectation of h_w is at least \frac{m}{2} for all w\in W_N\backslash \Lambda_N(\epsilon). Again this uses the Gibbs-Markov property and the Gaussian nature of the field. In particular, this conditioning means we are left with the DGFF on V_N\backslash \Lambda_N(\epsilon), ie with boundary \partial V_N\cup \Lambda_N(\epsilon), and then by linearity, the mean at non-boundary points is given by the harmonic extension, which is linear (and so increasing) in the boundary values.

At this point, the route through the calculations is fairly clear. Since we are aiming for a lower bound on the probability of the event \Omega^+(W_N), it’s enough to find a lower bound on P^0_N(\Omega^+(W_N)\cap B).

Now, by positive correlation (or, formally, the FKG inequality) we can control P^0_N(B) just as a product of the probabilities that the field exceeds the threshold at each individual site in \Lambda_N(\epsilon). Since the value of the field at each site is normal with variance at least 1 (by definition), this is straightforward.

Finally, we treat P^0_N(\Omega^+(W_N) \,\big|\, B). We’ve established that, conditional on B, the mean at each point of W_N\backslash \Lambda_N(\epsilon) is at least \frac{m}{2}, and we can bound the variance above too. Again, this is a conditional variance, and so is at most the corresponding original variance, which is bounded above by \sigma_N^2:=\mathrm{Var}(h^N_0). (This fact that the variance is maximised at the centre is intuitively clear when phrased in terms of occupation times, but the proof is non-obvious, or at least non-obvious to me.)

Since each of the event h_v^N\ge 0 for v\in W_N\backslash \Lambda_N(\epsilon) is positively correlated with B, we can bound the probability it holds for all v by the product of the probabilities that it holds for each v. But having established that the conditional mean is at least \frac{m_N}{2} for each v, and the variance is uniformly bounded above (including in N), this gives an easy tail bound of the form we require.

Again it just remains to choose the sequence of thresholds m_N to maximise the lower bound on the probability that we’ve found in this way. In both cases, it turns out that taking m_N= \sqrt{C\log N} is sensible, and this turns out to be linked to the scaling of the maximum of the DGFF, which we will explore in the future.

References

[1] – J-D Deuschel, Entropic Repulsion of the Lattice Free Field, II. The 0-Boundary Case. Available at ProjectEuclid.

Questionable Statistics

My four years in the Statistics Department have been characterised by a continual feeling that I don’t know enough about statistics. That said, I can’t help but notice how statistics are used in non-specialist contexts, and of course there are times when eyebrows might reasonably be raised. Andrew Gelman (who gave a very enjoyable departmental seminar on this topic in May) has a notable blog critiquing poor statistical methodology, especially in social science; and the blogosphere is packed with compilations of egregious statistical oxymorons (“All schools *must* be above average” etc).

I’m aiming for more of a middle ground here. I’ve picked three examples of articles I found interesting at some level over the past few months. In each of them, some kind of data presentation or experiment design arose, and in all cases, I think it resulted in more questions rather than more answers, not really in a good way, since in all cases I did actually want to know more about what was going on.

Extreme rounding errors

This Guardian article about inequality in career trajectories for teachers in schools serving more advantaged and more deprived areas raises a lot of interesting questions, and actually proposes answers to several of them. The problem is the double bar chart halfway down.

First a superficial moan. Rounding to the nearest integer is fine, indeed sensible in most contexts, but not when you are treating small numbers. Comparing the extreme bars, we could have 11.5 v 12.5 or we could have 10.5 v 13.5. The headlines would probably read “N% more teachers leave disadvantaged schools”. In the first case N is 9, in the second it’s 29. So it’s not really a superficial moan. Data is supposed to offer a measure of the effect under consideration, and a discussion of how treat this effect requires a veneer of reliability about the size of the effect. We don’t just need to be asking “how can we solve this”; we also need to be asking “is this worth solving?” I’m not saying the answer is no, but based on this graph alone the answer is not ‘definitely yes’. [1]

A question to ask in the context of this report is “why do more teachers leave the profession from schools in deprived areas?” But I think most people could speculate a broadly sensible answer to this. The data raises the more subtle question “why are the rates of leaving the profession so similar across all types of school?” Essentially I think this survey is a negative result – the effect just isn’t as strong as I’d have suspected, nor I imagine the authors nor the Guardian education editorship.

By contrast, even with the amateurish presentation, the rates of moving school clearly are significant and worth talking about based on this survey. Significant data demands further information though. Once an effect is significant, we need to know more details, like to what extent the teachers are moving to schools in the same band or to mostly towards the left end of the graph. Again though, there’s no comment on the magnitude of this effect. Assuming the rate is given per year [2], then among teachers who do not leave the profession, the average tenure of a given job is more than ten years, even in the most deprived category. Maybe this is all very heavy-tailed, and so the average isn’t a good thing to be using. But this doesn’t seem like an unreasonable number to me? If the claim is that this is a major problem for the teaching profession, then we should be told what the numbers are in vaguely comparable industries.

The final thing is pretty bad. Three paragraphs under the graph, it is claimed that the rate of leaving is 70% higher in most- than least-deprived categories. We decided that N was somewhere between 9 and 29. But not 70. I can only assume that this came from the ‘moving’ category instead…

[1] I’m assuming the sample pool was large enough that the effect is statistically significant, because there isn’t a direct link to the source data or even the source report unfortunately.

[2] and is it plausible that this is rate per year? Does the profession really experience ten percent annual turnover? Is it even plausible that the scale is the same? Maybe rate of leaving really is twice rate of moving school, and I have no idea about anything, but this seems questionable.

Many, many categories

The bank Halifax commissions an annual survey about pocket money, and this year’s received widespread coverage. My attention was caught by this article on BBC news. The short summary is that they surveyed about 1,200 children from about 600 families (so in many cases a direct comparison between siblings could have been possible), and it sounds like they restricted to the age range 8-15, and asked how much pocket money they received, and whether they wanted more.

The clickbait summary was that boys receive about 13% more than girls. While it doesn’t give the exact numbers, it also mentions that more boys than girls thought they deserved more money. A psychologist conjectures that this latter effect might explain the former effect, and indeed this seems plausible. The problem is that elsewhere in the article, it says that in the corresponding survey in 2015, boys receive on average only 2% more than girls.

We therefore have to consider a couple of things. 1) Is it plausible that the actual average pocket money rates (among the whole population) have fluctuated in such a gender-dependent way in 12 months? 2) If not, then can we still say something useful, even if our confidence in the methodology of the survey is reduced?

I think the answer to the first question is definitely ‘no’. So we come to the second question. Firstly, how could this have arisen? Well, there’s no indication how the children were chosen, but equally it’s hard to think of a way of choosing them that would increase artificially the boys’ pocket money. In this last sentence, I’m deliberately suggesting the null hypothesis that boys and girls are the same. This is misleading. For now, our null hypothesis is that 2015 should be the same as 2016. Indeed, it’s equally plausible that this year’s summary data was ‘more correct’, and so we are asking why the difference was excessively compressed in 2015.

This is entirely a matter of effect size, and it’s to the article’s credit that so much information is given further down the page that we can actually make the following remarks quantitatively. At the bottom, they show the average pay (across genders) in different regions. There is a lot of variation here. The rate of pay in East Anglia is only 60% what it is in London. At some level, I’m surprised it isn’t even higher. The article tells us that children between the ages of eight and fifteen were surveyed. By what rate did your pocket money change in that interval? Surely it doubled at the very least? Weekly pocket money at age eight is for sweets and an occasional packet of Pokemon cards (substitute 21st century equivalent freely…). Teenagers need to pay for outings and clothes etc, so there’s no reason at all why this should be comparable. For the purposes of definiteness in the next calculation, let’s say that fifteen-year-olds get paid four times as much as eight-year-olds on average, which I think is rather conservative.

So here’s a plausible reason for the fluctuations. Suppose between 2015 and 2016, the survey substituted 10 eight-year-old boys from the Midlands for 10 fifteen-year-old boys from London. The expectation change in the average amongst the 600 boys surveyed is

\frac{10}{600} \times (\sim 6.5) \times (4 \times (0.6)^{-1}) \approx 0.7,

in pounds, which is on the order of the actual change from 2015 to 2016. Choosing the participants in a non-uniform way seems like too basic a mistake to make, but mild fluctuations in the distribution of ages and locations, as well as the occasional outlier (they want to use the mean, so one oligarch’s daughter could make a noticeable difference in a sample size of 600) seems more plausible as an explanation to me than a general change in the population rates. Choosing participants in a uniform way is just hard when there are loads and loads of categories.

I’m not really saying that this survey is bad – they have to report what they found, and without a lot more information, I have no idea whether this year’s is more or less plausible than last year’s. But if you add the phrase “especially in 2016” to everything the psychologist says, it suddenly seems a bit ridiculous. So it would be worth making the remark that even if this effect is statistically significant, that doesn’t mean the effect size is large relative to lots of other less controversial effect sizes visible in the data.

Comparing precious metals

I’ve recently returning from this year’s International Mathematical Olympiad, and now we are well into the swing of its sweatier namesake in Rio. At both events, there have been many opportunities to observe how different people with different ambitions and levels of extroversion display different levels of pleasure at the same medal outcomes. In the light of this, I was drawn to this article, which has been getting quite a lot of traction online.

The basic premise is simple. Silver medallists are less happy than bronze medallists (when – unlike at the IMO – there is only one of each medal), and it’s not hard to come up with a cheap narrative: silver-winners are disappointed to have missed out on gold; bronze-winners are glad to have got a medal at all. This is all pretty convincing, so maybe there’s no need actually to collect any data, especially since asking a crowd of undergraduates to rate faces on the 1-10 agony-ecstacy scale sounds like a bit of an effort. Let’s read a couple of sentences, describing a follow-up study on judo medallists at the Athens Olympics:

Altogether, they found that thirteen of the fourteen gold medal winners smiled immediately after they completed their winning match, while eighteen of the twenty-six bronze medalists smiled. However, none of the silver medalists smiled immediately after their match ended.

You might wonder how come there are almost twice as many bronzes as golds. Well, very full details about the judo repechage structure can be found here, but the key information is that all bronze-medallists won their final match, as, naturally, did the gold-medallists. The silver-medallists lost their final match, ie the gold-medal final. So this study is literally reporting that highly-driven competitive sportsmen are happier straight after they win, than straight after they lose. This doesn’t have much to do with medals, and isn’t very exciting, in my opinion. I would, however, be interested to know what was eating the one gold medallist who didn’t smile immediately.

This isn’t really a gripe about the statistics, more about the writing. They are testing for an effect which seems highly plausible, but is branded as surprising. The study for which they give more methodological details in fact seems to be testing for a related effect, which is not just plausible, but essentially self-evident. So naturally I want to know more about the original study, which is the only place left for there to be any interesting effects, for example if they looked at athletics events which don’t have a binary elimination structure. But we aren’t told enough to find these interesting effects, if they exist. How annoying. The only thing left is to think about is my bronze medal at IMO 2008. They said eight years would be enough for the wounds to heal but I’m still not smiling.

IMO 2016 Diary – Part Four

A pdf of this report is also available here.

Thursday 14th July

I have now spent a while thinking about square-free n in Q3 after rescaling, and I still don’t know what the markscheme should award it. I therefore request that Joe and Warren receive the same score as each other, and any other contestant who has treated this case. In my opinion this score should be at most one, mainly as a consolation, but potentially zero. However, we are offered two, and after they assure me this is consistent, I accept.

There is brief but high drama (by the standards of maths competitions) when we meet Angelo the Australian leader, who confirms that he has just accepted one mark for almost the same thing by his student Johnny. A Polish contestant in a similar situation remains pending, so we all return for a further meeting. I’m unconvinced that many of the coordinators have read all the scripts in question, but they settle on two for everyone, which is consistent if generous. The only drama on Q5 is the ferocious storm that sets in while I’m making final notes in the plaza. Again though, coordinator Gabriele has exactly the same opinion on our work as Geoff and I, apart from offering an additional mark for Lawrence’s now slightly damp partial solution.

And so we are finished well before lunch, with a total UK score of 165 looking very promising indeed. I’m particularly pleased with the attention to detail – Jacob’s 6 on Q4 is the only mark ‘dropped’, which is brilliant, especially since it hasn’t come at the expense of the students’ usual styles. We’ll have to wait until later to see just how well we have done.

It would be nice to meet the students to congratulate them in person, but they are with Jill on the somewhat inaccessible Victoria Peak, so instead I take a brief hike along the trail down the centre of HK Island, ending up at the zoo. This turned out to be free and excellent, though I couldn’t find the promised jaguar. There was, however, a fantastic aviary, especially the striking flock of scarlet ibis. A noisy group of schoolchildren are surrounding the primates, and one lemur with an evil glint in his eye swings over and languidly starts an activity which elicits a yelp from the rather harried teacher, who now has some considerable explaining to do.

With 1000 people all returning to UST at roughly 6.30, dinner is not dissimilar to feeding time at the zoo, and afterwards various leaders lock horns during the final jury meeting. Two countries have brought an unresolved coordination dispute to the final meeting, and for the first time since I became deputy leader, one of them is successful. Congratulations to the Koreans, who now have a third student with a highly impressive perfect score. Andy Loo and Geoff chair the meeting stylishly and tightly, and although there are many technical things to discuss, it doesn’t drag for too long. Eventually it’s time to decide the medal boundaries, and the snazzy electronic voting system makes this work very smoothly. I feel the gold and bronze cutoffs at 29 and 16 are objectively correct, and the 50-50 flexibility at silver swings towards generosity at 22. We can now confirm the UK scores as:

UKscoresThis is pretty much the best UK result in the modern era, placing 7th and with a medal tally tying with the famous food-poisoning-and-impossible-geometry IMO 1996 in India. But obviously this is a human story rather than just a 6×6 matrix with some summary statistics, and Harvey in particular is probably looking at the world and thinking it isn’t fair, while Warren’s gold is the ideal end to his four years at the IMO, two of which have ended one mark short. The American team are pretty keen to let everyone know that they’ve placed first for the second year in succession, and their remarkable six golds will hopefully allow scope for some good headlines. There is much to talk about, celebrate and commiserate, and this continues late into the night.

Friday 15th July

Our morning copy of the IMO Newsletter includes an interview with Joe, with the headline ‘Meh’. Frank Morgan has rather more to say, which is good news, since he’s delivering the IMO lecture on Pentagonal Tilings. He discusses the motivation of regular tilings where the ratio Perimeter/Area is minimised, starting from questions about honeycombs raised by the Roman author Varro! We move onto more mathematical avenues, including the interesting result of L’Huilier that given a valid set of angles, the associated polygon with minimal Perimeter/Area has an incircle, and the corresponding result for in-n-spheres in higher dimension. A brief diversion to the beach on the way home is punctuated with attempts to project the hyperbolic plane onto the sand.

The day’s main event is the closing ceremony, held at the striking Hong Kong Convention Centre. As usual, the adults and our students have been vigorously separated for the journey. As I arrive, it seems the UK boys have been directing a massed gathering behind the EU flag on stage, while the non-European teams are divided into two sides in a giant paper aeroplane dogfight. All attempts by the organisers to quash this jocularity are being ignored, and after bringing everyone here two hours early, I have minimal sympathy. Geoff sits on a secluded bench, and agrees to the many selfie requests from various teams with regal if resigned tolerance.

The ceremony is started by a fantastically charismatic school brass band, and proceeds with some brief speeches, and more astonishing drumming. Then it’s time to award the medals. Lawrence and Jacob get to go up together among the clump of 24-scorers, while Kevin from Australia does an excellent job of untangling his flag and medal while keeping hold of the ubiquitous cuddly koala. Neel has been threatened with death if he appears on stage again with an untucked shirt, but no direction is required for his and Warren’s smiles as they receive the gold medallists’ applause.

P1010513 (3)Afterwards, there is a closing banquet. We get to join British coordinators James and Joseph for a climate-defying carrot soup, followed by a rare diversion onto Western carbohydrates accompanying what is, for many of us, a first taste of caviar. Both Geoff and the American team are forced to make speeches at no notice. It is all generally rather formal, and fewer photographs are taken than usual. An attempt to capture Joe and Harvey looking miserable results in one the biggest grins of the evening. The UK and Australian teams have a thousand stickers and micro-koalas to give out as gifts, and some of the attempts at this descend into silliness. All clothing and body parts are fair game, and Jacob makes sure that Geoff is fully included. The UK and Australian leaders, variously coated, retreat from the carnage to the relative safety of our top-floor balcony as the IMO drifts to an end, until midnight, when it seems sensible to find out what the students are up to.

Saturday 16th July

This is what the students are up to. When we arrived at UST last week, everyone was given food vouchers to redeem at the campus’s various restaurants. Very very many of these are left over, and, despite the haute cuisine on offer earlier, people are hungry. They have therefore bought McDonalds. And I mean this literally. Animated by Jacob and American Michael, they have bought the entire stock of the nearest branch. If you want to know what 240 chicken nuggets looks like, come to common room IX.1, because now is your chance. Fortunately our team have made many friends and so after the Herculean task (I make no comment on which Herculean labour I feel this most resembles) of getting it to their common room, pretty much the entire IMO descends to help. Someone sets up a stopmotion of the slow erosion of the mountain of fries, while the usual card games start, and a group around a whiteboard tries to come up with the least natural valid construction for n=9 on Q2. Around 3.30am everything is gone, even the 30 Hello Kitties that came with the Happy Meals, and we’re pre-emptively well on the way to beating jetlag.

I wake up in time to wave Geoff off, but he’s been bumped to an earlier bus, so the only thing I see is Lawrence and colleagues returning from a suicidal 1500m round the seaside athletics track. Our own departure is mid-morning, and on the coach the contestants are discussing some problems they’ve composed during the trip. They’ll soon be able to submit these, and by the sounds of it, anyone taking BMO and beyond in 2018 has plenty to look forward to. Jacob has already mislaid his room key and phone, and at the airport he’s completed the hat-trick by losing one of the two essential passport insert pages. Fortunately, it turns out that he’s lost the less essential one, so we can clear security and turn thoughts towards lunch.

Jill has given me free licence to choose our dim sum, so the trip ends with pork knuckle and chicken feet. Our aim is to stay awake for the whole flight, and Neel helps by offering round copies of a Romanian contest from 2010, while I start proof-reading. By the time they finish their paper, many rogue commas have been mercilessly expunged. It should be daylight outside, but the windows are all shut, and by the ninth hour time starts to hang drowsily in a way that combinatorial geometry cannot fix, and so the mutual-waking-up pact kicks in, aided by Cathay Pacific’s unlimited Toblerone. Winding through Heathrow immigration, Joe unveils his latest airport trick of sleeping against vertical surfaces. We diverge into the non-humid night.

Reflection

IMG_0468 original (2)There’s a great deal more to life and mathematics than problem-solving competitions, but our contestants and many other people have worked hard to prepare for IMO 2016 over the past months (and years). So I hope I’m allowed to say that I’m really pleased for and proud of our UK team for doing so well! The last three days of an IMO are very busy and I haven’t had as much time as I’d have liked to talk in detail about the problems. But I personally really liked them, and thought the team showed great taste in choosing this as the British annus mirabilis in which to produce lots of beautiful solutions.

But overall, this is really just the icing on the cake of a training progamme that’s introduced lots of smart young people to each other, and to the pleasures of problem-solving, as well as plenty of interesting general mathematics. I have my own questions to address, and (unless I’m dramatically missing something) these can’t be completed in 4.5 hours, but as ever I’ve found the atmosphere of problem discussion totally infectious, so I hope we are doing something right.

Lawrence and Warren are now off to university. I’m sure they’ll thrive in every way at this next stage, and hopefully might enjoy the chance to contribute their energy and expertise to future generations of olympiad students. The other four remain eligible for IMO 2017 in Brazil, and while they will doubtless have high personal ambitions, I’m sure they’ll also relish the position as ideal role models for their younger colleagues over the year ahead. My own life will be rather different for the next two years, but our camp for new students is held in my no-longer-home-town Oxford in a few weeks’ time, and I’m certainly feeling excited about finding some new problems and doing as much as possible of the cycle all over again!

The Secretary Problem

This post explores in a direction rather different to my research and recent problems I’ve been talking about. We discuss a problem of optimal stopping theory. In less politically correct times, there were various other names for this including (according to Wikipedia) the marriage problem, the Sultan’s dowry problem and the fussy suitor problem. A much more appealing situation might be someone running an auction or selling a house, who wants the maximum bid, but has to accept or reject bids immediately. In any case, we shall quickly reduce it to a context-free setting.

The problem is as follows. A manager needs to hire a secretary and has n applicants, who are interviewed one at a time. I can’t think of a good reason why this should be the case in this context, but the manager’s only concern is to maximise the probability of picking the best of the n candidates. This would be easy if the choice were made at the end, but in fact the decision whether to accept or reject an applicant has to be made straight after the interview. What is the optimal strategy?

It must be clarified what is going on. In a practical setting, there would be some underlying numerical attribute which could be compared, and so the problem would reduce to what I’ve previously called the Passport Photograph problem. In this setting, after the kth candidate, we only know the relative ranks of the first k candidates to be seen. This in turn massively reduces the possibilities for a strategy. The strategy must be of the form:

Accept the kth candidate if they are the best candidate yet seen with some probability that is a function of k and n. Reject otherwise. In particular, this probability cannot depend on the history of the process – that is of basically no relevance at all since we only know the relative ranks at any given time.

There are two ideas that I want to justify informally for now. It seems reasonable to assume that this probability will either be 0 or 1 for each k and n. For example, one could work backwards in k, from n back to 1 working out the probabilities, and proving at each stage inductively that there is no advantage to a mixed strategy.

Secondly, suppose we decide we will accept the kth candidate if they are the best so far. Well if they are not the best, we pass to the next candidate. I claim that if we are using an optimal strategy, we should also accept the (k+1)st candidate if they are the best so far. This property is called monotonicity for the algorithm. In many senses this is the meat of the problem. If we can prove this, then everything else will be relatively straightforward. For now though, we assume it is true. This means that our optimal strategy for n is precisely defined by a threshold value of k. So we rewrite the strategy as follows:

We observe the first (k-1) candidates. After that, as soon as a candidate is the best so far, we accept them.

Note that this allows for the possibility that we do not choose anyone, so if this feels like a problem, we could always demand we choose the last candidate, even if we know they are not optimal. The question that remains is: what value should k take? Let’s make life easy and take n to be large, so we can assume k=cn for some constant c.

The probability that the second best was in the first cn, but the first was not is c(1-c). On that event, this strategy will definitely give us the best candidate. The probability that the third best was in the first cn, but the first and second were not is c(1-c)^2. Our strategy gives us the best candidate overall if and only if the first candidate appears before the second candidate in what remains of the process. Since we are just sampling from a random permutation, these are equally likely, so the probability that we get the best candidate is

\frac{1}{2} c(1-c)^2.

Continuing, the probability that the best candidate in the first cn is the fourth best overall, and the strategy gives us the best candidate is:

\frac{1}{3}c(1-c)^3.

So to find the optimal c, we have to maximise the sum

\sum_{k\geq 1}\frac{1}{k}c(1-c)^k

=-c\log c.

To find the maximum, we set the derivative equal to zero. Solving, we get c=1/e.

It turns out the most natural way to generalise this problem is to consider n independent random variables taking the values 0 and 1. The aim is to find a strategy that maximises the probability of picking the final 1. An informal analysis proceeds much as in the secretary problem. In this setting, we will work with fixed finite n rather than in some limit. Let us call the {0,1}-valued RVs, I_1,I_2,\ldots,I_n, and set

p_j=\mathbb{P}(I_j=1),\quad q_j=1-p_j,\quad r_j=\frac{p_j}{q_j},

in keeping with Bruss’s original paper dealing with this so-called ‘Odds problem’. Then, as before, we want to find the threshold for k. We should remark that the argument given below is shorter than Bruss’s proof, which uses generating functions, but again we will not address the matter of proving that the optimal strategy should have this threshold form.

First we explain why the secretary problem is a special case of this. Observe that, given no information about the first (k-1) candidates apart from their relative ranks, the probability that the kth candidate is the best so far is independent of the history of the process, and is equal to 1/k. So taking p_k=1/k in the odds problem precisely replicates the secretary problem, since the best candidate is, by construction, the final candidate who had the property of being the best so far.

Now we work out how to calculate the threshold for k. We could define k by:

k=\arg\max_{1\leq j \leq n}\left\{\mathbb{P}(I_k+\ldots+I_n=1)\right\}.

By summing over the possibilities for which of the I_j’s is 1, we get

\mathbb{P}(I_k+\ldots+I_n)=q_kq_{k+1}\ldots q_n\big[\frac{p_k}{q_k}+\ldots+\frac{p_n}{q_n}\big]=q_k\ldots q_n[r_k+\ldots+r_n].

So we ask, for which values of k is:

q_k\ldots q_n[r_k+\ldots+r_n]\geq q_{k+1}\ldots q_n[r_{k+1}+\ldots+r_n] ?

This is equivalent to

q_k\ldots q_n \cdot r_k \geq (1-q_k)q_{k+1}\ldots d_n[r_{k+1}+\ldots+r_n],

and we recall that (1-q_k)=p_k=q_kr_k, hence

\iff q_{k+1}\ldots q_n\ge q_{k+1}\ldots q_n[r_{k+1}+\ldots+r_n],

\iff 1\geq r_{k+1}+\ldots+r_n.

So we conclude that the correct optimal value for the threshold k is the largest value of j such that

r_j+\ldots+r_n < 1.

We can check that this agrees with our answer for the secretary problem since

\frac{1}{cn}+\frac{1}{cn+1}+\ldots+\frac{1}{n}\approx \int_{cn}^n \frac{dx}{x}=-\log c

which is approximately 1 precisely when c is roughly 1/e.

Finally a word on generalisations. Dendievel’s paper which appeared on arXiv yesterday considers a problem of Richard Weber where the RVs instead take values {-1,0,1}, and you want a strategy that successfully selects either the last time the value -1 appears or the last time +1 appears. The case where the probabilities of the event 1 and the event -1 are 1) equal and 2) constant is relatively straightforward by backwards induction as here, and the author deals with the two natural generalisations by removing 1) and 2) in turn. It seems natural that such a method should adapt for RVs taking any finite number of values.

REFERENCES

Bruss – Sum the odds to one and stop (2000)

Bruss – A note on bounds for the odds theorem of optional stopping (2003)

Dendievel – Weber’s optimal stopping problem and generalisations (2013) http://arxiv.org/abs/1309.2860

Subordinators and the Arcsine rule

After the general discussion of Levy processes in the previous post, we now discuss a particular class of such processes. The majority of content and notation below is taken from chapters 1-3 of Jean Bertoin’s Saint-Flour notes.

We say X_t is a subordinator if:

  • It is a right-continuous adapted stochastic process, started from 0.
  • It has stationary, independent increments.
  • It is increasing.

Note that the first two conditions are precisely those required for a Levy process. We could also allow the process to take the value \infty, where the hitting time of infinity represents ‘killing’ the subordinator in some sense. If this hitting time is almost surely infinite, we say it is a strict subordinator. There is little to be gained right now from considering anything other than strict subordinators.

Examples

  • A compound Poisson process, with finite jump measure supported on [0,\infty). Hereafter we exclude this case, as it is better dealt with in other languages.
  • A so-called stable Levy process, where \Phi(\lambda)=\lambda^\alpha, for some \alpha\in(0,1). (I’ll define \Phi very soon.) Note that checking that the sample paths are increasing requires only that X_1\geq 0 almost surely.
  • The hitting time process for Brownian Motion. Note that this does indeed have jumps as we would need. (This has \Phi(\lambda)=\sqrt{2\lambda}.)

Properties

  • In general, we describe Levy processes by their characteristic exponent. As a subordinator takes values in [0,\infty), we can use the Laplace exponent instead:

\mathbb{E}\exp(-\lambda X_t)=:\exp(-t\Phi(\lambda)).

  • We can refine the Levy-Khintchine formula;

\Phi(\lambda)=k+d\lambda+\int_{[0,\infty)}(1-e^{-\lambda x})\Pi(dx),

  • where k is the kill rate (in the non-strict case). Because the process is increasing, it must have bounded variation, and so the quadratic part vanishes, and we have a stronger condition on the Levy measure: \int(1\wedge x)\Pi(dx)<\infty.
  • The expression \bar{\Pi}(x):=k+\Pi((x,\infty)) for the tail of the Levy measure is often more useful in this setting.
  • We can think of this decomposition as the sum of a drift, and a PPP with characteristic measure \Pi+k\delta_\infty. As we said above, we do not want to consider the case that X is a step process, so either d>0 or \Pi((0,\infty))=\infty is enough to ensure this.

Analytic Methods

We give a snapshot of a couple of observations which make these nice to work with. Define the renewal measure U(dx) by:

\int_{[0,\infty)}f(x)U(dx)=\mathbb{E}\left(\int_0^\infty f(X_t)dt\right).

If we want to know the distribution function of this U, it will suffice to consider the indicator function f(x)=1_{X_t\leq x} in the above.

The reason to exclude step processes specifically is to ensure that X has a continuous inverse:

L_x=\sup\{t\geq 0:X_t\leq x\} so U(x)=\mathbb{E}L_x is continuous.

In fact, this renewal measure characterises the subordinator uniquely, as we see by taking the Laplace transform:

\mathcal{L}U(\lambda)=\int_{[0,\infty)}e^{-\lambda x}U(dx)=\mathbb{E}\int e^{-\lambda X_t}dt

=\int \mathbb{E}e^{-\lambda X_t}dt=\int\exp(-t\Phi(\lambda))dt=\frac{1}{\Phi(\lambda)}.

The Arcsine Law

X is Markov, which induces a so-called regenerative property on the range of X, \mathcal{R}. Formally, given s, we do not always have s\in\mathcal{R} (as the process might jump over s), but we can define D_s=\inf\{t>s:t\in\mathcal{R}\}. Then

\{v\geq 0:v+D_s\in\mathcal{R}\}\stackrel{d}{=}\mathcal{R}.

In fact, the converse holds as well. Any random set with this regenerative property is the range of some subordinator. Note that D_s is some kind of dual to X, since it is increasing, and the regenerative property induces some Markovian properties.

In particular, we consider the last passage time g_t=\sup\{s<t:s\in\mathcal{R}\}, in the case of a stable subordinator with \Phi(\lambda)=\lambda^\alpha. Here, \mathcal{R} is self-similar with scaling exponent \alpha. The distribution of \frac{g_t}{t} is thus independent of t. In this situation, we can derive the generalised arcsine rule for the distribution of g_1:

\mathbb{R}(g_1\in ds)=\frac{\sin \alpha\pi}{\pi}s^{\alpha-1}(1-s)^{-\alpha}ds.

The most natural application of this is to the hitting time process of Brownian Motion, which is stable with \alpha=\frac12. Then g_1=S_1-B_1, in the usual notation for the supremum process. Furthermore, we have equality in distribution of the processes (see previous posts on excursion theory and the short aside which follows):

(S_t-B_t)_{t\geq 0}\stackrel{d}{=}(|B_t|)_{t\geq 0}.

So g_1 gives the time of the last zero of BM before time 1, and the arcsine law shows that its distribution is given by:

\mathbb{P}(g_1\leq t)=\frac{2}{\pi}\text{arcsin}\sqrt{t}.

Missing in Action?

Aside

Not much maths has been appearing here in the past few weeks. But I have been working…

As part of Part III, instead of sitting an extra exam paper I am writing an essay. I have chosen the topic of ‘Multiplicative Coalescence’ so have been hard at work reading various papers and articles. I’ve been writing some posts about the topic as practice for writing up the essay – in fact, it’s entirely possible that large chunks will end up featuring verbatim. As a result, to ensure I stay firmly on the correct side of the rules about plagiarism, I’m going to wait until after exam results are announced on June 20th before making these posts visible.