IMO 2013 – Part Four: Co-ordination and Close

Thursday 25th July

There is commotion at the adjacent (Netherlands?) table at breakfast when a large iguana steals a piece of bread then climbs onto a low-hanging branch to gloat over the spoils and relieve itself into their ceviche. Geoff and I also have some difficult encounters with the locals ahead today, as it is the first day of co-ordination.

This is the process by which the exam papers are marked. Geoff and I have looked at the UK students’ scripts, as have a team of local markers, called co-ordinators, who are split between the six questions. In an ideal world, all parties agree on the appropriate mark, so we can sign and head to the beach. In practice, however, the co-ordinators have very little reading time per solution, and are also responsible for ensuring the mark schemes are consistently applied.

Geoff has the 9am slot for Q4. Despite having prepared meticulous analysis of each UK student’s diagram dependency, we sign for 42/42 in a matter of seconds. Not such a baptism of fire after all. I am dealing with Q5 after lunch. They feel that Sahl has not finished the problem. I explain his argument in a slightly less minimalist fashion and they agree, getting the 41/42 we were looking for. We finish the day with Q1, which proves as straightforward as Q4.

Everyone is very pleased with progress so far, but also aware that tomorrow will be the tricky day, with the three hardest questions, including two which feature long combinatorial essays rather heavily. Geoff and I retire early to immerse ourselves in mathematics.

In the end I do spend a token amount of time asleep. Q6 is the main cause of my insomnia. Andrew has written a long argument that astonishingly combines both official solutions. Unfortunately he claims some results as trivial which the model answer devotes up to a page to proving, so we fear 6 is the best we can hope for, though explaining what is going on may take some time. Meanwhile Matei has come up with a very satisfying original argument, but has run out of time to finish it. In order to convince the co-ordinators that this will work, I cobble together the final steps and practice my speed-LaTeX while the sun rises.

Friday 26th July

First thing in the morning, and Geoff is trying to snare some partial marks on the hard geometry Q3. We feel Andrew deserves a point for some non-trivial progress in his rough work. The co-ordinators disagree and despite his entreaties we are forced to sign for a total of zero. The double combinatorics slog begins after lunch with Q2. We are able to get an extra mark for Gabriel bringing him to a total of 25 which will now surely be enough for a silver.

We are scheduled to be last to co-ordinate Q6, at 5.30pm. Aware that our arguments might take a while, and reluctant to hold up the machinations of the entire competition, we loiter and hope for an earlier slot. We end up with the problem captain for Q6 and the chief co-ordinator for all problems, so there would be no higher authority to resolve any disputes apart from an unprecedented (for the UK) appeal to the jury.

Daniel’s work turns out to be the main problem. He has not had much time, so has done the calculations for the increments of the inductive construction, and merely described how the induction itself works. The mark scheme looks very rigid, but appears to offer 4 marks for this, so I ask for that, and predictably the co-ordinators look surprised. We wrangle for a very long time indeed, but in the end I’m unable to convince them that despite the lack of proofs of the more technical part of the solution it is still worth at least 3. This extra mark would have earned Daniel a gold medal, so it is a shame, but he can perhaps draw some consolation from the fact that the regime was undoubtedly applied very fairly.

Matei and Andrew’s arguments also require lots of attention, and I am glad I prepared thoroughly, but in the end we get the 5 and 6 respectively that we wanted. They are now ensured strong gold medals. Geoff and I retire to the bar to toast what has been a record-breaking performance by the team, coming 9th overall, and top of the EU by some margin.

There follows the final jury meeting, where speeches are made by various team leaders, before the decision on the medal boundaries. There are no real controversies, and we end in good time to celebrate with our success and friends’ successes (not least a 15th place for Australia and top-ten individual score for AUS2 Alex Gunning) late into the night. I fear the supplies of Cachaca have been hit rather hard.

Saturday 27th July

The optional morning excursion to the nearby town of El Rodadero is generally spurned in favour of a lie-in and a final chance to enjoy the beach and the pool on the roof of my hotel. Since their well-deserved success may necessitate press releases and the like, the team are particularly encouraged to avoid obvious sunburn for the inevitable photos later.

