100k Views

Posted on March 9, 2015 by dominicyeo

When I started this blog, I implicitly made a promise to myself that I would be aiming for quality of posts rather than quantity of posts. Evaluating quality is hard, whereas one always feels some vague sense of purpose by seeing some measure of output increase. Nonetheless, I feel I have mostly kept this promise, and haven’t written that much solely for the sake of getting out another post. This post is something of an exception, since I noticed in the office on Friday that this blog was closing in on 100,000 page views. Some of these were not actually just me pressing F5 repeatedly. Obviously this is no more relevant an integer to be a threshold as any other, and one shouldn’t feel constrained by base 10, but it still feels like a good moment for a quick review.

Here are some interesting statistics over the $(3+\epsilon)$ years of this website’s existence.

175 posts, not including this one, or the three which are currently in draft status. This works out at about 4.7 posts a month. By some margin the most prolific period was May 2012, when I was revising for my Part III exams in Cambridge, and a series of posts about the fiddliest parts of stochastic calculus and network theory seemed a good way to consolidate this work. I’ve learned recently that PhDs are hard, and in fact it’s been a year since I last produced at least five posts in a month, if you discount the series of olympiad reports, which though enjoyable, don’t exactly require a huge amount of mathematical engagement.
By at least one order of magnitude, the most viewed day was 17th August 2014, when several sources simultaneously linked to the third part of my report on IMO 2014 in Cape Town. An interesting point to note is that WordPress counts image views separately to page views, so the rare posts which have a gallery attached count well in a high risk / high return sense. In any case, the analytics consider that this day resulted in 2,366 views by 345 viewers. During a typical period, the number of views per visitor fluctuates between roughly 1.5 and 1.8, so clearly uploading as many photos of maths competitions as possible is the cheap route to lots of hits, at least by the WordPress metric.

One might well expect the distributions involved in such a setup to follow a power-law. It’s not particularly clear from the above data about views per month since late 2012 whether this holds. One anomalously large data point (corresponding to the interest in IMO 2014) does not indicate a priori a power law tail… In addition, there is a general upward trend. Since a substantial proportion of traffic arrives from Google, one might naively assume that traffic rate might be proportion to amount of content, which naturally will grow in time, though it seems impractical to test this. One might also expect more recent posts to be more popular, though in practice this seems not to have been the case.
The variance in popularity of the various posts has been surprisingly large. At some level, I guess I thought there would be more viewers who browse through lots of things, but such people would probably do so from the home page, so it doesn’t show up as viewing lots of different articles. There is some internal linking between some pages, but not enough to be a major effect.
At either end of the spectrum, a post about coupling and the FKG inequality has received only 16 views in 2.5 years, while a guide to understanding the Levy-Khintchine formula has, in slightly less time, racked up 2,182 hits. There are direct reasons for this. Try googling Levy-Khintchine formula and see what comes up. In a sense, this is not enough, since you also need people to be googling the term in question, and picking topics that are hard but not super-hard at a masters level is probably maximising interest. But I don’t have a good underlying reason for why some posts should end up being more Google-friendly than others.
In particular, quality of article seems at best loosely correlated with number of views. This is perhaps worrying, both for my reputation, and for the future of written media, but we will see. Indeed, two articles on the Dubins-Schwarz theorem and a short crib sheet for convergence of random variables, both get a regular readership, despite seeming to have been written (in as much as a blog post can be) on the back of an envelope. I also find it amusing that the Dubins-Schwarz theorem is always viewed at the same time of the year, roughly mid-February, as presumably it comes up in the second term of masters courses, just like it did in my own.
By contrast, I remain quite pleased with the Levy-Khintchine article. It’s the sort of topic which is perfectly suited to this medium, since most books on Levy processes seem to assume implicit that their readers will already be familiar with this statement. So it seemed like a worthwhile enterprise to summarise this derivation, and it’s nice to see that others clearly feel the same, and indeed I still find some posts of this flavour useful as revision for myself.

This seemed like a particularly good data set in which to go hunting for power-laws. I appreciate that taking a print-screen of an Excel chart will horrify many viewers, but never mind. The above plot shows the log of page view values for those mathematical articles with at least 200 hits. You can see the Levy-Khintchine as a mild anomaly at the far left. While I haven’t done any serious analysis, this looks fairly convincing.
I haven’t engaged particularly seriously in interaction with other blogs and other websites. Perhaps I should have done? I enjoy reading such things, but networking in this fashion seems like a zero-sum game overall except for a few particularly engaged people, even if one gets a pleasing spike in views from a reciprocal tweet somewhere. As a result, the numbers of comments and out-going clicks here is essentially negligible.
Views from the UK narrowly outnumber views from the US, but at present rates this will be reversed very soon. I imagine if I discounted the olympiad posts, which are sometimes linked from UK social media, this would have happened already.
From purely book-keeping curiosity, WordPress currently thinks the following countries (and territories – I’m not sure how the division occurs…) have recorded exactly one view: Aaland Islands, Afghanistan, Belize, Cuba, Djibouti, El Salvador, Fiji, Guatemala, Guernsey, Laos, Martinique, Mozambique, New Caledonia, Tajikistan, US Virgin Islands, and Zambia. Visiting all of those would be a fun post-viva trip…

Conclusion

As I said, we all know that 100,000 is just a number, but taking half an hour to write this has been a good chance to reflect on what I’ve written here in the past three years. People often ask whether I would recommend that they start something similar. My answer is ‘probably yes’, so long as the writer is getting something out of most posts they produce in real time. When writing about anything hard and technical, you have to accept that until you become very famous, interest in what you produce is always going to be quite low, so the satisfaction has to be gained from the process of understanding and digesting the mathematics itself. None of us will be selling the musical rights any time soon.

I have two pieces of advice to anyone in such a position. 1) Wait until you’ve written five posts before publishing any of them. This is a good test of whether you actually want to do it, and you’ll feel much more plausible linking to a website with more than two articles on it. 2) Don’t set monthly post count targets. Tempting though it is to try this to prevent your blog dying, it doesn’t achieve anything in the long term. If you have lots to say, say lots; if you don’t, occasionally saying something worthwhile feels a lot better when you look back on it than producing your target number of articles which later feel underwhelming.

I don’t know whether this will make it to $6+2\epsilon$ years, but for now, I’m still enjoying the journey through mathematics.

Real Trees – Root Growth and Regrafting

Posted on March 9, 2015 by dominicyeo

Two weeks ago in our reading group meeting, Raphael told us about Chapter Five which introduces root growth and regrafting. One of the points of establishing the Gromov-Hausdorff topology in this book was to provide a more natural setting for a discussion of tree-valued processes. Indeed in what follows, one can imagine how to start the construction of a similar process for the excursions which can be used to encode real trees, involving cutting off sub-excursions above one-sided local minima, then glueing them back in elsewhere. But taking account of the equivalence structure will be challenging, and it is much nicer to be able to describe cutting a tree in two by removing a single point without having to worry about quotient maps.

We have seen in Chapter Two an example of a process defined on the family of rooted trees with n labelled vertices which has the uniform rooted tree as an invariant distribution. Given a rooted tree with root p, we choose uniformly at random a vertex p’ in [n] to be the new root. Then if p’=p we do nothing, otherwise we remove the unique first edge in the path from p’ to p, giving two trees. Adding an edge from p to p’ completes the step and gives a new tree with p’ as root. We might want to take a metric limit of these processes as n grows and see whether we end up with a stationary real tree-valued process whose marginals are the BCRT.

To see non-trivial limiting behaviour, it is most interesting to consider the evolution of a particular subtree (which includes the root) through this process. If the vertex chosen for cutting lies in our observed subtree, then the subtree undergoes a prune and regraft operation. On the other hand, if the vertex chosen for cutting does not lie in the subtree, then we do not see any effect of the pruning, except the addition of a new vertex below the original root, which becomes the new root. So essentially, from the point of view of our observed subtree, the root is growing.

Now we can think about interpreting the dynamics of a natural limit process acting on real trees. The key idea is that we don’t change the set on which the tree is supported much, but instead just change the metric. In particular, we will keep the original tree, and add on length at unit rate. Of course, where this length gets added on entirely determines the metric structure of the tree, but that doesn’t stop us giving a simple ‘name’ for the extra length. If we consider a process $X^T$ starting from a particular finite subtree T, then at time t, the tree $X^T_t$ is has vertex set $T \coprod (0,t]$ . (Finite subtree here means that it has finite total length.)

Root regrafting should happen at a rate proportional to the total length of the current observed tree. This is reasonable since after all it is supported within a larger tree, so in the discrete case the probability of a prune-regrafting event happening within a given observed subtree is proportional to the number of vertices in that subtree, which scales naturally as length in the real tree limit. It turns out that to get unit rate root growth with $\Theta(1)$ rate prune-regrafting, we should consider subtrees of size $\sqrt{n}$ within a host tree of size n as $n\rightarrow\infty$ . We also rescale the lengths by $\frac{1}{\sqrt{n}}$ , and time by $\sqrt{n}$ so we actually see prune-regraft events.