The now-familiar convoy of buses gathers at dusk to transport the IMO to the nearby Quinta de San Pedro Alejandrino, site of Simon Bolivar’s impressive tomb, and location for the closing ceremony. First there are several speeches and performances from traditional singers and dancers. The mixing desk suffers some unfortunate problems, so the sound engineering for the ridiculously skilful young accordion player consists of a technician walking a single microphone from one side of the instrument to the other as the register changes.

The main event is the presentation of the medals. The UK students all do a good job of getting their Union Jacks in front of the competing flags from adjacent competitors. The space in front of the stage turns into a bit of a scrum of photographers. I turn out to be substantially bigger than the average South-East Asian mathematician, and so get some particularly suitable shots of our gold medallists.

During a further long sequence of dancing, everyone starts to drift away back towards the closing dinner at our Irotama hotel. It turns out that the British Maths Olympiad booklets have finally arrived at this late hour. Gabriel and his new friend from the Irish delegation do an excellent job of speedily distributing them amongst all the teams. After a slow start, the dance floor gradually fills while a table of deputy leaders watches on with a mixture of enthusiasm, concern and indifference. Some final goodbyes are said, others plan to chat the whole night away. This year’s IMO draws to a close.

Sunday 28th / Monday 29th July

We leave for picturesque Santa Marta airport after breakfast. It appears that some of the team have spent a non-zero time asleep. The short hop to Bogota is almost entirely made up of mathematicians, and there are plenty of paper pads and Rubik’s cubes out in the departure lounge (remembering of course that compasses can’t be taken in hand luggage).

A short change in Bogota is enlivened when the ever-suspicious Andrew Carlotti is summoned by the police. It turns out to be merely a random inspection… Geoff and I muse over plans for next year, and I learn that The Glass Bead Game is a very useful tool for getting to sleep much earlier than natural.

After a layover and much-needed triple espresso in Madrid, and an initial aborted landing at windy Heathrow, everyone is united with adoring parents and other fans. Despite Geoff’s best efforts, his dream of a flash-heavy welcome by the national press fails to come to fruition. We live in hope for next year.

IMO 2013 – Part Three: Opening Ceremony and Exams

Sunday 21st July

It turns out that the main entrance to the Hotel Irotama, the resort hosting the olympiad, is less than 100m from the entrance to the villas we’ve been staying. The jury remains out on whether that makes us the first team to arrive at an IMO on foot, not least because we are joined for this short but significant journey by the Australian and Israeli teams.

It’s another sticky and unpleasant day, but initial impressions are very favourable. The team have a pair of bungalows with dried leaves for roofs. Among other things, the air conditioning is working well! Lunch is available from beside the beach at a selection of restaurants, which have all been uniformised for the week. In any case, it is a pleasant reversal of the usual situation for the food to be high in quality and low in queueing time.

The UK students are immediately keen to meet other teams, starting with some of English-speaking countries, and moving on to the United States. The non-verbal school of interaction continues as a massive multi-national cross between water polo and rugby emerges in the pool, visible from my 11th floor balcony. The view across the bay as the sun sets are spectacular, even if the wind and the low railings do make me question the wisdom of the hammock strings above the jacuzzi?

Monday 22nd July

Today’s main event is the opening ceremony, which is being held in Barranquilla, near where the team leaders are currently based. The boards in the lobby advertise a sensible plan partitioning the teams into equal-sized classes alphabetically. We are bound for bus 20 with the USA and the enigmatic “others”, though disaster strikes when it transpires the buses provided are not equal in size. An appropriately weighted partition emerges organically, and we are on the move. The two-hour drive offers some views of the closest Colombia’s Caribbean can get to a rugged coastline and bustling towns offering a welcome contrast to the constant glossiness of the resorts.

The Opening Ceremony features the usual sequence of speeches, children’s choirs, and the procession of the teams. Barranquilla is Colombia’s fourth-largest city, and the economic centre of this region. The carnival held there annually is the most famous in South America outside of Rio. Even though that was six months ago, it is a nice touch to invite a selection of the dancers, acrobats and musicians to accompany each of the teams round the sports hall where the ceremony is taking place.