Furthermore, if the subtree is pruned, the location of the pruning is chosen uniformly by length of the current observed subtree. So we can view the pruning process as being driven by a Poisson point process with intensity given by the instantaneous length measure of the tree, which at time t has vertex set $T\coprod (0,t]$ . It will turn out to be consistent that there is a ‘piecewise isometry’ for want of a better phrase between the metric (and thus length measure) on $X^T_t$ and the canonical induced measure on $T\coprod (0,t]$ , so we can describe the instances and locations of the pruning events via a pair of PPPs. The first is supported on $T \times [0,\infty)$ , and the second on $\{(t,x): 0 \le x \le t\}$ , since we only ‘notice’ pruning at the point labelled x if the pruning happens at some time t after x was created.

If we start from a compact tree T, then the total intensity of this pair is finite up to some time t, and so we have a countable sequence $\tau_0=0<\tau_1<\tau_2<\ldots$ of times for pruning events. It is easy to describe (but a bit messy to notate) the evolution of the metric between these pruning times. Essentially the distance between any pair of points in the observed tree at time $\tau_m$ with root $\rho_{\tau_m}$ is constant between times $\tau_m,\tau_{m+1}$ , and new points are added so that the distance between $\rho_{\tau_m}$ and any new point $a\in(\tau_m,\tau_{m+1}]$ is $a-\tau_m$ , and everything thing else follows from straightforward consideration of geodesics.

When a pruning event happens at point $x_m$ at time $\tau_m$ , distances are preserved within the subtree above $x_m$ in $X^T_{\tau_m -}$ , and within the rest of the tree. Again, an expression for the cross distances is straightforward but requires a volume of notation not ideally suited to this medium.

The natural thing to consider is the coupled processes started from different subtrees (again both must contain the original root) of the same host tree. Say $T^1,T^2\le T$ , then it is relatively easy to check that $X^{T^1}_t,X^{T^2}_t \le X^T_t \,\forall t$ , when we drive the processes by consistent coupled Poisson processes. Furthermore, it is genuinely obvious that the Hausdorff distance between $X^{T^1}_t,X^{T^2}_t$ , here viewed as compact subsets of $(X^T_t, d^T_t)$ remains constant during root growth phase.

Less obvious but more important is that the Hausdorff distance decreases during regrafting events. Suppose that just before a regrafting event, the two subtrees are T’ and T”, and the Hausdorff distance between them is $\epsilon$ . This Hausdorff distance is with respect to the metric on the whole tree T. [Actually this is a mild abuse of notation – I’m now taking T to be the whole tree just before the regraft, rather than the tree at time 0.]

So for any $a\in T'$ , we can choose $b\in T''$ such that $d_T(a,b)\le \epsilon$ . This is preserved under the regraft unless the pruning point lies on the geodesic segment (in T) between a and b. But in that case, the distance between a and the pruning point is again at most $\epsilon$ , and so after the regrafting, a is at most $\epsilon$ away from the new root, which is in both subtrees, and in particular the regrafted version of T”.

This is obviously a useful first step on the path to proving any kind of convergence result. There are some technicalities which we have skipped over. It is fairly natural that this leads to a Markov process when the original tree is finite, but it is less clear how to define these dynamics when the total tree length is infinite, as we don’t want regrafting events to be happening continuously unless we can bound their net effect in some sense.

Last week, Franz showed us how to introduce the BCRT into matters. Specifically, that BCRT is the unique stationary distribution for this process. After a bit more work, the previous result says that for convergence properties it doesn’t matter too much what tree we start from, so it is fine to start from a single point. Then, the cut points and growth mechanism corresponds very well to the Poisson line-breaking construction of the BCRT. With another ‘grand coupling’ we can indeed construct them simultaneously. Furthermore, we can show weak convergence of the discrete-world Markov chain tree algorithm to the process with these RG with RG dynamics.

It does seem slightly counter-intuitive that a process defined on the whole of the discrete tree converges to a process defined through subtrees. Evans remarks in the introduction to the chapter that this is a consequence of having limits described as compact real trees. Then limitingly almost all vertices are close to leaves, so in a Hausdorff sense, considering only $\sqrt{n}$ of the vertices (ie a subtree) doesn’t really make any difference after rescaling edge lengths. I feel I don’t understand exactly why it’s ok to take the limits in this order, but I can see why this might work after more checking.

Tomorrow, we will have our last session, probably discussing subtree prune-and-regraft, where the regrafting does not necessarily happen at the root.

RMM 2015 – UK Team Blog Part Two

Posted on March 3, 2015 by dominicyeo

Saturday 28th Feburary

There is much to squeeze into the programme, and so the second paper starts an hour earlier. James and I spend the day based at Tudor Vianu, the specialist maths and computing school that has hosted this competition since its first incarnation in 2008. Even coming from schools which regularly send students to such international competitions, we find it remarkable to see how much explicit emphasis they place on academic excellence here. Where British observers might expect lists of prefects and photos of glorious football teams, here instead we see students posing with medals and Romanian flags from contests around the world.

Our first task is to coordinate yesterday’s problems. Qs 1 and 3 are agreed extremely rapidly, with the problem captains very complimentary of the UK boys’ number theory solutions. Q2 has all the ingredients to suggest a long slog, but coordinators Lucian Turea and Radu Gologan have clearly thought very carefully about the UK scripts. Everything they say is sensible and easy to make consistent, so we are finished and happy comfortably within our 20 minute slot.

James and I also have to supervise the Romanian scripts for Qs 2 and 3 as these are British submissions. My schoolboy Latin helps a little bit, and we eventually agree on how to pair up comments in the solutions with points on the markscheme just in time to meet our students as they finish. Joe is full of excitement, having completed all three in the closing moments, while others are disappointed, having been slightly thrown by the geometry, but overall spirits are high.

The team are squirrelled off by the guides, and I have the afternoon to engage with the Q5 scripts. We have five solutions, and all are fine, but might not appear fine to a casual observer. Liam has opted for the Jackson Pollock approach to truth, where statements of various levels of interest and veracity are independently sprayed freely across three pages, though after a while I am convinced that every line does follow from something somewhere else on the page.

While working, I realise that having a ground floor room in an Eastern European hostel has its drawbacks. That said, opening the window gives the chance for an experiment to determine exactly which genre of music is found least appealing by lingering smokers. Enescu’s sonate dans le caractere populaire roumain proves successful, despite its local heritage.

I have a better idea what’s going on in all our students’ arguments in time to venture down to the slightly baffling Bucharest metro towards the farewell dinner, which retains its name despite not falling on the final evening. The students are deliberately separated from the leaders, but no attempt is made to enforce this and everyone mingles freely. This year the Chinese team comes from the Shanghai area, and their leader teaches at their high school. He has recently spent a term in Reading and, together with Warren and Harvey, we have a highly enthusiastic conversation about differences in education systems between our countries.

The UK students’ table seems to have been chosen for especially ponderous service, but the 30 seconds they are given between their desserts arriving and the bus arriving proves sufficient. I feel judged when I arrive back at my room and find the Hungarian deputy leader still working on his problematic geometry, so make sure to have at least a nominal further glance at our Q5s before setting an early alarm.

Sunday 1st March

The only people in Victory Square at 6.30am are stray dogs, and stray leaders heading to the school to prepare for their coordinations. I’m apprehensive about being asked to go through Harry’s solution to Q5 line-by-line, but though the effort to understand everything felt purposeful, it wasn’t necessary, as we get what we request almost immediately. Exactly the same thing happens on the other second day questions, so James and I are kicking our heels by 9.30, and the possibility of a return to bed feels very inviting while we wait for the other countries’ scores to clear.

Joe write: Meanwhile, we are at the mysterious ‘Hostel X’, in order to visit an ‘escape room‘. This was not actually as dubious as it first sounds. As Dominic explained, we were to be locked in a room for an hour during which we would have to solve a number of puzzles in order to escape. [DY: think of The Crystal Maze but with less leopard-print.] This turns out to be extremely enjoyable, as we gradually discover the collective significance of some masks, a chessboard and a couple of UV torches, but also quite difficult. Sam, Harvey, Andrei and I manage to escape with barely five minutes to spare but the others do not quite finish, although they assure us that their room was by far the more difficult of the two…

We meet the students, who are discussing Morse decoding and similar things with great enthusiasm. En route home, James thinks that we have been too hasty to accept a flaw in Joe’s solution to Q6, since it suddenly dawns that it could be fixed with the addition of a single $\ge$ sign. Our original coordinators have gone home, but chief coordinator Mihai Baluna graciously takes a second look, and agrees with our re-assessment, so James’ defibrillator can go back in the box.

The bronze and silver medal boundaries have settled naturally, and after brief discussion the jury decides to round up the number of golds to ten, which is surely the right decision. This leaves the UK with three honourable mentions, two silvers, and a gold. Though some of our students might be disappointed to lie just below a boundary, they all recognise that this contest features challenging problems and experienced contestants, many from countries with far more strenuous training programmes than ours. By any measure, this is a fantastic team performance, and James and I are very proud of them.