Other teams have extravagant rituals planned for their brief moment of limelight, but the UK students opt for a more reserved approach, apart from choosing at the last minute to hoist Sahl onto various shoulders. Having safely dismounted near the end of their circuit, they receive a bold thumbs-up from Geoff who is sitting in the leaders’ area, segregated on the other side of the arena. Whether this is a token of encouragement for tomorrow’s paper, or a show of delight in the minimalist choreography remains to be seen.

The festivities drag on a bit longer than planned, and after four hours hunger levels are becoming fractious. I don’t really want to know how long the turkey sandwiches had been slow-cooking in the sun, but for once it is convenient to have a solid component of vegetarians in the UK team. After an entire day of sitting around, I propose a brisk walk along the shore after dinner. We are prevented from leaving the Irotama’s portion of beach by a member of hotel security. I have a Deputy Leader’s badge. He has a gun. We make do with the view of the stars and the flotilla of ships lining up for the Panama Canal.

Tuesday 23rd July

It’s the first day of the competition and understandably the team are a bit nervous at breakfast. We follow the organisers’ instructions to the letter, and arrive almost an hour early at the exam hall, located at a similar hotel further down the road. After a final check of compasses and so forth, the team sally forth to their respective rooms, and the deputies return to the hotel and take a quick swim while waiting for some copies of the paper to materialise.

As the delay grows, the number of deputies waiting outside the office reaches what feels like a critical mass. It will transpire that some members of the Syrian team, who had been delayed by visa complications, have just arrived, and arrangements are being made for them to sit the paper before it is generally released. Ivan is able briefly to astonish onlookers by quoting instantly a solution to Q2, before revealing that it is in fact his question. We have about an hour to think about the problems before meeting the students.

The UK team are generally pleased with the paper, with five students claiming the first two questions, and some tentative offerings on the final question. We have a succession of more formal individual debriefs while walking back to the Irotama down the beach. Some of their arguments for Q1 sound rather more complicated than required, but hopefully it will all make sense when Geoff and I get to see the scripts. In the meanwhile, the UK students head to the pool, trying as much as possible to avoid comparisons with other teams and other non-helpful forms of post-mortem.

Wednesday 24th July

We allow ourselves the luxury of an extra 20 minutes at breakfast but along with many teams are still absurdly early for the second day’s exam. Today’s security is much tighter, and the deputies are not allowed into the conference building, so content ourselves with exchanging the national olympiad booklets and competing for the few patches of shade available from the baking morning sun.

Back at the resort, there is again no sign of the problems, so I use the freshly-unlocked Irotama wifi to sort out a very last-minute change of tenancy agreement and speak further with Colombian customs. Apparently the tax on a case of frisbees is 150,000 Pesos (a slightly less impressive sounding £50). My expectations remain low. It will transpire, however, that missing the official deputies excursion might have been a good idea. Reports are floating around of a 2 hour video and a bus tour with no actual stops.

After the paper we meet the team, who all seem very upbeat. Everyone claims solutions to Qs 4 and 5, with all but Warren resisting the temptation to deploy some form of co-ordinate method on the geometry. Andrew also claims Q6, so all in all everyone is rather pleased, and looking forward to an afternoon free to enjoy all that’s on offer at the competition site free now that the pressure is off.

Geoff joins us in time for dinner bearing the first day’s examination scripts and plenty of gossip about activities at the leaders’ site. However, our task for the evening is not a social one. The second day’s scripts arrive at about 8pm, and then we retire to devise our plan of attack. It makes sense to tackle three questions each, so I have a look through the Q5 scripts, and all seems fine, with the Q2 and Q6 answers to be addressed tomorrow. By comparison with the grapevine, it does look as if the UK might have done rather well indeed!

IMO 2013 – Part Two: Ashes and Santa Marta

Thursday 18th July