The closing ceremony is held in the atrium of Vianu school, and after an encouraging speech from the headteacher, the medals are awarded fairly swiftly. Joe reports that the hardest aspect of winning a gold at RMM is the necessity to smile on stage continuously for three minutes. Russia is announced as the winner of the team competition, with a very impressive set of performances, closely followed by the USA.

With the entire evening clear, the UK and USA teams head to Piata Romana to celebrate each other’s successes. The Romanian guides and the UK leadership have slightly different views about what constitutes an appropriate venue for this, but in the end everyone is entirely happy to gather in the common area at James’ hotel. This has been an excellent competition, and it is wonderful to see students, guides and leaders from all teams finding so much in common and much to learn from one another.

Monday 2nd March

My roommate departs for a train to Budapest at 4am, and the accommodation staff are enthusiastically dismantling the bunkbeds in the adjacent room at 6am, so it is fair to say I might have slept better. Two cars take us out to the airport, precisely one of which thinks we are having a race through the rush hour traffic. Suffice it to say, I would probably like to cycle round the Arcul de Triumf even less than its Parisian counterpart.

The students’ recently acquired metalwork doesn’t quite take us over the baggage weight limit. The Wizzair boarding procedure leaves a little to be desired, but the party looks keen for little except sleep, so it makes no difference to do this sparsely. As ever, the arrivals barriers at Luton only just manage to hold back the legions of adoring fans. Goodbyes are exchanged before we head our separate ways, though we will meet again for more worthwhile mathematics in just over three weeks at our next training camp in Cambridge.

RMM 2015 – UK Team Blog Part One

Posted on February 28, 2015 by dominicyeo

The UK was invited to send a team to the Romanian Master of Mathematics competition, held in Bucharest for the seventh time in 2015. This is a short account of what happened. There are moments when I wasn’t present, for which Joe reports on behalf of the students.

A pdf version with more details about the organisation of the contest, statements of the problems and a brief summary of results can be found here. Background and reports on similar competitions can be found here, including links to more comprehensive registers of hosted elsewhere.

Wednesday 25th February

We have spent the night at a hotel close to Luton Airport, so we can proceed to our flight on foot. Walking in front of a bright red sunrise to a bright orange terminal to depart on a bright pink plane leaves me with a sense of colour overload not experienced since I last watched South Pacific. The three hour flight to Bucharest is unremarkable. Sam has fallen asleep with pencil poised halfway through a long expression where every other term is $2012^{2012}$ , and Harvey makes rapid progress on a dodecahedronal Rubik’s Cube.

Soon afterwards we arrive in Romania and get lifts to the Moxa accommodation complex of the University of Economics where the students will stay. There are clearly mild cultural differences concerning what levels of privacy middle-aged adults might expect to enjoy, but the organisers have done a good job, and all is resolved satisfactorily. Of the students, Harry and Sam will share with two Brazilian boys who are due to arrive in the middle of the night, and the remaining four have a dorm to themselves, complete with precarious looking upper bunks.

Joe writes: Slightly surprisingly, we have been given seven guides, an entire Year 11 class at the Vianu school. Four of them take us on a walking tour round the central area of Bucharest, including the imposing Victory Square, and Herastrau Park. A sign informs us we should not toboggan down the brief slope between the path and the lake. We heed this advice.

Later in the evening, James and I diverge for the first leaders’ meeting. Old friendships are renewed, and the proceedings are informal and brief, allowing as much time as possible to get to grips with the questions. A proposed pair of papers is circulated by chief problem selector Ilya Bogdanov, and we get to work in James’ room. Our immediate impression is that we like them a lot, and this is reaffirmed over the coming hours as we explore them further.

Thursday 26th February

The leaders get to work finalising the papers. My confidence in the quality of the questions has grown even stronger overnight, and so I am not surprised when these are approved fairly rapidly. I propose swapping questions 3 and 5 based entirely on my own prejudice regarding their relative difficulty, and it turns out that others feel similarly, and this is approved.

Next, we must finalise a definitive wording of the questions before they are translated into languages for 14 other countries. Various people have strong views on commas, how many times one should use the word `let’ in a given sentence, and whether `open’ or `interior’ are more likely to be found ambiguous by students. Perhaps unexpectedly, a question submitted by the UK, courtesy of Lex Betts, causes the most problems for wording. In the end, it seems easiest to avoid ambiguity by completely rephrasing it in terms of the blackboard setup that will now appear as Q3 on the paper, accompanying Q2, the work of our own Jeremy King.

Joe writes: Meanwhile we enjoy a more comprehensive tour of Bucharest, past the old city and the Palace of the Parliament, then on to an excellent lecture by Calin Popescu. He tells us about topological dimension, and we learn that triangles are two-dimensional, though unsurprisingly the real challenge is deciding precisely what `triangle’ and `two-dimensional’ actually mean.

The opening ceremony is a well-organised affair in the grand university hall with several generous speeches from the mayor and other local dignitaries, and representatives of Tudor Vianu school. On the way home, the students examine their goodie bags, featuring various stationery and an RMM polo shirt. The leaders have not been missed out, though I wonder whether their guesses at sizes may have been informed by my predecessors? Certainly I will have to eat a lot of the omnipresent potato salad to run any danger of fitting into this item before the end of the competition…

After our winter camp in Hungary, the students are now connoisseurs of Eastern European cuisine, and remain unfazed by even the most remarkable display of gherkins. While James and I catch up on work, they relax before tomorrow’s festivities by starting another round of the card game which I am apparently not allowed to name. Suffice it to say, it has a similar quality to The Archers, offering a nonsensical background murmur which proves surprisingly supportive to research productivity.

Friday 27th February

Harry reports over breakfast that he spent some of the night helping dismantle a hyperactive burglar alarm, but it seems everyone is feeling well-prepared for the first day of the contest. James and I have carefully assembled a selection of fruit for the UK team’s refreshment, but, after Snow White themed questions regarding our intentions, the apples prove substantially more popular with the Hungarian students.

After approving answers to a handful of questions, mostly about the nature of the `first turn’ in Q2, we are free, so I return for a walk around the serpentine Herastrau Lake. The boundary of the lake seems to have Hausdorff dimension slightly greater than 1, but in any case, it is pleasant to stop halfway round its seemingly infinite perimeter to work on some problems about multitype branching processes. I also stop at the orthodox cathedral, from which my own college chapel could learn plenty about how a solemn space can be gold without being gauche.

Our students seem unsure whether to be upbeat or not, but we have a complete set of solutions claimed for Q1, and some cautious reports of progress on Q2. To avoid wasting time worrying about the recent past, some of the guides scoop up the Russian, American and UK teams for a walking tour of Bucharest old town and the stylish Cismigiu park. As in 2008, I observe that Bucharest enjoys a surfeit of excellently-equipped playgrounds almost everywhere, but a total absence of children using them. On this occasion, the younger members of our team are reluctant to rectify this.

I get started on the Q2s after dinner, and in a pleasing reversal of what often happens at some competitions, our two students claiming partial solutions have actually done rather better than they suggested. Sam in particular has been very clear about what he can and cannot do, and might even end up scoring seven. James and I convene at his hotel to discuss the challenging Q3 which seems to be equally clear-cut, so it is a hard-working evening, but a lot less drawn-out than it might have been. It is good to see that our recent active efforts to encourage the students to improve their write-up style are paying dividends.

Gromov-Hausdorff Distance on Trees

Posted on February 19, 2015 by dominicyeo

This post continues the exposition of Gromov-Hausdorff distance, as introduced in Chapter Four of Steve Evans’ Probability and Real Trees, which we are reading as a group in the Stats Dept in Oxford at the moment. In this post, we consider applications of the Gromov-Hausdorff distance we have just introduced in the context of trees, viewed as metric spaces.

First we consider a direct application of the previous result, which related the Gromov-Hausdorff distance to the infimum of the distortion across the family of correspondences between the two relevant metric spaces. I found this as Corollary 3.7 in notes by Le Gall and Miermont on scaling limits of random trees and maps, which can be found here. I’m not clear whether there is an original source, but the result is simple enough that probably it does not matter hugely.

Proposition – Given f,g excursions above [0,1], and $T_f, T_g$ the real trees associated with these excursions in the standard way, then

$d_{GH}(T_f,T_g)\le 2 ||f-g||.$

Proof: We construct an appropriate correspondence

$\mathcal {R}=\left\{(a,b) \,:\, \exists t\in[0,1]\text{ s.t. } a=p_f(t), b=p_g(t)\right\}.$

In other words, the trees are defined as projections from [0.1] (with some equivalence structure), so taking pairs of projections from [0,1] gives a natural correspondence. Now, suppose $(p_f(s),p_g(s)), (p_f(t),p_g(t))\in \mathcal {R}$ . Then

$d_{T_f}(p_f(s),p_f(t)) = f(s) + f(t) - 2\hat f(s,t),$

where $\hat f(s,t):= \min{r\in[s,t]}f(r)$ . Obviously, we can replace f by g to obtain

$d_{T_g}(p_g(s),p_g(t)) = g(s) + g(t) - 2\hat g(s,t).$

By thinking slightly carefully about where the functions achieve their minima compared with where the minimum in the sup norm is achieved, we can conclude that