The third practice exam again proceeds smoothly. The first problem is a nice exercise by John Conway, on classifying sets of points which obey some intersection property. There were various ways to misread the problem, of which some students took full advantage, and an almost limitless number of ways to classify the satisfactory configurations. As a result the marking, which I chose to do outside, took ages, though at least I had the company of a few passing green lizards and a brief visit from an eagle.

The resort where we are staying, and in fact where the IMO itself will be held, is actually about 10km outside Santa Marta itself, so we decide to venture in to explore the town once marking is complete. The historical centre, though modelled on a grid, is very Mediterranean, with narrow streets wending their way underneath exposed municipal wiring down to the seafront. We pause outside the Cathedral, where Mass is just starting. The dry heat clearly not enough to discourage a very full and colourful set of vestments.

On the way down to the sea we pass a park featuring yet another statue of the most famous man to live (and in fact die) in Santa Marta. Our guide Maria looks horrified as one of the students asks “Simon Who?” Dinner ends up al fresco, where we are treated to the accordion playing and fire-juggling in the town square. How does some one take up fire-juggling one wonders? Are there beginner kits with just lightbulbs on the end? Very few of the party receive the meal they think they ordered, but all are satisfied nonetheless. The convoy of taxis departs into the night. I am in the second one and it is clear that the driver has no idea where he is going, and his dedication to staying within sight of his leader is admirable if occasionally terrifying.

Friday 19th July

To mix things up, today each team has set an IMO-style paper for the other to attempt. The UK team then has to mark the Australian scripts during the afternoon and vice versa, before co-ordinating the results with Ivan the Australian deputy leader and myself. It’s always a profitable exercise to have to struggle with poorly worded solutions as perhaps it will encourage everyone to avoid such things in the actual exam. Questions which fall into the realm of the combinatorial essay are always particularly at risk of large blocks of waffling prose, and each Q2 produces exactly that. Hopefully the students found the exercise useful as well as time-consuming.

Meanwhile, it seems that the UKMT-branded frisbees we ordered to distribute as gifts at the IMO have been held up somewhere in the intricacies of Colombian customs. Initial attempts to speak on the phone are hindered by my non-existent Spanish, and even an attempt to spell out my email address is fraught with the challenges of differing vowel pronunciations. I fear we may have to resign ourselves to being the stingy delegation at this competition…

I take advantage of a relatively free afternoon to sample the resort’s various pools and catch up on what’s been happening in the cricket. Our own version of the Ashes is taking place tomorrow, so hopefully the demolition happening at Lord’s is a good omen. Geoff and his brother are attempting to get the hashtag #otherashes trending. So far we have one tweet (by me) and a mention in the Guardian cricket feed. From tiny acorns…

Saturday 20th July

And so to the final practice exam of this pre-IMO camp, the Mathematical Ashes. I was a student in 2008 for the inaugural competition, the only time the UK has lost, and so in keeping with the cricket tradition the ceremonial funeral urn is filled with the ashes of UK mathematics, including a geometry question in my handwriting. (In fact, the pyre formed during an excursion after the IMO in Madrid got a bit out hand, and so it probably contains a comparable amount of Australian material.)

As for the other exams, we are using questions from last year’s IMO shortlist, that is, problems that were considered for inclusion by the jury, but not selected. The first two chosen are at the easier end of the IMO difficulty spectrum, while the third is really very awkward indeed. Post-exam, the teams compare notes and it seems that it will be tight, so Ivan and I divide up the questions, devise brief mark schemes and get going. Three hours later we feel happy with our conclusion: UNK 82, AUS 81. In reality, by far the most pleasing aspect is that both teams have demolished the two easier questions with such aplomb. This bodes very well for the IMO itself next week.

A wager is placed that less than 10 minutes will elapse between emailing Joseph Myers, custodian of the IMO Register and the BMOS website, and the results appearing on the latter. The placer of this wager turns out to be rather wise. We await a flood of hits on the OtherAshes blog. Meanwhile, we pay our final visit to the Santorini resort restaurant, who have accommodated our various dietary specifications and comical Spanish with elan. I order at random from the fish and seafood section and end up with a steak topped with guacamole. Definitely not complaining. Everyone heads back feeling understandably excited for the start of the main event tomorrow.

IMO 2013 – Part One: Travel and Training

Preamble

Six years ago in Rhodes, Tom Lovering and I started what has now become a strong tradition of preparing an unofficial report about maths competitions from the student perspective. It seems appropriate to attempt to continue this in my new role as the Deputy Leader of this year’s UK team at the IMO. And since I have excellent wifi and a (just about) active maths blog, there seems no reason not to do this in real time, at least to a first approximation. I’m sure fans all around the world will be glued to their screens.

I should briefly explain what the IMO is. The acronym stands for International Mathematical Olympiad, and it is a competition held every year in July, welcoming school students from over 100 countries. Tempting though it is to picture a drawn-out global version of the ‘mathletics’ scene at the end of Mean Girls, the reality is somewhat different. Each country sends six students, who sit two 4.5 hour exams, each with three questions, in roughly increasing order of difficulty. It does however remain the case that you get jackets if you make the finals, admittedly with polyester rather than leather sleeves. Medals are awarded to roughly half of the participants.

Each team has a leader, who arrives early to help set the paper, and also assesses their team’s scripts, presenting their marks for approval by a board of co-ordinators supplied by the host country. Each team also has a deputy leader, who stays with the team initially, then joins the leader for this marking process.

As well as the competitive side, the olympiad is a great opportunity to meet other young mathematicians from all around the world. Certainly I am still in touch with many of the people I met when I was lucky enough to compete in Vietnam and Madrid (2007, 2008 respectively). As the competition moves country every year, it’s also a great chance to see some exciting places. This year it is in Santa Marta on Colombia’s Caribbean coast, after Buenos Aires in 2012.

Anyway, on with the report.

Sunday 14th July

I spend the morning packing up my room as I am moving to a new flat pretty much directly after this trip. Everything seems a lot clearer after sorting out the IMO team uniform which has arrived just in time leaving my floor essentially invisible under a sea of boxes. The mini-crisis wherein they were all delivered without my knowledge to the Worcester College kitchens seems but a distant memory…

We are flying at a painfully early hour tomorrow morning, so it makes sense to spend the night at an airport hotel. Courtesy of the satnav, I learn the hard way that there are three Holiday Inns at Heathrow. Geoff, Bev and I are the first to arrive, and wait for the students, two of whom are arriving directly from Copenhagen, bearing prizes and stories from the analogous physics competition just finished there. Parents are reassured that the occasional email and postcard will be sent and we retire in preparation for tomorrow’s Odyssey.

Monday 15th July

Up at 4.30am for the first leg over to Madrid. With time for little other than a quick espresso, straight onto the transatlantic flight to Bogota. The ten hours afford plenty of time to catch up on reading some papers. Had a think about how these results about (uniform) random forests might affect our thoughts about frozen percolation, and took advantage of the increasing tedium to do a long rate function calculation I’d been putting off for ages. I think the answer is – the question is somewhat more interesting…

Also relish the chance to spend several hours diving into Love in the Time of Cholera, having figured that this was almost certainly a once-in-a-lifetime opportunity to explore a Colombian novelist while in Colombia. So far, so good. In particular, much more interesting than One Hundred Years of Solitude, or perhaps my tastes have changed in the past few years?

We learn courtesy of Iberia that tuna, peach and olives do not make a good sandwich combination, and wonder whether they will be able to resist the temptation to follow every announcement with a synthesised rendition of the Concierto de Aranjuez. A slight delay changing at Bogota airport allows sufficient time for extra sushi and further progress through the example sheet solutions I’ve offered to before the short hop north to Santa Marta. Gabriel’s cynicism about the fate of our luggage turns out to be unfounded, but the two panama hats packed in my suitcase have not enjoyed the trip at all. The Santorini Hotel seems ill-prepared for a group arrival at 10.30pm, but eventually we obtain keys and pay. Shortly afterwards, we are able to unpay one of the bills that they have charged us twice within the space of five minutes. With everyone very grateful for the violent air conditioning, we head for much overdue sleep.