$|d_{T_f}(p_f(s),p_f(t)) - d_{T_g}(p_g(s),p_g(t)) | \le 4||f-g||,$

and so the result follows from the relation between Gromov-Hausdorff distance and the infimum of distortions over the set of correspondences proved at the end of the previous post.

Gromov-Hausdorff Limits of Real Trees

If we are going to consider the Gromov-Hausdorff topology for limits of tree, we want to be sure that the limit of a sequence of real trees is another real tree. In particular, we want to show that this convergence preserves the property of being a geodesic space.

Theorem 4.19 – Given $X_n$ geodesic spaces, and $X$ complete, such that $X_n \stackrel{d_{GH}}\rightarrow X$ , then X is geodesic.

Proof: Here, I’ll go in the opposite order to Evans’ book, as I think it’s easier understand why a special case of this implies the whole result once you’ve actually shown that special case.

Anyway, we want to show that given $x,y\in X$ , there is a geodesic segment $x\leftrightarrow y$ in X. We will start by showing that there is a well-defined midpoint of the geodesic, that is a point $z \in X$ such that $d(x,z)=d(y,z)=\frac12 d(x,y)$ .

Given arbitrary $\epsilon>0$ , we can take n such that $d_{GH}(X,X_n) < \frac{\epsilon}{3}$ and then a correspondence $\mathcal{R}$ between $X,X_n$ with $\mathrm{dis}\mathcal {R}<\frac{2\epsilon}{3}$ . Now, by definition of correspondence, we have $x',y'\in X_n$ such that $(x,x'),(y,y')\in\mathcal{R}$ . But we do have geodesics in $X_n$ , so we can take $z'\in X_n$ the midpoint of geodesic $x'\leftrightarrow y'$ . Predictably, we now take $z\in X$ such that $(z,z')\in\mathcal {R}$ .

We can show that z is ‘almost’ the midpoint of [x,y] in the sense that

$|d(x,z) - \frac12 d(x,y)| \le |d(x',z')-\frac12 d(x',y')+\frac32 \mathrm{dis}\mathcal{R} \le \epsilon.$

Similarly, we have $|d(y,z)-\frac12 d(x,y)|\le \epsilon$ .

Perhaps it’s helpful to think of this point z that we’ve constructed as being like a taut, but not quite rigid string. The midpoint of the string has to be fairly near the midpoint of the endpoints, and in particular, as we let $\epsilon\rightarrow 0$ , the z’s we deal with form a Cauchy sequence, and thus converge to some point, which (in a case of poor notation planning) we also call $z \in X$ , which is the midpoint of $[x,y]$ as described before.

We can now iterate this iteration, to demonstrate that whenever q is a dyadic rational in [0,1], there exists $z_q \in X$ such that

$d(x,z_q)=q d(x,y),\quad d(y,z_q) = (1-q)d(x,y).$

Again then, if we want the above to hold for some general real r in [0,1], we can approximate r arbitrarily well by dyadic rationals q, and the associated points $z_q$ are Cauchy and thus have a well-defined limit with the required properties. We thus have our geodesic segment $x\leftrightarrow y$ .

Rooted Gromov-Hausdorff Distance

In the end, the trees we want to compare might be rooted. For example, we talk about finite trees being invariant under random re-rooting, and we might be interested in similar results for real trees, in particular the BCRT. So we need to compare metric spaces as viewed outwards from particular identified points of each space.

An isometry of rooted spaces must map the root to the root, and so we adjust to obtain rooted Gromov-Hausdorff distance. We might try to consider embeddings into a common space so that the roots are shared, but it will be more convenient to maintain the infimum over metrics on the disjoint union as before. But to ensure the roots are in roughly the ‘same’ place in both set embeddings, we minimise the maximum of the Hausdorff distance between the sets, and the distance between the images of the roots in the common covering space.

Similar results apply as in the unrooted case, and normally the proofs are very similar. As we might expect, when defining a correspondence between rooted spaces, we demand that the pair of roots is one of the roots in the correspondence, and then the same equivalence between the minimal distortion and the rooted G-H distance applies.

Evans shows that $\mathbb{T}^{\mathrm{root}}$ , the set of compact rooted trees is complete and separable under the rooted G-H topology. Separability is relatively easy to see. Compact trees have finite $\epsilon$ -nets, and there is a canonical way to view the net as the vertices of a finite tree with edge lengths. Approximating these edge lengths by rationals and consider the countable family of isomorphism classes of rooted finite trees gives separability.

If we want, we can also define k-pointed Gromov-Hausdorff distance, where we demand k points in each space are held fixed.

Tree $\eta$ -erasure

To show that this is a natural topology to consider for the family of trees, Evans devotes a short section to the operation of $\eta$ -erasure, where all points within $\eta$ of a leaf are removed from a given tree.

Formally, $R_\eta$ is a map $\mathbb{T}^{\mathrm{root}}\rightarrow \mathbb{T}^{\mathrm{root}}$ (recalling that these are compact real trees), so that $R_\eta(T)$ consists of the tree

$\{\rho\}\cup\{a \in T \, : \, \exists x\in T,\, a\in[\rho, x],d_T(a,x)\ge \eta\},$

rooted again at $\rho$ . We claim that the range of $R_\eta$ is the set of compact rooted trees with a finite number of leaves. In this setting, we want a geodesic definition of leaf, for example a leaf is a point that doesn’t lie in the interior of the (unique) geodesic segment between any other point and the root.

Given a tree T with a finite number of leaves, we can glue disjoint segments of length $\eta$ onto every leaf. Taking $R_\eta$ of this deeper tree will give T. Similarly, suppose $R_\eta(T)$ has infinitely many leaves, which we can label $a_1,a_2,\ldots$ . Thus we also have $x_1,x_2,\ldots \in T$ such that $a_i\in[\rho,x_i]$ , and the segments $\{[a_i,x_i]\}$ are disjoint, and all have length at least $\eta$ , hence T cannot be compact, as it has no finite $\frac{\eta}{2}$ net.

It is clear that for fixed T, the family of these maps applied to T is continuous with respect to $\eta$ in the G-H topology. When $\eta$ is changed a small amount, the amount of extra tree removed is locally small, and so approximating correspondences by points in what is left is absolutely fine. Indeed, the operations $T_{\eta_1}, T_{\eta_2}$ commute to give $T_{\eta_1+\eta_2}$ .

We want to show that for fixed $\eta$ this map $R_\eta$ is continuous with respect to G-H topology. Suppose two compact rooted trees S,T are covered by a rooted correspondence $\mathcal R$ with distortion $\epsilon \ll \eta$ . We can’t immediately restrict $\mathcal R$ to $R_\eta(S)\times R_\eta(T)$ , as it won’t necessarily be a surjection under the projection maps any more.

But we can get around this. Note that if $(x,y)\in\mathcal{R}$ , then $|d_S(\rho_S,x) - d_T(\rho_T,y)| \le \epsilon$ by assumption. We will construct a correspondence $\mathcal R'$ on the erased trees as follows. Given $(x,y)\in\mathcal{R}$ , if $(x,y)\in R_\eta(S)\times R_\eta(T)$ , we keep it, and if $x\not\in R_\eta(S), y\not \in R_\eta(y)$ , we throw it away. Suppose we have $(s,t) in \mathcal{R}$ with $s\in R_\eta(S), t\not \in R_\eta(T)$ . Let $l_s$ be a leaf of S such that $s \in [\rho_S,l_s]$ , and let $\bar t$ be the farthest point from the root of the geodesic $[\rho_T,t]$ restricted to $R_\eta(T)$ . So the tree above $\bar t$ includes t and has height at most $\eta$ .

In words, if a point appears in a pair in the correspondence but is removed by the erasure, we replace it in the pair with the point closest to the original point that was not removed by the erasure.

It remains to prove that this works. My original proof was short but false, and its replacement is long (and I hope true now), but will postpone writing this down either until another post, or indefinitely. The original proof by Evans and co-authors can be found as the main content of Lemma 2.6 in the original paper [1].

REFERENCES

[1] Evans, Pitman, Winter – Rayleigh processes, real trees, and root growth with regrafting.

Gromov-Hausdorff Distance and Correspondences

Posted on February 17, 2015 by dominicyeo

This term, some members of the probability group have been reading Probability and Real Trees, by Steve Evans based on his Saint-Flour course in 2005. A pdf can be found here. This morning was my turn to present, and I gave a precis of Chapter 4, which concerns metrics on metric spaces, a family of tools which will be essential for later chapters which discuss convergence of trees, viewed as metric objects. Hausdorff Distance We start by considering a metric on subsets of a given base space X. The Hausdorff distance between two sets A, B is defined as

$d_H(A,B):=\inf\{ r>0: A\subset U_r(B), B\subset U_r(A)\},$

where $U_r(A):=\{x\in X, d(x,A)< r\}$ consists of set A, and all the points within r of set A. So the Hausdorff distance measures how much we have to fatten each set before it contains the other. Note that if we have a giant set next to a tiny one, we will have to fatten the tiny one a great deal more to achieve this. Sometimes it will be more helpful to think of the following alternative characterisation

$d_H(A,B) = \max\left \{ \sup_{a\in A}\inf_{b\in B} d(a,b), \inf_{a\in A}\sup_{b\in B} d(a,b)\right\}.$

In words, we measure how far away is the point in A farthest from B, and vice versa, and take the larger of the two. The presence of the sups and infs indicates that the inclusion or otherwise of the boundaries of A,B does not affect this distance. In particular, this means that $d_H(A,\bar A) = d_H(A,A^{\circ})$ , and so to allow us to call Hausdorff distance a metric, we restrict attention to the closed subsets of X, M(X).

We also observe immediately that if X does not have bounded diameter, then it is possible for the Hausdorff distance between two sets to be infinite. We won’t worry about that for now, because we will mainly be considering host spaces which are compact, for which the following results will be useful.

Lemma 4.4 – If (X,d) is complete, then (M(X),d_H) is also complete.

Proof: Assume we have a sequence of closed sets $S_1,S_2,\ldots \subset X$ which have the Cauchy property under d_H. I’m going to do this slightly differently to Evans, because it’s not the case you can immediately choose $x_n\in S_n$ for each n, such that $d(x_n,x_m)\le d_H(S_n,S_m)$ for all m,n. For an explicit counterexample, see comment from Ed Crane below the article.

Note that if a subsequence of a Cauchy sequence converges to a limit, then the whole sequence converges to that same limit. So we can WLOG replace $S_1,S_2,\ldots$ by some subsequence such that $d_H(S_n,S_{n+1})\le 2^{-n}$ . Now it is clear that for any $x_n\in S_n$ , there is a choice of $x_{n+1}\in S_{n+1}$ such that $d(x_n,x_{n+1})\le 2^{-n}$ (*). Starting from arbitrary $x_1\in S_1$ , we can construct in this manner a sequence $x_1,x_2,\ldots,\in X$ that is Cauchy, and thus has a limit point $x\in X$ .

Let $\mathcal{X}$ be the set of sequences $(x_m,x_{m+1},\ldots)$ for some m, with $x_n\in S_n\,\forall n\ge m$ , satisfying (*). Now let S be the closure of the set of limit points of this family of sequences, which we have shown is non-empty.

Then for any n, and any $x_n\in S_n$ , we can construct such a sequence, and its limit point x, and the triangle inequality down the path $x_n,x_{n+1},\ldots$ gives $d(x_n,S)\le 2^{-(n-1)}$ . Furthermore, by construction $S\subset U_{2^{-(n-1)}}(S_n)$ , hence it follows that $S_n \stackrel{d_H}\rightarrow S$ .

Lemma 4.5 – Given (X,d) compact, (M(X),d_H) is also compact.

Sketch proof: We are working with metric spaces, for which the existence of a finite $\epsilon$ -net for every $\epsilon>0$ is equivalent to compactness. [An $\epsilon$ -net is a set S of points in the space such that every point of the space lies within $\epsilon$ of an element of S. Thinking another way, it is the set of centres of the balls in a finite covering of the space by $\epsilon$ -balls.] It is not too hard to check that if $S_\epsilon$ is an $\epsilon$ -net for (X,d), then $\mathcal{P}(S_\epsilon)$ is finite, and an $\epsilon$ -net for (M(X),d_H).

Gromov-Hausdorff Distance

So far this is fine, but won’t be useful by itself for comparing how similar two trees are as metric spaces, because we can’t be sure a priori that we can embed them in a common host space. To resolve this, we consider instead the Gromov-Hausdorff distance, which will serve as a distance between metric spaces, even when they are not canonically defined as subsets of a common metric space.

Given X, Y metric spaces, we define

$d_{GH}(X,Y)=\inf_Z \left\{ d_H(X',Y') \, : \, X',Y' \subset (Z,d)\text{ a metric space }, X'\simeq X, Y'\simeq Y\right\}.$

In words, the Gromov-Hausdorff distance between two metric spaces examines the ways to embed them isometrically into a common larger metric space, and gives the minimal Hausdorff distance between them under the class of such embeddings. One issue is that the collection of all metric spaces is not a set. For example, given any set, we can define a metric via the discrete metric, so the collection of metric spaces is at least as large as the collection of all sets, which is not a set. Fortunately, all is not broken, as when we consider a general metric space Z in which we might embed copies of X and Y we are wasting lots of the perhaps very complicated space, because we only need to compare the subsets which are isometric copies of X and Y. So in fact, we lose nothing if we assume that Z is a disjoint union of copies of X and Y, with a metric chosen appropriately. So

$d_{GH}=\inf\left\{ d_H(X,Y) : d\text{ a metric on }X\coprod Y\text{ restricting to }d_X \text{ on }X,\, d_Y\text{ on }Y \right\}.$

In practice though, this is difficult to compute, since the set of things we have to minimize over is complicated. It turns out we can find an equivalent characterisation which will be easier to use in a number of examples, including the case of real trees which is the whole point of the course.

Correspondence and Distortion

We define a correspondence from X to Y to be

$\mathcal{R}\subset X\times Y\text{ s.t. } \pi_X(\mathcal {R}) = X, \, \pi_Y(\mathcal {R}) = Y,$

where $\pi_X,\pi_Y$ are the canonical projection maps from $X\times Y$ into $X,Y$ respectively. So we can think of a correspondence as being something like a matching from X to Y. In a matching, we insist that the projection maps into each set are injections, ie that each element of X (resp Y) can appear in at most one pair, whereas for a correspondence, we demand that the projection maps are surjections, ie that each element of X appears in at least one pair.

Then the distortion of a correspondence

$\mathrm{dis}(\mathcal{R}):= \sup\left\{ |d_X(x,x') - d_Y(y,y')| \,;\, (x,y),(x',y')\in \mathcal{R} \right\}.$

In words, if two sets are non-isomorphic, then a correspondence can’t describe an isometry between the sets, and the distortion is a measure of how far from being an isometry the correspondence is. That is, given a pair of pairs in the correspondence, for an isometry, the distance between the X-elements would be equal to the distance between the Y-elements, and the distortion measures the largest discrepancy between such pairs of pairs over the correspondence.

Theorem 4.11 – $d_{GH}(X,Y) = \frac12 \inf_{\mathcal{R}} (\mathrm{dis}\mathcal R)$ , where the infimum is taken over all correspondences $\mathcal{R}$ X to Y.

Remark: The RHS of this equivalence can be thought of as the set coupling between X and Y such that the pairs have as equal distances as possible.

Proof: Given an embedding into $X\coprod Y$ with $d_H(X,Y)<r$ , we have $\mathcal{R}$ with $\mathrm{dis}\mathcal {R}<2r$ , by taking:

$\mathcal{R}=\{(x,y): d(x,y)<r\}.$

From the definition of Hausdorff distance, it follows that the for every x, there is a y with d(x,y)<r, and hence the appropriate projection maps are projections.

So it remains to prove that $d_{GH}(X,Y)\le \frac12 \mathrm{dis}\mathcal{R}$ . We can define a metric on $X\times Y$ by

$d(x,y)=\int\left\{ d_X(x,x')+d_Y(y,y') + r \,:\, (x',y')\in \mathcal{R} \right\}.$

Then for any $x\in X$ , there is $(x,y)\in\mathcal{R}$ , and thus $d(x,y)\le r$ , and vice versa hence $d_H(X,Y)\le r$ .

It only remains to check that this is actually a metric. Let’s take $x,\bar x \in X$ , and so

$d(\bar x,y)\le \inf\{ d_X(x,\bar x) + d_X(x,x')+d_Y(y,y')+r \,: \, (x',y')\in\mathcal{R}\},$

so taking $d_X(x,\bar x)$ outside the brackets gives one form of the triangle inequality. We have to check the ‘other combination’ of the triangle inequality. We assume that the infima for $(x,y), (\bar x,y)$ are attained at $(x',y'),(\bar x',\bar y')$ respectively.

$d(x,y)+d(\bar x,y)= 2r+ d_X(x,x')+d_X(\bar x,\bar x') + d_Y(y,y')+d_Y(d,\bar y').$

But we also have $d_X(x',\bar x')-d_Y(y',\bar y')\ge -r$ from the definition of distortion, and so adding these gives the triangle inequality we want, and completes the proof of this theorem.corc

Enumerating Forests

Posted on February 16, 2015 by dominicyeo

I’ve just got back from a visit to Budapest University of Technology, where it was very pleasant to be invited to give a talk, as well as continuing the discussion our research programme with Balazs. My talk concerned a limit for the exploration process of an Erdos-Renyi random graph conditioned to have no cycles. Watch this space (hopefully very soon) for a fully rigorous account of this. In any case, my timings were not as slick as I would like, and I had to miss out a chunk I’d planned to say about a result of Britikov concerning enumerating unrooted forests. It therefore feels like an excellent time to write something again, and explain this paper, which you might be able to find here, if you have appropriate journal rights.

We are interested to calculate $a_{n,m}$ the number of forests with vertex set [n] consisting of m unrooted trees. Recall that if we were interested in rooted trees, we could appeal to Prufer codes to show that there are $m n^{n-m-1}$ such forests, and indeed results of Pitman give a coalescent/fragmentation scheme as m varies between 1 and n-1. It seems that there is no neat combinatorial re-interpretation of the unrooted case though, so Britikov uses an analytic method.