Tuesday 16th July

Up at dawn from the jetlag, but a useful moment to sort out the details for the first practice exam. This pre-IMO camp is a joint venture with the Australian team, and both sets of students are sitting an IMO style exam each morning. The villa we are occupying is somewhat sort on table space, but the three UK students perched on the kitchen bar with their scripts claim that it is fine. If IMO 2008 is anything to go by, where the desks for the competition were so steeply sloped that pens became more valuable as paperweights than as writing equipment, this might be useful practice.

While the students are getting on with the festivities, Bev and I explore various local food options, I study a couple of papers and explore the beach, though the humidity is rather cloying in the middle of the day. The UK team make confident noises about the exam, so I hope that marking the Q2 geometry won’t be too traumatic. Some complicated diagram dependencies render this hope in vain, but we finish up in time for a quick debrief before dinner. Meanwhile, the team have learned the hard way that Colombian plumbing does not hugely appreciate toilet paper…

Wednesday 17th July

I would normally struggle rather badly to find the motivation to go for a 7am run, but with a mile or so of relatively quiet beach on offer, it suddenly becomes a much more attractive proposition. As I return to the Santorini resort, the first waves of peddlers are arriving. One or two make a token attempt to sell me sunglasses, and a nice lady asks me how I got a particularly purple bruise, though I figure my Spanish is not sufficient to explain the idea of cricket right now.

Geoff bids us farewell and heads off to join the other team leaders at a top-secret location where they will begin the process of setting the paper. In theory it’s top-secret; in practice, it must be Barranquilla, the next city down the coast. The students power through another exam all morning, and pleasingly resist the temptation to make anything too complicated, so marking everything is relatively straightforward. Our stroll to dinner is accompanied by a small posse of feral dogs. I am reminded of the health guidance for this part of the world: “rabies is relatively low-risk, except for children, who are more likely to allow themselves to be licked in the face.”

Related articles

• Shakira in Ashes row (otherashes.wordpress.com)
• IMO team unveiled (cp4space.wordpress.com)

The Contour Process

As I explained in my previous post, I haven’t been reading around as much as I would generally like to recently. A few days in London staying with my parents and catching up with some friends has therefore been a good chance to get back into the habit of leafing through papers and Pitman’s book among other things.

This morning’s post should be a relatively short one. I’m going to define the contour process, a function of a (random or deterministic) tree, related to the exploration process which I have mentioned a few times previously. I will then use this to prove a simple but cute result equating in distribution the sizes of two different branching processes via a direct bijection.

The Contour Process

To start with, we have to have a root, and from that root we label the tree with a depth-first labelling. An example of this is given below. It is helpful at this stage to conceive this process as an explorer walking on the tree, and turning back on themselves only when there is no option to visit a vertex they haven’t already seen. So in the example tree shown, the depth-first exploration visits vertex V_2 exactly four times. Note that with this description, it is clear that the exploration traverses every edge exactly twice, and so the length of the sequence is 2n-1, where n is the number of vertices in the tree since obviously, we start and end at the root.

Another common interpretation of this depth-first exploration is to take some planar realisation of the tree. (Note trees are always planar – proof via induction after removing a leaf.) Then if you treat the tree as a hedge and starting at the root walk along, following the outer boundary with your right hand, this exactly recreates the process.

The height of a tree at a particular vertex is simply the graph distance between that vertex and the root. So when we move from one vertex to an adjacent vertex, the height must increase or decrease by 1.

The contour process is the sequence of heights seen along the depth-first exploration. It is therefore a sequence:

and such that .

Note that though the contour process uniquely determines the tree structure, the choice of depth-first labelling is a priori non-canonical. For example, in the display above, V_3 might have been explored before V_2. Normally this is resolved by taking the suitable vertex with the smallest label in the original tree to be next. It makes little difference to any analysis to choose the ordering of descendents of some vertex in a depth-first labelling randomly. Note that this explains why it is rather hard to recover Cayley’s theorem about the number of rooted trees on n vertices from this characterisation. Although the number of suitable contour functions is possible to calculate, we would require a complicated multiplicative correction for labelling if we wanted to recover the number of trees.