We know that

$a_{n,m}= \frac{n!}{m!} \sum_{\substack{k_1+\ldots+k_m=n\\ k_i\ge 1}} \prod_{j=1}^m \frac{k_j^{k_j-2}}{k_j!}.$

To see this, observe that the $k_j$ s correspond to the sizes of the m trees in the forest; $\frac{n!}{\prod k_j!}$ gives the multinomial number of ways to assign vertices to the trees; given the labels for a tree of size $k_j$ , there are $k_j^{k_j-2}$ ways to make up the tree itself; and $\frac{1}{m!}$ accounts for the fact that the trees have no order.

What we would really like to do is to take the uniform distribution on the set of all labelled trees, then simulate m IID copies of this distribution, and condition the union to contain precisely n vertices. But obviously this is an infinite set, so we cannot choose uniformly from it. Instead, we can tilt so that large trees are unlikely. In particular, for each x we define

$\mathbb{P}(\xi=k) \propto \frac{k^{k-2} x^k}{k!}$ ,

and define the normalising constant

$B(x):= \sum_{k\ge 1} \frac{k^{k-2}x^k}{k!},$

whenever it exists. It turns out that $x\le e^{-1}$ is precisely the condition for $B(x)<\infty$ . Note now that if $\xi_1,x_2,\ldots$ are IID copies of $\xi$ , then

$\mathbb{P}(\xi_1+\ldots+\xi_m=n) = \frac{x^n}{B(x)^m} \sum_{k_1+\ldots + k_m=n} \prod_{j=1}^m \frac{k_j^{k_j-2}}{k_j!},$

and so we obtain

$a_{n,m}= \frac{n!}{m!} \frac{B(x)^m}{x^n} \mathbb{P}(\xi_1+\ldots + \xi_m=n).$

So asymptotics for $a_{n,m}$ might follows from laws of large numbers of this distribution $\xi$ .

So far, we haven’t said anything about how to choose this value x. But observe that if you want to have lots of trees in the forest, then the individual trees should generally be small, so we take x small to tilt away from a preference for large trees. It turns out that there is a similar interpretation of criticality for forests as for general graphs, and taking x equal to 1/e, its radius of convergence works well for this setting. If you want even fewer trees, there is no option to take x larger than 1/e, but instead one can use large deviations machinery rather than laws of large number asymptotics.

We will be interested in asymptotics of the characteristic function of $\xi$ for x=1/e. In particular $\mathbb{E}[e^{it\xi}]=\frac{B(xe^{it})}{B(x)}$ , and it will be enough to clarify the behaviour of this as $t\rightarrow 0$ . It’s easier to work with a relation analytic function

$\theta(x)=\sum_{k\ge 1} \frac{k^{k-1}x^k}{k!},$

ie the integral of B. What now feels like a long time ago I wrote a masters’ thesis on the subject of multiplicative coalescence, and this shows up as the generating function of the solutions to Smoluchowski’s equations with monodisperse initial conditions, which are themselves closely related to the Borel distributions. In any case, several of the early papers on this topic made progress by establishing that the radius of convergence is 1/e, and that $\theta(x)e^{-\theta(x)}=x$ everywhere where $|x|\le 1/e$ . We want to consider x=1/e, for which $\theta=1$ .

Note that $\mathbb{E}\xi = \frac{\theta(x)}{B(x)}$ , so we will make progress by relating $B(x),\theta(x)$ in two ways. One way involves playing around with contour integrals in a fashion that is clear in print, but involves quite a lot of notation. The second way is the Renyi relation which asserts that $\theta(x)=B(x)+\frac{\theta(x)^2}{2}$ . We will briefly give a combinatorial proof. Observe that after multiplying through by factorials and interpreting the square of a generating function, this is equivalent to

$k^{k-1} = k^{k-2} + \frac12 \sum_{\substack{l+m=k\\l,m\ge 1}} l^{l-1}m^{m-1}\binom{k}{l},$

for all k. As we might expect from the appearance of this equality, we can prove it using a bijection on trees. Obviously on the LHS we have the size of the set of rooted trees on [k]. Now consider the set of pairs of disjoint rooted trees with vertex set [k]. This second term on the RHS is clearly the size of this set. Given an element of this set, join up the two roots, and choose whichever root was not initially in the same tree as 1 to be the new root. We claim this gives a bijection between this set, and the set of rooted trees on [k], for which 1 is not the root. Given the latter, the only pair of trees that leads to the right rooted tree on [k] under this mapping is given by cutting off the unique edge incident to the root that separates the root and vertex 1. In particular, since there is a canonical bijection between rooted trees for which 1 is the root, and unrooted trees (!), we can conclude the Renyi relation.

The Renyi relation now gives $\mathbb{E}\xi = \frac{\theta(x)}{B(x)}=2$ when x=1/e. If we wanted, we could show that the variance is infinite, which is not completely surprising, as the parameter x lies on the radius of convergence of the generating function.

Now, playing around with contour integrals, and being careful about which strands to take leads to the asymptotic as $t\rightarrow 0$

$\mathbb{E}[ e^{it\xi}] = 1+2it + \frac{2}{3}i |2t|^{3/2} (i\mathrm{sign}(t))^{3/2} + o(|t|^{3/2}).$

So from this, we can show that the characteristic function of the rescaled centred partial sum $\frac{\xi_1+\ldots+\xi_N-2N}{bN^{2/3}}$ converges to $\exp(-|t|^{3/2}\exp(\frac{i\pi}{4}\mathrm{sign} t))$ , where $b= (32/9)^{1/3}$ is a constant arising out of the previous step.

We recognise this as the characteristic function of the stable distribution with parameters 3/2 and -1. In particular, we know now that $\xi$ is in the domain of attraction for a stable-3/2 distribution. If we wanted a version of the central limit theorem for such partial sums, we could have that, but since we care about the partial sums of the $\xi_i$ s taking a specific value, rather than a range of values on the scale of the fluctuations, we actually need a local limit theorem.

To make this clear, let’s return to the simplest example of the CLT, with some random variables with mean $\mu$ and variance $\sigma^2<\infty$ . Then the partial sums satisfy

$\mathbb{P}(\mu N + a\sigma\sqrt{N} \le S_N \le \mu_N+b\sigma\sqrt{N}) \rightarrow \int_a^b f_{\mathcal N}(x)dx,$

as $N\rightarrow\infty$ . But what about the probability of $S_N$ taking a particular value m that lies between $\mu N+a\sigma \sqrt{N}$ and $\mu N + b\sigma \sqrt{N}$ ? If the underlying distribution was continuous, this would be uncontroversial – considering the probability of lying in a range that is smaller than the scale of the CLT can be shown in a similar way to the CLT itself. A local limit theorem asserts that when the underlying distribution is supported on some lattice, mostly naturally the integers, then these probabilities are in the limit roughly the same whenever m is close to $\mu N+a\sigma\sqrt{N}$ .

In this setting, a result of Ibragimov and Linnik that I have struggled to find anywhere in print (especially in English) gives us local limit theory for integer-supported distributions in the domain of attraction of a stable distribution. Taking p( ) to be the density of this distribution, we obtain

$bm^{2/3}\mathbb{P}(\xi_1+\ldots+\xi_m=n) - p(\frac{n-2m}{b m^{2/3}}) \rightarrow 0$

as $n\rightarrow\infty$ , uniformly on any set of m for which $z= \frac{n-2m}{bm^{2/3}}$ is bounded. Conveniently, the two occurrences of b clear, and Britikov obtains