The only real observation about the uses of the contour process at this stage is that it is not in general a random walk with IID increments for a Galton-Watson branching process. This equivalence is what made the exploration process so useful. In particular, it made it straightforward, at least heuristically, to see why large trees might have a limit interpretation through Brownian excursions. If for example, the offspring distribution is bounded above, say by M, then the contour process certainly cannot be a random walk, as if we have visited a particular vertex exactly M+1 times, then it cannot have another descendent, and so we must return closer to the root at the next step.

I want to mention that in fact Aldous showed his results on scaling limits towards the Continuum Random Tree through the contour process rather than the exploration process. However, I don’t want to say any more about that right now.

A Neat Equivalence

What I do want to talk about is the following distribution on the positive integers. This comes up in Balazs Rath and Balint Toth’s work on forest-fires on the complete graph that I have been reading about recently. The role of this distribution is a conjectured equilibrium distribution for component size in a version of the Erdos-Renyi process where components are deleted (or ‘struck by lightning’) at a rate tuned so that giant components ‘just’ never emerge.

This distribution has the possibly useful property that it is the distribution of the total population size in a Galton-Watson process with Geom(1/2) offspring distribution. It is also the distribution of the total number of leaves in a critical binary branching process, where every vertex has either two descendents or zero descendents, each with probability 1/2. Note that both of these tree processes are critical, as the expected number of offspring is 1 in each case. This is a good start, as it suggests that the relevant equilibrium distribution should also have the power-law tail that is found in these critical branching processes. This would confirm that the forest-fire model exhibits self-organised criticality.

Anyway, as a sanity check, I tried to find a reason why, ignoring the forest-fires for now, these two distributions should be the same. One can argue using generating functions, but there is also the following nice bijective argument.

We focus first on the critical Geometric branching process. We examine its contour function. As explained above, the contour process is not in general a random walk with IID increments. However, for this particular case, it is. The geometric distribution should be viewed as the family of discrete memoryless distributions.

This is useful for the contour process. Note that if we are at vertex V for the (m+1)th time, that is we have already explored m of the edges out of V, then the probability that there is at least one further edge is 1/2, independently of the history of the exploration, as the offspring distribution is Geometric(1/2), which we can easily think of as adding edges one at a time based on independent fair coin tosses until we see a tail for example. The contour process for this random tree is therefore a simple symmetric random walk on Z. Note that this will hit -1 at some point, and the associated contour process is the RW up to the final time it hits 0 before hitting -1. We can check that this obeys the clear rule that with probability 1/2 the tree is a single vertex.

Now we consider the other model, the Galton-Watson process with critical binary branching mechanism. We should consider the exploration process. Recall that the increments in this process are given by the offspring distribution minus one. So this random sequence also behaves as a simple symmetric random walk on Z, again stopped when we hit -1.

To complete the bijective argument, we have to relate leaves in the binary process to vertices in the geometric one. A vertex is a leaf if it has no offspring, so the number of leaves is the number of times before the hitting time of -1 that the exploration process decreases by 1. (*)

Similarly for the contour process. Note that there is bijection between the set of vertices that aren’t the root and the set of edges. The contour process explores every edge exactly twice, once giving an increase of 1 and once giving a decrease of 1. So there is a bijection between the times that the contour process decreases by 1 and the non-root vertices. But the contour process was defined only up to the time we return to the root. This is fine if we know in advance how large the tree is, but we don’t know which return to the root is the final return to the root. So if we extend the random walk to the first time it hits -1, the portion up until the last increment is the contour process, and the final increment must be a decrease by 1, hence there is a bijection between the number of vertices in the Geom(1/2) G-W tree and the number of times that the contour process decreases by 1 before the hitting time of -1. Comparing with (*) gives the result.

Related articles

• Non-classical interacting random walks (cordis.europa.eu)
• Iterative Preorder Traversal of Binary Tree (codeatsociallywired.wordpress.com)