$a_{n,m} = (1+o(1)) \frac{\sqrt{2\pi} n^{n-1/6}}{2^{n-m}(n-m)!} p(\frac{n-2m}{n^{2/3}},$

uniformly in the same sense as before.

The Yule Process

Posted on November 12, 2014 by dominicyeo

The second problem sheet for classes on the Applied Probability course this term features a long question about the Yule process. This is probably the simplest example of a birth process. It’s named for the British statistician George Udny Yule, though some sources prefer to call it the Yule-Furry process for the American physicist Wendell Furry who used it as a model of a radioactive reaction.

The model is straightforward. At any time there is some number of individuals in the population, and each individual gives birth to an offspring at constant rate $\lambda$ , independently from the rest of the population. After a birth has happened, the parent and child evolve independently. In the notation of general birth processes, the birth rate when there are n individuals is $\lambda_n=\lambda n$ .

Note that if we start with two or more individuals, the sizes of the two or more families of descendents evolve as a continuous-time Polya’s urn. The arrivals process speeds up with time, but the jump chain is exactly Polya’s urn. Unsurprisingly, the Yule process can be found embedded in preferential attachment models, and other processes which are based around Polya’s urn with extra information.

This is a discrete, random version of exponential growth. Since the geometric distribution is the discrete analogue of the exponential distribution, we probably shouldn’t be surprised to learn that this is indeed the distribution of the process at some fixed time t, when it is started from a single original ancestor. This is all we care about, since the numbers of descendents from each different original ancestors are independent. In general, the distribution of the population size at some fixed time will be negative binomial, that is, a sum of IID geometric distributions.

The standard method here is to proceed using generating functions. Conditioning on the first splitting time gives two independent copies of the original process over a shorter time-scale. One derives an ODE in time for the generating function evaluated at any particular value z. This can be solved uniquely for each z, and patching together gives the generating function of the distribution at any specific time t, which can be seen to coincide with the corresponding generating function of the geometric distribution with parameter $e^{-\lambda t}$ .

So we were trying to decide whether there might be a more heuristic argument for this geometric distribution. The method we came up with is not immediate, but does justify the geometric distribution in a couple of steps. First, we say that the birth times are $T_2,T_3,\ldots$ , so between times $[T_n,T_{n+1})$ there are n individuals, with $T_1:=0$ for concreteness. Then by construction of the birth process, $T_{n+1}-T_n\stackrel{d}{=}\mathrm{Exp}(\lambda n)$ .

We now look at these ‘inter-birth times’ backwards, starting from $T_{n+1}$ . Note that $\mathrm{Exp}(\lambda n)$ is the distribution of the time for the first of n IID $\mathrm{Exp}(\lambda)$ clocks to ring. But then, looking backwards, the next inter-birth time is thus the distribution of the time for one of (n-1) IID $\mathrm{Exp}(\lambda)$ clocks to ring. So by memorylessness of the exponential distribution (discussed at great length on the first problem sheet), we can actually take these (n-1) clocks to be exactly those of the original n clocks which did not ring first. Continuing this argument, we can show that the first (in the original time direction) inter-birth time corresponds to the time spent waiting for the final clock to ring. Rewriting this observation formally:

$T_{n+1}\stackrel{d}{=}\max\{X_i : X_1,\ldots,X_n\stackrel{\text{iid}}{\sim}\mathrm{Exp}(\lambda)\}.$ (*)

To return to justifying the geometric form of the distribution, we need to clarify the easiest relationship between the population size at a fixed size and these birth times. As we are aiming for the geometric distribution, the probability of the event $\{X_t>n\}$ will be most useful. Clearly this event is the same as $\{T_{n+1}<t\}$ , and from the description involving maxima of IID exponentials, this is easy to compute as $(1-e^{-\lambda t})^n$ , which is exactly what we want.

There are two interesting couplings hidden in these constructions. On closer inspection they turn out to be essentially the same from two different perspectives.

We have specified the distribution of $T_n$ at (*). Look at this distribution on the right hand side. There is a very natural way to couple these distributions for all n, namely to take some infinite sequence $X_1,X_2,\ldots$ of IID $\mathrm{Exp}(\lambda)$ random variables, then use initial sequences of these to generate each of the $T_n$ s as described in (*).

Does this coupling correspond to the use of these IID RVs in the birth process? Well, in fact it doesn’t. Examining the argument, we can see that $X_1$ gives a different inter-birth time for each value of t in the correspondence proposed. Even more concretely, in the birth process, almost surely $T_{n+1}>T_n$ for each n. This is not true if we take the canonical coupling of (*). Here, if $X_n<\max\{X_1,\ldots,X_{n-1}\}$ , which happens with high probability for large n, we have $T_{n+1}=T_n$ in the process of running maxima.

Perhaps more interestingly, we might observe that this birth process gives a coupling of the geometric distributions. If we want to recover the standard parameterisation of the geometric distribution, we should reparameterise time. [And thus generate an essentially inevitable temptation to make some joke about now having a Yule Log process.]

Let’s consider what the standard coupling might be. For a binomial random variable, either on [n] or some more exotic set, as in percolation, we can couple across all values of the parameter by constructing a family independent uniform random variables, and returning a 1 if $U_i>1-p$ and so on, where p is the parameter of a specific binomial realisation.

We can do exactly the same here. A geometric distribution can be justified as the first success in a sequence of Bernoulli trials, so again we can replace the relevant Bernoulli distribution with a uniform distribution. Take $U_1,U_2,\ldots$ to be IID U[0,1] random variables. Then, we have:

$X_t=\stackrel{d}{=}\bar X_t:= \max\{n: U_1,\ldots,U_{n-1}\ge e^{-\lambda t}\}.$

The equality in distribution holds for any particular value of t by constructing. But it certainly doesn’t hold uniformly in t. Note that if we define $\bar X_t$ as a process, then typically the jumps of this process will be greater than 1, which is forbidden in the Yule process.

So, we have seen that this Yule process, even though its distribution at a fixed time has a standard form, provides a coupling of such distributions that is perhaps slightly surprising.

Tightness in Skorohod Space

Posted on October 24, 2014 by dominicyeo

This post continues the theme of revising topics in the analytic toolkit relevant to proving convergence of stochastic processes. Of particular interest is the question of how to prove that families of Markov chains might have a process scaling limit converging to a solution of some stochastic differential equation, in a generalisation of Donsker’s theorem for Brownian motion. In this post, however, we address more general aspects of convergence of stochastic processes, with particular reference to Skorohod space.

Topological Background

I’ve discussed Skorohod space in a previous post. For now, we focus attention on compactly supported functions, D[0,T]. Some of what follows can be extended to the infinite-time setting easily, and some requires more work. Although we can define a metric on the space of cadlag functions in lots of ways, it is more useful to think topologically, or at least with a more vague sense of metric. We say two cadlag functions are close to one another if there is a reparameterisation of the time-axis, (a function [0,T] to itself) that is uniformly close to the identity function, and when applied to one of the cadlag functions, brings it close to the other cadlag function. Heuristically, two cadlag functions are close if their large jumps are close to one another and of similar size, and if they are uniformly close elsewhere. It is worth remembering that a cadlag function on even an unbounded interval can have only countably many jumps, and only finitely many with magnitude greater than some threshold on any compact interval.

For much of the theory one would like to use, it is useful for the spaces under investigation to be separable. Recall a topological space is separable if there exists a countable dense subset. Note in particular that D[0,T] is not separable under the uniform metric, since we can define $f_x(\cdot)=\mathbf{1}_{(\cdot \ge x)}$ for each $x\in[0,T]$ , then $||f_x-f_y||_\infty=1$ whenever $x\ne y$ . In particular, we have an uncountable collection of disjoint open sets given by the balls $\mathcal{B}(f_x,\frac12)$ , and so the space is not countable. Similarly, $C[0,\infty)$ is not separable. A counterexample might be given by considering functions which take the values {0,1} on the integers. Thus we have a map from $\{0,1\}^{\mathbb{N}}\rightarrow C[0,\infty)$ , where the uniform distance between any two distinct image points is at least one, hence the open balls of radius 1/2 around each image point give the same contradiction as before. However, the Stone-Weierstrass theorem shows that C[0,T] is separable, as we can approximate any such function uniformly well by a polynomial, and thus uniformly well by a polynomial with rational coefficients.

In any case, it can be shown that D[0,T] is separable with respect to the natural choice of metric. It can also be shown that there is a metric which gives the same open sets (hence is a topologically equivalent metric) under which D[0,T] is complete, and hence a Polish space.

Compactness in C[0,T] and D[0,T]

We are interested in tightness of measures on D[0,T], so first we need to address compactness for sets of deterministic functions in D[0,T]. First, we consider C[0,T]. Here, the conditions for a set of functions to be compact is given by the celebrated Arzela-Ascoli theorem. We are really interested in compactness as a property of size, so we consider instead relative compactness. A set is relatively compact (sometimes pre-compact) if its closure is compact. For the existence of subsequential limits, this is identical to compactness, only now we allow the possibility of the limit point lying outside the set.

We note that the function $C[0,T]\rightarrow \mathbb{R}$ given by $||f||_\infty$ is continuous, and hence uniform boundedness is certainly a required condition for compactness in C[0,T]. Arzela-Ascoli states that uniform boundedness plus equicontinuity is sufficient for a set of such functions to be compact. Equicontinuity should be thought of as uniform continuity that is uniform among all the functions in the set, rather than just within the argument of an individual particular function.

For identical reasons, we need uniform boundedness for relative compactness in D[0,T], but obviously uniform continuity won’t work as a criterion for discontinuous functions! We seek some analogue of the modulus of continuity that ignores jumps. We define

$\omega'_\delta(f):=\inf_{\{t_i\}} \max_i \sup_{s,t\in[t_{i-1},t_i)} |f(s)-f(t)|,$

where the infimum is taken over all meshes $0=t_0<t_1<\ldots<t_r$ with $t_i-t_{i-1}>\delta$ . Note that as $\delta\downarrow 0$ , we can, if we want, place the $t_i$ so that large jumps of the function f take place over the boundaries between adjacent parts of the mesh. In particular, for a given cadlag function, it can be shown fairly easily that $\omega'_\delta(f)\downarrow 0$ as $\delta\rightarrow 0$ . Then, unsurprisingly, in a similar fashion to the Arzela-Ascoli theorem, it follows that a set of functions $A\subset D[0,T]$ is relatively compact if it is uniformly bounded, and

$\lim_{\delta\rightarrow 0} \sup_{f\in A}\omega'_\delta(f)=0.$

Note that this ‘modulus of continuity’ needs to decay uniformly across the set of functions, but that we do not need to choose the mesh at level $\delta$ uniformly across all functions. This would obviously not work, as then the functions $\mathbf{1}_{(\cdot\ge x_n)}$ for any sequence $x_n\rightarrow x$ would not be compact, but they clearly converge in Skorohod space!

Tightness in C[0,T] and D[0,T]

Naturally, we are mainly interested in (probability) measures on D[0,T], and in particular conditions for tightness on this space. Recall a family of measures is tight if for any $\epsilon>0$ , there exists some compact set A such that

$\pi(A)>1-\epsilon,\quad \forall \pi\in\Pi.$

So, for measures $(\mu_n)$ on D[0,T], the sequence is tight precisely if for any $\epsilon>0$ , there exists $M,\delta$ and some N such that for any n>N, both

$\mu_n(||f||_\infty >M)\le \epsilon,\quad \mu_n(\omega'_\delta(f)>\epsilon)\le \epsilon$

hold. In fact, the second condition controls variation sufficiently strongly, that we can replace the first condition with

$\mu_n(|f(0)|>M)\le \epsilon.$

Often we might be taking some sort of scaling limit of these processes in D[0,T], where the jumps become so small in the limit that we expect the limit process to be continuous, perhaps an SDE or diffusion. If we can replace $\omega'_\delta$ by $\omega_\delta$ , the standard modulus of continuity, then we have the additional that any weak limit lies in C[0,T].

In general, to prove convergence of some stochastic processes, we will want to show that the processes are tight, by demonstrating the properties above, or something equivalent. Then Prohorov’s theorem (which I tend to think of as a probabilistic functional version of Bolzano-Weierstrass) asserts that the family of processes has a weak subsequential limit. Typically, one then shows that any weak subsequential limit must have the law of some particular random process. Normally this is achieved by showing some martingale property (eg for an SDE) in the limit, often by using the Skorohod representation theorem to use almost sure subsequential convergence rather than merely weak convergence. Then one argues that there is a unique process with this property and a given initial distribution. So since all weak subsequential limits are this given process, in fact the whole family has a weak limit.

Where Do Probability Measures Come From?

Non-separable Skorohod Representations

Posted on October 16, 2014 by dominicyeo

In the previous post, I discussed the statement and proof of the Skorohod representation theorem. This concerns the conditions under which it is possible to couple distributions which converge in law, to obtain a family of random variable on a possibly very large probability space, which converge almost surely. The condition for the theorem to hold is that the base space, or at least the support of the limiting distribution should be a separable metric space. Skorohod’s original proof concerned the case where all the distributions were supported on a complete, separable metric space (Polish space), but this extension is not particularly involved, and was proven not long after the original result.

It is natural to ask exactly what goes wrong in non-separable or non-metrizable spaces. Recall a space is separable if it contains a countable dense subset. Obviously, finite or countable sets are by definition separable with any metric. Considering the points with rational coordinates shows that $\mathbb{R}^d$ is separable for each d, and the Stone-Weierstrass theorem shows that continuous functions with on a bounded interval are also separable with the uniform topology, as they can be approximated uniformly well by polynomials with rational coefficients. One heuristic is that a separable space does not have ‘too many’ open sets.

There are references (for example, see [2]) to examples of Skorohod non-representation in non-metrizable topological spaces, which are ‘big’ enough to allow convergence in distribution with respect to a particular class of test functions, but where the distributions are not uniformly tight, so cannot converge almost surely. However, I don’t really understand this well at all, and have struggled to chase the references, some of which are unavailable, and some in French.

Instead, I want to talk about an example given in [1] of a family of distributions on a non-separable space, which cannot be coupled to converge almost surely. The space is (0,1) equipped with the discrete metric, which says that $d(x,y)=1$ whenever $x\ne y$ . Note that it is very hard to have even deterministic convergence in this space, since the only way to be close to a element of the space is indeed to be equal to that element. We will construct random variables and it will unsurprising that they cannot possibly converge almost surely in any coupling, but the exact nature of the construction will lead to convergence in distribution.

Based on what we proved last time, the support of the limiting distribution will be non-separable. It turns out that the existence of such a distribution is equiconsistent in the sense of formal logic with the existence of an extension of Lebesgue measure to the whole power set of (0,1). This is not allowed under the Axiom of Choice, but is consistent under the slightly weaker Axiom of Dependent Choice (AC). This weaker condition says, translated into language more familiar to me, that every directed graph with arbitrary (and in particular, potentially uncountable) vertex set, and with all out-degrees at least 1 contains an infinite directed path. This seems obvious when viewed through the typically countable context of graph theory. But the natural construction is to start somewhere and ‘just keep going’ wherever possible, which involves making a choice from the out-neighbourhood at lots of vertices. Thus it is clear why this is weaker than AC. Anyway, in the sequel, we assume that this extension of Lebesgue measure exists.

Example (from [1]): We take $(X_n)_{n\ge 1}$ to be an IID sequence of non-negative RVs defined on the probability space $((0,1),\mathcal{B}(0,1),\mathrm{Leb})$ , with expectation under Lebesgue measure equal to 1. It is not obvious how to do this, with the restriction on the probability space. One example might be to write $\omega\in(0,1)$ as $\overline{\omega_1\omega_2\ldots}$ , the binary expansion, and then set $X_n=2\omega_n$ . We will later require that $X_n$ is not identically 1, which certainly holds in this example just given.

Let $\mu$ be the extension of Lebesgue measure to the power set $\mathcal{P}=\mathcal{P}(0,1)$ . Now define the measures:

$\mu_n(B)=\mathbb{E}_\mu(X_n \mathbf{1}_B),\quad \forall B\in\mathcal{P}.$

To clarify, we are defining a family of measures which also are defined for all elements of the power set. We have defined them in a way that is by definition a coupling. This will make it possible to show convergence in distribution, but they will not converge almost surely in this coupling, or, in fact, under any coupling. Now consider a restricted class of sets, namely $B\in \sigma(X_1,\ldots,X_k)$ , the class of sets distinguishable by the outcomes of the first k RVs.

[Caution: the interpretation of this increasing filtration is a bit different to the standard setting with for example Markov processes, as the sets under consideration are actually subsets of the probability space on which everything is defined. In particular, there is no notion that a ‘fixed deterministic set’ lies in all the layers of the filtration.]

Anyway, by independence, when n>k, by independence, we have

$\mu_n(B)=\mathbb{E}_\mu(X_n\mathbf{1}_B)=\mathbb{E}_\mu(X_n)\mathbb{E}_\mu(\mathbf{1}_B)=\mu(B).$

So whenever $B\in\mathcal{F}\bigcup_k \sigma(X_1,\ldots,X_k)$ , $\lim_n \mu_n(B)=\mu(B)$ . By MCT, we can extend this convergence to any bounded $\mathcal F$ -measurable function.

This is the clever bit. We want to show that $\mu_n(B)\rightarrow\mu(B)$ for all $B\in\mathcal P$ , but we only have it so far for $B\in\mathcal F$ . But since $\mathcal{F}\subset \mathcal P$ , which is the base field of the probability space under the (non-AC) assumption, we can take conditional expectations. In particular for any $B\in\mathcal P$ , $\mathbb{E}_\mu[\mathbf{1}_B | \mathcal{F}]$ is a bounded, $\mathcal F$ -measurable function. Hence, by definition of $\mu_n$ and the extended MCT result:

$\mu_n(B)=\mathbb{E}_\mu[X_n\mathbb{E}_\mu[\mathbf{1}_B|\mathcal F]]=\mathbf{E}_{\mu_n}[\mathbb{E}_\mu[\mathbf{1}_B|\mathcal F]] \rightarrow \mathbb{E}_\mu [\mathbb{E}_\mu[\mathbf{1}_B |\mathcal{F}]].$

Now, since by definition $\mathbf{1}_B$ is $\mathcal{P}$ -measurable, applying the tower law gives that this is equal to $\mu(B)$ . So we have

$\mu_n(B)\rightarrow \mu(B),\quad \forall B\in\mathcal{P}.$ (*)

This gives weak convergence $\mu_n\Rightarrow \mu$ . At first glance it might look like we have proved a much stronger condition than we need. But recall that in any set equipped with the discrete topology, any set is both open and closed, and so to use the portmanteau lemma, (*) really is required.

Now we have to check that we can’t have almost sure convergence in any coupling of these measures. Suppose that we have a probability space with random variables $Y,(Y_n)$ satisfying $\mathcal L(Y)=\mu, \mathcal L(Y_n)=\mu_n$ . But citing the example I gave of $X_n$ satisfying the conditions, the only values taken by $Y_n$ are 0 and 2, and irrespective of the coupling,

$\mathbb{P}(Y_n=2\text{ infinitely often})>0.$

So it is impossible that $Y_n$ can converge almost surely to any supported on [0,1].

References

[1] Berti, Pratelli, Rigo – Skorohod Representation and Disintegrability (here – possibly not open access)

[2] Jakubowski – The almost sure Skorokhod representation for subsequences in non-metric spaces.

Isomorphic groups from linear algebra

Eventually Almost Everywhere

A blog about probability and olympiads by Dominic Yeo