The Perron-Frobenius Theorem for Stochastic Matrices

Posted on November 8, 2012 by dominicyeo

This article was prompted by a question asked by one of my students about 5 minutes before the end of the final lecture of my Markov Chains course in Linyi. Although I didn’t have time to think about it right then, the flight home offered plenty of opportunity for having a play around. I am well aware that the proof given below is not the best one, but the ideas of minimising quadrants of a matrix seemed fairly natural. Anyway, it’s been sitting on my desktop for over two months now, so I decided I should put it up.

———

Recall that the transition probabilities of a finite Markov chain are determined by a stochastic matrix P. That is, each row of P is a probability distribution. In both theory and applications, the existence and properties of an invariant distribution is of interest. This is a probability distribution $\pi$ satisfying the relation:

$\pi P=\pi.$ (1)

It is clear that $\bigg(\begin{smallmatrix}1\\ \vdots\\1\end{smallmatrix}\bigg)$ is a right- or column eigenvector of P, with eigenvalue 1. Since the spectrum of $P^T$ is the same as that of P, we conclude that 1 is a left-eigenvalue of P also. So we can be assured of the existence of a vector $\pi$ satisfying (1). What is unclear is that this eigenvector $\pi$ should be a probability distribution. Since at least one entry must be non-zero, it will suffice to show that every entry of $\pi$ is non-negative.

A necessary condition for the uniqueness of an invariant distribution is that the Markov chain be irreducible. This is best defined using the terminology of random walks: the chain is irreducible if for every pair of states $i,j\in I$ , it is possible to move from i to j and back again. In terms of the transition matrix, P is irreducible if it is not block upper-triangular, up to reordering rows and columns.

We want to show that when P is irreducible, the (unique) 1-eigenvector is a probability distribution. The standard method proposed in this context is to exhibit the invariant distribution directly. For example, Norris’s Markov Chains defines

$\gamma_i^k=\text{ expected time spent in i between visits to k }=\mathbb{E}_k\sum_{n=0}^{T_k}1_{\{X_n=i\}},$

and shows that $(\gamma_i^k)_{i\in I}$ satisfies (1).

Nonetheless, the result required is clearly at least one step removed from the probabilistic interpretation, so it would be satisfying to find a direct proof of existence. Typically, one quotes the substantially more general theorem of Perron and Frobenius, the most relevant form of which is:

Theorem (Perron-Frobenius): Given A a non-negative and irreducible square matrix. Then there is a positive real eigenvalue $\lambda$ with multiplicity 1 and such that all other eigenvalues have absolute value less than or equal to $\lambda$ . Then the (unique up to scaling) left- and right-eigenvectors corresponding to $\lambda$ are positive.

Here we present a short proof of this result in the case where A is the (stochastic) transition matrix of a Markov chain.

Proposition: An irreducible stochastic matrix has a 1-eigenvector with all entries non-negative.

Proof: We show instead the contrapositive: that if a stochastic matrix has a 1-eigenvector with both negative and non-negative components, then it is reducible. The motivation is this third eigenvector given in example (2). Observe that the communicating classes are $\{1,2\}$ and $\{3\}$ , and it is not hard to see that for any eigenvector with negative and non-negative components, the sign of a component is a class property.

Informally, given an $n\times n$ stochastic matrix P, and a 1-eigenvector $\pi$ with this property, we relabel the states so that the non-negative components, which we call $A\subset I$ are first. That is, in a moderate abuse of notation:

$\pi=(\underbrace{\pi_A}_{\geq 0}\quad\underbrace{\pi_B}_{<0}).\quad\text{ If we write P as }\begin{pmatrix}P_{AA}&P_{AB}\\P_{BA}&P_{BB}\end{pmatrix},$

our aim is to show that the sub-matrices $P_{AB}$ and $P_{BA}$ are both zero. This implies that states in A and states in B do not communicate, showing that P is reducible. We can formulate this as a linear programming problem:

$\text{Maximise }\sum_{\substack{x\in A,y\in B\\x\in B, y\in A}}p_{xy}\text{ s.t. }\begin{cases}p_{xy}\geq 0&\forall x,y\in I\\p_{x1}+\ldots+p_{xn}=1&\forall x\in I\\\pi_1p_{1y}+\ldots+\pi_np_{ny}=\pi_y&\forall y\in I\end{cases}$

It suffices to show that this maximum is 0. Now, we take $|A|=i$ , and assume that $1\leq i\leq n-1$ , that is, there are a positive number of negative and non-negative components. Noting that the sum of the rows in a stochastic matrix is 1, we may consider instead:

$\text{Minimise }\sum_{\substack{x,y\in A\\x,y\in B}}p_{xy}\text{ s.t. }\begin{cases}p_{xy}\geq 0&\forall x,y\in I\\p_{x1}+\ldots+p_{xn}=1&\forall x\in I\\\pi_1p_{1y}+\ldots+\pi_np_{ny}=\pi_y&\forall y\in I\end{cases}$

and it will suffice to show that this minimum is n. To do this, we consider instead the dual:

$\text{Maximise }\lambda_1+\ldots+\lambda_n+\pi_1\mu_1+\ldots+\pi_n\mu_n,$

$\text{ s.t. }\lambda_x+\pi_y\mu_x\leq\begin{cases}1&\text{if }x,y\leq i\text{ or }x,y\geq i+1\& \text{otherwise}\end{cases}$

The objective is certainly bounded by n. And in fact this is attainable, for example by taking:

$\lambda_1=\ldots=\lambda_i=1,\quad \lambda_{i+1}=\ldots=\lambda_n=0$

$\mu_1=\ldots=\mu_i=0,\quad \mu_{i+1}=-\frac{1}{\pi_{i+1}}, \ldots,\mu_n=-\frac{1}{\pi_n}.$

Applying strong duality for linear programming problems completes the proof.

Understanding Linear Algebra Intuitively (stata.com)
Simulation II: Markov Chains, Monte Carlo, and Markov Chain Monte Carlo (Introduction to Statistical Computing) (bactra.org)
Markovian Excursions (eventuallyalmosteverywhere.wordpress.com)

Invariant Distributions of Markov Chains

Posted on September 12, 2012 by dominicyeo

My lecture course in Linyi was all about Markov chains, and we spent much of the final two sessions discussing the properties of invariant distributions. I was not surprised, however, that none of the class chose this topic as the subject for a presentation to give after the end of the teaching week. One of the main problems is that so many rather similar properties are introduced roughly simultaneously. As we did in the class, I thought it was worth making some sort of executive summary, as a mixture of revision and interest.

Definition: $\pi$ is an invariant measure if $\pi P=\pi$ . If in addition $\sum_{i\in I}\pi_i=1$ , then we say it is an invariant distribution. Of course, if I is finite, then any invariant measure can be normalised to give an invariant distribution.

The key initial questions are about existence and uniqueness. First, if there are multiple communicating classes, then an invariant measure (resp. distribution) is a linear (resp. affine) combination of the invariant measures / distributions on each (closed) class. So we restrict attention to irreducible Markov chains.

In the finite case, P is a stochastic matrix so has a column eigenvector with eigenvalue 1, namely the vector with all entries equal to 1. Thus, by reference to general theory in linear algebra, P has a row eigenvector $\pi$ with eigenvalue 1. To paraphrase a remark made by one of my students, what is not clear is that this should be a measure. Demonstrating that this is true is rather non-trivial I think, normally done by reference to the rather more general Perron-Frobenius theorem, though on the flight home I came up with a short argument using Lagrangian duality. For now, we accept existence in the finite case, and note that we typically show existence by showing that the vector of expected time spent in each state between successive visits to a fixed reference state satisfies the properties of an invariant measure.

This is a good moment to note that recurrence is not a necessary condition for the existence of an invariant measure. For example, the random walk on $\mathbb{Z}^3$ is transient, but the uniform measure is invariant. However, it is not a sufficient condition for the existence of an invariant distribution either. (Of course, an irreducible finite chain is always recurrent, and always has an invariant distribution, so now we are considering only the infinite state space case.) The random walk on $\mathbb{Z}^2$ is recurrent, but the invariant measure is not normalisable.

The property we in fact need is positive recurrence. This says that the expected return time to each point is finite. Again, this is a class property. This is a common requirement in probabilistic arguments: almost surely finite is often not strong enough to show results if the expectation is infinite (see for example the various requirements for the optional stopping theorem). If this holds, then $\pi_i=\frac{1}{\mathbb{E}T_i}$ , where $T_i$ is the the return time starting from some $i\in I$ .

The final question is ‘Why are we interested?’ One of the best answers is to look at convergence properties. A simple suggestion is this: if we start in equilibrium, then $X_0,X_1,X_2,\ldots$ are all equal in distribution. Note that the dependence structure remains complicated, and much much more interesting than the individual distributions. Next, we observe that a calculation of n-step transition probabilities for a finite chain will typically involve a linear combination of nth powers of eigenvalues. One of the eigenvalues is 1, and the others lie strictly between -1 and 1. We observe in examples that the constant coefficient in $p_{ij}^{(n)}$ is generally a function of j alone, and so $p_{ij}^{(n)}\rightarrow\lambda_j$ , some distribution on I. By considering $P^{n+1}=P\cdot P^n$ , it is easy to see that if this converges, $(\lambda_j)_{j\in I}$ is an invariant distribution. The classic examples which do not work are

$P=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ and $P=\begin{pmatrix}0&1&0\\ 0&0&1\\1&0&0\end{pmatrix}$ ,

as then the distribution of $X_n$ is a function of the remainder of n modulo 3 alone. With a little thought, we can give a precise classification of such chains which force you to be in particular proper subsets of the state space at regular times n. Chains without this property are called aperiodic, and we can show that distributions for such chains converge to the equilibrium distribution as $n\rightarrow\infty$ .

The Markovian Mind (isnerd.wordpress.com)
Chain Reaction (thebigquestions.com)
Generating Gibberish in Python – Markov Chains (terse-words.blogspot.com)

Teaching Probability in China

Posted on September 4, 2012 by dominicyeo

As I’ve mentioned in passing in a few recent posts, which have tended to focus on Markov chains more than might perhaps be expected, I’ve just finished a two-week trip teaching at Linyi University in Shandong province, about 600km south of Beijing. I’ve been describing some of my touristic and social observations of China on my personal blog, but it has been mainly a mathematical adventure, so I thought I would describe some of the main cultural differences in the approach to science here. I was surprised to find these a far larger obstacle than the more obvious language barrier in the classroom.

1) I think many of us were surprised by how different the gender divide was at Linyi to what we are accustomed to in Cambridge. Although of course it varies from year to year, from course to course, and in select cases from lecturer to lecturer, in general there is a significant male majority in lecture halls. In China, amongst my students (who had just finished their third year), the ratio seemed to have been reversed and then further extremised. I had about twelve students in attendance during the middle of the course, and only one was a boy.

2) Perhaps the most clear reason for this reversal of the Western trend became apparent when I asked some of my group what they were planning to do after leaving university. As most of them have just a year left, they all seemed to have a fairly concrete idea of what their plans were, and the answers were perhaps unexpected. One of the most able girls said she wanted to continue with postgraduate mathematics, but all of the rest wanted to become teachers. And not just high school either. In fact, all bar two or three planned to teach middle or even elementary school. I don’t want to get burned by talking about things I don’t much understand, but I understand this is very different to the UK. Here, I do not believe many maths graduates from top universities (in a national context) have ambitions in primary education. I do not know which way round the causality works. Are they encouraged towards a pure science degree as a route into schools, or are teaching jobs viewed the natural job to follow a hard quantitative course? In either case, it sounds like an excellent situation to be in from the point of mathematical education.

3) The role of the lecturer in China evidently carries a great deal more gravitas than comparable positions in England. Clearly his task is to stand at the board and write down the notes, which the audiences copies politely. So far, so like Cambridge Part III. But then it seems that the notion of interacting with the class doesn’t really apply here. Even an utterly uncontentious question such as ‘what is your name, and which year are you in?’ produced a flurry of nervousness, and then each student stood up stiffly in turn to answer. This continued even as the class size reduced, and my manner became more informal, for example starting to explain ideas while perching on a desk in the front row. I guess old habits die hard. It’s a bit of a shame because I feel the purpose of a lecture is not just to transcribe course material, but also to give motivation and a flavour of the mathematical landscape, as well as to inject some enthusiasm into an appreciation of the topic. And it’s very hard to start such ideas in a culture where it is totally unexpected.

4) This was even more evident in some of the research talks. Each member of the Cambridge group and various Linyi staff, postgraduates and masters students gave a talk outlining some aspect of their research interest. The motivation had been to try and recreate a seminar series, at least in environment if not in totality given the expansive range of areas of study represented. I was struck by the fact that what seemed like the entire maths undergraduate community had been forced to attend, but many of the talks were completely inaccessible to a non-specialist audience. A paper on a technical property of spectral theory read out at speaking pace from a powerpoint is not going to get younger students excited about research maths.

5) As suggested by their enthusiasm for PDEs and complicated graph theory construction problems in the research talks, the students seemed to relish calculation over theory. I found it very difficult to get across the idea that it was sometimes better to use the reuslt we had just shown rather than immediately attempting to diagonalise all visible matrices. I think some of the undergraduate teaching mirrors sections of Maths A level in this country, where the emphasis is on deploying solution techniques rather than ideas. For example, the class looked absolutely lost when I tried to use recurrence relations, to the extent that I decided just to start my explanation from the basics. It turned out that I had notated the general solution as $h_i=\alpha \lambda^i+\beta \mu^i$ whereas their teacher had used $h_i=\alpha \lambda^{i-1}+\beta \mu^{i-1}$ , and this had caused the major confusion. The problem is compounded by the fact that despite constant encouragement, they feel mortified at the thought of asking a question or seeking a clarification. Again, it seems to be a matter of respect, but of course this spirit can remain in a more enquiring environment.

Overall, it was a very interesting insight into a completely alien mathematical culture. I know which one I prefer, but I think my perspective is richer for having experienced something of mathematics in China. And hopefully any teaching I do in the near future will seem straightforward by comparison, if only for the property of sharing a language with the students…!

Cambridge Linyi Summer School 2012 – Part Six – Jinan and Home

Posted on August 25, 2012 by dominicyeo

Thursday 23rd August

Whatever conspiracy theories were proposed yesterday were proved unfounded, as today we do indeed go to the mountain. First, however, are the student presentations. I am paired with Jonas, so my students present first to his group, then the reverse. I am extremely pleased with the Markov Chains presentations – it is clear that the speakers have not only understood much of the course than I’d suspected, but have put a great deal of thought and time into preparing a talk that would be well-selected, interesting and intelligible. Given what a disaster would result if I had to give a talk on probability in a foreign language, we were all very impressed with the standard of English shown in all the talks as well. I think everyone is agreed that this was an excellent high point on which to end our trip to Linyi.

Anyway, finally we are off to the Meng Shan mountain. The first stop is a family-run restaurant at the roadside on the edge of the forest park. While we drink tea on stools, we see a chicken being fetched from the outside coop by a Chinese lady with a cleaver and a determined glint in her eye. Sadly, our meal is meat-free, though some of the seasoning and spices go a long way to disproving the assertion that all vegetarian food is bland. The toilet is out back in an ominous brick hut in the middle of the apple orchard. To describe it as a ****hole would be inaccurate. There was no hole. Chris has evidently chosen a bad day for his experience of what our illustrious leader in absentia Marj Batchelor euphemistically defined as V&D. I view this as divine retribution for his shameless attempts to peer pressure me into the club last night.

The mountain itself is a maze of paths through forests, rocks and waterfalls. We are relatively pleased with the cardiovascular exertions of the journey to the main waterfall, until Georgios, who has forsaken the climb for a cable car tour, informs us we saw merely a quarter of the resort. Highlights include the questionable English on pretty much every visible sign, attempting to identify the silhouette of a sleeping Buddha apparently formed by a valley (topology in action?) and the tourist’s t-shirt declaring ‘Love Oneself. Slow. Vicious.’ Glibness aside, the view from the summit was astonishing, and rounded off an excellent visit.

Friday 24th August

Our final morning in Linyi is a ceremonial one. First we each receive a scroll, featuring a quotation by Linyi’s most famous philosopher, as notated by Linyi’s most famous calligrapher. Then we trek across campus for the obligatory photograph next to the stone commemorating the first edition of this summer school, adorned with sage words from Confucius and Dr Marj Batchelor. All that remains is to pack and brace oneself for the four hour drive across Shandong province to the capital, Jinan. Some of the students (who have come from universities in Jinan) are travelling with us. Evidently they had limited faith in the Linyi University accommodation, as we are sharing the bus with twenty duvets…

This is probably an excellent moment to thank the staff at Linyi, in particular Dr Lu, for everything they’ve done to organise and run this summer school. Everyone has been entirely helpful and welcoming, and we’ve all enjoyed our stay a great deal. Also Yuan, my teaching assistant, for her assistance with everything from translating probabilistic notation to advice on ice cream flavours!

I spend some of the journey thinking about whether you can think of measures and metrics as the same thing. I decide that you can’t. More accurately, I decide that I can’t. We are being housed in an impressive hotel on the campus at Shandong Polytechnic. A reunion with hot showers is most welcome. Dinner with our host professors is an astonishing spread. After everyone receives an amuse-bouche of a lightly sauteed sea cucumber, a dazzling array of local dishes arrive. The highlights are oysters, a ferociously spicy brain soup and a trio of donkey meats. We are strongly encouraged to try everything, and though it is a pleasure I am enormously full afterwards, and slightly nervous about maintaining my digestive composure during a 9am research talk tomorrow.

Saturday 25th August

If two attempts at delivering ‘Coalescence: various modern perspectives’ have taught me anything, it’s that I really need to improve my title selection skills. The schedule runs fairly late today, so the four speakers are asked at the last minute to cut the talks to 20 minutes, including time for questions and non-simultaneous translation, which proves a challenge too far. I overrun slightly so as to make sure I have actually got somewhere in terms of content. Many of the audience leave directly after my talk. I can only assume there is an unmissable commitment elsewhere in Jinan at 10.25 rather than any reflection on the quality…

After lunch, we are taken on a tour of Jinan, with stops at the two most famous sites, the Baotu Spring park, and the Daming Lake. As with some of the sights in Beijing, these are very much places of simple beauty and quiet reflection, and so are rather spoilt by the presence of crowds of tourists. A group of locals poke a floating log with umbrellas in an attempt to persuade a shy turtle to emerge from underneath. I can understand its reluctance. Nonetheless, the more peaceful areas were delightful. There is mild panic when we hear by email that the group departing on the late afternoon train are facing five hour delays. Ruadhai, Richard and I are starting to have misgivings about choosing an overnight train to Beijing for the ’experience’. In preparation, I am cautious in observing calls of gan bei, and avoid all dishes with visible chillis. The lack of any signs at Jinan railway station using the Western alphabet is a bit concerning, especially as our train, the illustrious K47, has a different display to all the other departures. After some pained gesticulation we ascertain that it is running half an hour late, so enjoy the additional time with the packs of people sleeping on the concourse. Eventually, just after midnight, the sleeper from Qingdao pulls in, so we join the human tide down to the platform, to see exactly what awaits us in coach 6…

Sunday 26th August

Well that cliffhanger was entirely justified. It turns out that hard seats rather than beds of some kind have been booked for us. Whether this was out of necessity or to enhance the sense of ‘experience’ I do not know. That said, we still feel like emperors in comparison to the scores of travellers who have standing tickets only. I had been worried that my suitcase might be anti-socially unwieldy, but it was as nothing compared to the guy who was travelling with only a 100kg sack of rice for company. Eventually, with everyone safely on board, and luggage stored in a variety of increasingly improvised locations, we steam off into the night. There is initial confusion when it turns out we have arrived at a different station in Beijing to what we had been expecting, but all is forgotten as we find a McDonalds and so by extension, coffee. Richard is suffering somewhat, but Ruadhai and I managed to get a reasonable amount of sleep, so decide to head across town to the airport. After check-in, I come across Ben – or at least, I think it’s Ben, but then all these Westerners look the same… – so we fill the time by talking about stochastic analysis and trying to spend our last handful of Yuan. The flight home is long and uneventful. The modern art instalment next to Gate 37 at Helsinki airport provides brief distraction, but finally back to London. An excellent trip is at an end!

Cambridge Linyi Summer School 2012 – Part Five – Finishing in Linyi

Posted on August 22, 2012 by dominicyeo

Sunday 19th August

Today’s lectures show greater promise, though we have stalled at around the 15 page mark of James Norris’s canonical textbook. I think a change of direction may be called for on Monday, just to avoid getting bogged down in the same calculations every time. The main excitement today was the burst water pipe caused by yesterday evening’s extraordinary thunderstorm. Annoyingly, I didn’t realise this until after I had loaded my laundry into one of the alfresco washing machines, so won’t have any usable clothes until tomorrow at the earliest. Still, worse things happen at sea. I was surprised to realise that I have now been in China for over two weeks. My only real hardship at this point is the limited choice of carbohydrates. Ruadhai agrees – this the probably the longest time an Irishman has gone without a potato since the Famine.

Monday 20th August

The water has returned to an extent. The shower provides only hot, and the washing machine only cold, but now both me and my clothes are clean so my happiness knows no bounds. We cover invariant distributions in the fifth lecture. I am confused why the students choose to ask only today what ‘distribution’ means when it has featured several times in every session so far. Nonetheless, by talking about convergence to equilibrium, I am glad we are approaching a natural finishing point for the course, as there’s nothing worse than a story with a weak ending. Over dinner there are toasts of varying degrees of seriousness with the dean as Siu is leaving tomorrow. The beer of choice is unsubtly called ‘WHEAT’. Afterwards, Karolina does an excellent job of teaching some basic Latin dance steps to an unexpectedly large gathering of the Cambridge group and some students. The plan for teacher-student bonding over the cha cha cha is a huge success. My many left feet are in high demand, but not quite as much as Jonas’s – I think tall blond Germans are something of a rarity in these parts.

Tuesday 21st August

I decide against including too many examples in today’s lecture and instead race through some material so that I can finish early and leave my students some time to prepare for the presentations which they will give on Thursday. The teaching component of this trip has been a challenge. My main difficulty was that I found it very hard to gauge whether the students were understanding what I was doing. In other situations, you can sense what any problems might be from the audience’s real-time reaction, but in China it is clearly a show of disrespect to make any such demonstration. On the other hand, some of the questions they finally realised it was acceptable to ask towards the end of the course, for example about the eigendecomposition of stochastic matrices, showed that the enterprise might have had some positive effect. And in my final lecture, I managed to get through two hours without breaking either a stick of chalk or the blackboard pulley mechanism for the first time… To celebrate the end of the courses, the group is heading out to a karoake bar in town, but my voice and my brain are tired, and I’m mindful of needing to be in full tenor in a few days, so I refrain. Well that’s the excuse I give: mainly I just despise karoake.

Wednesday 22nd August

Another rest day. For a second time, our planned day trip to the Meng Shan mountain and national park is cancelled because of concerns over the potentially dangerous weather, despite both the forecasts and the actuality showing sun and moderate temperatures all day. I feel rather like the little boy in To the Lighthouse, doomed forever to wonder what might have been. Perhaps reflecting the lack of much to do other than foment, various extravagant conspiracy theories are proposed. Instead we play a great deal more table tennis, and I meet my students briefly to help them prepare their presentations. Disappointingly, it seems several have already gone home, but I am confident those who remain will do a good job tomorrow. After dinner, we find a bar beside the Yi river which seems to be the focal point for the few foreigners who live here. Two Americans, Dwayne and Tom, regale us with stories of a year teaching English privately to the city’s swelling middle class. Most of them seem to revolve around implementations of their patented three-step local seduction technique. Apparently white skin and knowing how to say ‘Hello you sexy bitch’, ‘I have food for two at my apartment’ and ‘I don’t understand’ (in response to any attempt at further conversation) in Mandarin, is enough for a sizeable number of the maidens of Linyi. In case you were wondering, they found their current employment advertised on Craigslist. We also meet a young lady who makes a florid but vaguely plausible claim to be the daughter of a local mafia boss then immediately invites us all to a private room she has booked in a nearby club. Despite extreme attempts at coersion, I feel I have already exceeded my surreality limits for the day.

Cambridge Linyi Summer School 2012 – Part Four – Teaching in Linyi

Posted on August 18, 2012 by dominicyeo

Tuesday 14th August

When it rains in this part of the world, you certainly know about it. The skies turned black during breakfast and I was left feeling grateful for my trusty UKMT- issue umbrella. By the end of the day, however, there was no sign of any respite, and the way onto the campus resembled a river more than a road. We were invited to lunch with the Vice-President of the university at a nearby hotel. This proves a truly surreal experience. The selection of dishes is far more eclectic than anything we’ve seen so far. The fried cicadas were surprisingly nice. The sauce made all the difference. The slabs of tofu were less of a success, being more reminiscent of scouring pads than anything edible. The quantities were astonishing. Just when we thought we were making progress, we were each brought a pork tenderloin, served with a single segment of orange. A sequence of toasts was made: for each one the call of ‘gan bei’ demanded that we down our beers. Fortunately the glasses were small, but plans to write lectures and examples sheets in the afternoon had to be rearranged hastily! The Vice-President was very keen for everyone to say something in Chinese, especially the girls present, with mixed success. The few hours spent watching ‘Growing up with Chinese’ finally earned some reward. Tomorrow the raison d’etre of the trip begins, with the first lectures of our courses. I think everyone feels reasonably prepared, but also aware that we have no real idea what we should expect.

Wednesday 15th August

In the end, my first lecture went rather better than I could have expected. I had sat in on Robin’s first session in the morning, on basic statistical theory, and was surprised to chat to the students near the back and learn that some of them were not even science students. I guess their timid responses to relatively straightforward questions were understandable for English majors. My group, however, were all Linyi mathematics students and they seemed to have an excellent grasp of basic probability, so we made reasonably fast progress through the prerequisites, despite the language barrier, and so we should be ready to start the course (mine is on Markov chains) proper tomorrow. In many ways, this summer school is not so much about imparting knowledge of particular new subjects. Rather the focus is instead on promoting a Cambridge style of learning mathematics in Linyi, where the majority of learning seems to be via rote. To that end, today was actually a great success. I think choosing slightly easier material for the first lecture made the students feel more comfortable about answering questions in class and going up to the board to attempt various problems. Hopefully this promising trend will continue through the next five days! Meanwhile, as ever after teaching sessions, I cannot believe how tired I feel. Will be having an early night as soon as I have chosen some problems for tomorrow’s examples sheet.

Thursday 16th August

In the morning I give an examples class, in which we go through some exercises consolidating the material introduced yesterday, and then start another two hours of lectures after lunch. I am confused as to why the audience members are rather different to yesterday, but it seems that flexibility is the order of the day. Anyway, we made it through some of the elementary theory of memoryless random variables and Markov chains, with a view to starting work on ‘real’ examples tomorrow.

In other news, my table tennis skills have improved to the point where I was able to beat one of my students. My chopstick technique has enjoyed a similar transformation. The question of why a proud and technologically advanced nation continues to insist that a pair of glorified needles constitutes the best way to manipulate food is a mystery, but if these are the only route to fullness, you’ve rather got to man up and master them. Rice, fried eggs and chickpeas have provided excellent practice to raise one’s ability to the level required for the twice-daily dessert, banana, pear and tomato fruit salad. Meanwhile, our enthusiasm to spend our Yuan has devastated the campus shop’s supply of ice-creams.

Friday 17th August

My afternoon lecture was rather frustrating. We were talking about n-step transition probabilities, and had worked through the case of the general Markov chain with two states. All subsequent problems could be reduced to this, but it was an impossible task to persuade the students to use the general result which had taken us twenty minutes to develop and which was still sitting on the blackboard, rather than diving into another specific eigenvalue search. The problem is surely cultural. Here, great value is placed on being able to perform difficult computations competently, and this lessens the impact of theory which removes the need for repeated calculation. I’m unsure how to resolve the problem, except by continuing to give examples which are increasingly unyielding to ‘brute force’ methods. Tomorrow is a rest day, so there are plans afoot to examine the nightlife in the city centre with some other foreign residents in our building. I am exhausted by the combination of unrelenting heat and mathematics, so opt instead to join the group watching Groundhog Day in the kitchen. Although my feeling of ennui has declined sharply since the teaching began, aspects of the film feel dangerously similar to two weeks of maths at Linyi University.

Saturday 18th August

We have a day off to mark the halfway point of the teaching week. There is some consternation to learn that the main door to our accommodation, which also serves as the fire exit, is closed with a bike lock overnight. Conversely, our hosts have learned about last night’s club trip, and are apparently ‘very concerned’ for our safety. Hopefully some form of entente will be reached very soon. After lunch a group heads into the city once again, for a taste of ‘real’ life in China. Standards of public hygiene are, well, different. Everyone spits everywhere, and on the bus a mother holds out her little girl to pee all over the floor. Georgios is horrified – such indelicacy would be inconceivable in Athens. Our first stop is an enormous bookshop. Sections are devoted to, amongst others, poultry, adhesive science, and mushroom cultivation. Sadly mathematics does not feature. Jonas is amused to see an aisle devoted to Bildungsroman. This turns out to feature a collection of children’s adventures, all of whose characters appear to be Aryan. I retire to the piano music section. It is clear why the stereotype of prodigious young Chinese pianists exists. The majority of the available repertoire is etudes. That is an unhealthy quantity of Czerny and Burgmuller. I find some Debussy, Schoenberg and the complete Prokofiev sonatas in reasonable editions for a ridiculously low price. The joys of capitalist consumerism

Cambridge Linyi Summer School 2012 – Part Three – Talks in Linyi

Posted on August 13, 2012 by dominicyeo

Friday 10th August

On the Word document controlling the schedule of the summer school, today’s itinerary takes up more room than the rest of the fortnight combined. First up is the official opening ceremony. In the university’s main hall are sixteen armchairs with sixteen steaming pots of green tea set for our group, while the chancellor and the dean make the usual welcoming speeches, before a stream of photographs. After lunch, we are treated to a tour of the campus, and in particular the museum recording the history of the university. The exhibits detailing visits of influential local figures to the building site had an impact that was perhaps slightly lost in translation, but everyone enjoyed the large-scale model of the campus, partly because of its intricacy but also for its assistance in navigating the confusingly sprawling 6km wide site.

An opening banquet is scheduled for the evening, and indeed we turn up at the dining room to find an impressive spread on the lazy Susan. Soups, squids and a whole roasted carp are just the start as the dishes keep on arriving faster than we can possibly make possibly attend to them. We later find out that because the university party chairman could not make the date, this was not in fact the ceremonial dinner. We are intrigued to find out how the banquet could conceivably surpass this?

Saturday 11th August

The mathematical programme begins. For three days there is a series of seminars given by the Cambridge contigent and staff and students from Linyi, all in English. The quality is naturally quite mixed, but I doubt my mathematics would be up to much if I had to deliver a talk in Chinese! There is some confusion about pre-requisite knowledge: Georgios’ talk on ‘Post-Grothendieck Categorical Galois Theory’ gets off to a shaky start when the local students make it clear that they know neither what a category nor a Galois group is. Even the notion of a group causes some murmurings, so he decides to start from the very beginning instead. I don’t mind in the least: now I know the definition of a category! As lunch and dinner come round again, it becomes clear that last night’s feast was no rarity. The campus shop’s selection of red bean paste flavoured ice cream is also a new candidate for my favourite thing ever. My worries about eating well are no longer. For the princely sum of 6 Yuan (about 60p), we find a bottle of the local spirit from the campus supermarket. It smells like over-fermented Malibu but has a surprisingly complicated palate. The initial sensation of peaches gives way to something more woody and finally a heady aftertaste of anti-freeze.

Sunday 12th August

Another full day of seminars. The maths department at Linyi seems to specialise in graph theory, so I get to remind myself of the world of hyper-edges and vertex colouring problems. The highlight of the day is a trip into town. Well, I say town, but in fact Linyi is a city of 10 million people, according to Wikipedia. In spite of that, there doesn’t seem to be a whole lot to do in the centre of town, at least by the standards of Western cities. We have a look at the People’s Square then find a rapid restaurant, where a plate of noodles is a nice change from the rice that is the staple at the university. Afterwards, there are plans to find a bar, but Linyi seems to be somewhat lacking. Instead we check out a supermarket, where the few who remain outside are a major tourist attraction, and the rest of us examine the spirits aisle, where the local brew comes in varieties ranging from 6 to 17,000 Yuan. Unsurprisingly, the student mentality remains and we aim for the lower end of that range. An interesting evening, but with two weeks here remaining, it is slightly worrying that we might already have seen the best of Linyi.

Monday 13th August

I give my research seminar this morning. I choose to talk about coalescence, in particular the multiplicative kernel, essentially describing the skeleton of my Part III essay. It seemed reasonably suitable as it was possible to talk about several ideas and methodologies without actually working through any of the analysis involved in full. It also seemed an excellent opportunity to practise giving a talk on very little preparation. After all, apart from about five Cambridge people, no-one in the audience spoke much English… It was clear from the platform that many of the local undergraduates were engaged in other activities, and most of the remainder just smiled and nodded irrespective of the content. Nonetheless a worthwhile experience. Later, we were able to get into the university’s sports centre. On the ground floor we were greeted by the sight of thirty yellow-shirted ten year olds practising table tennis backhands in regimented unison with astonishing efficiency. The rooms upstairs were a bit less congested, and it was excellent to work off some energy in a way that maths can never quite achieve. And I suspect that by the time we leave, we may all be quite a lot better at badminton!

Cambridge Linyi Summer School 2012 – Part Two – Beijing continued

Posted on August 9, 2012 by dominicyeo

Tuesday 7th August

An early start to beat the Beijing rush hour. I’ve booked myself onto a bus tour of the area north of the city, including a visit to the famous Great Wall. First though, we stop at the Ming dynasty tomb at Dingling. Inside the burial chambers, which are dug deep into a wooded mountainside, the tombs themselves are somewhat less impressive than the stone thrones for the emperor and empresses. It turns out that the entire excavation was ransacked by Red Guards during the Cultural Revolution. The relics from the site were left to spoil, and the skeletons of the emperor and empress were removed and burned. Since then, plans to excavate other, grander tombs have been put on hold.

Then on to Mutianyu, a strategically-located mountain pass 70km north of Beijing. There we eat lunch at a rather touristy restaurant boasting the full range of lazy Susans and sweet and sour pork intestines. I get a chance to meet the rest of the group properly: Roger, Alfredo and Africa from Barcelona and Franz and Barbara, a couple from Basel who have spent the past four weeks in outer Mongolia, and have a fortnight left in China! I ask whether this is a once-in-a-lifetime trip and they look shocked – apparently they do this sort of thing every year.

Anyway, afterwards we board the cable car through the forest canopy and up to the wall. Approaching from below, it is a truly impressive spectacle, stretching for further than the eye can see along the skyline. Any Mongol hordes approaching from the north wouldn’t have stood a chance. The humidity is stifling and even the flatter sections feel like a fair hike. The climb up to the Chinese flag at the end of the main restored section proves a struggle for many, and the hawkers who have somehow raised a fridge up there are getting good business from selling water at 30 Yuan a bottle. The physical reality of the Great Wall is breath-taking, but even more so is the thought of the power of spirit than surrounded its construction. Over hundreds of years, for hundreds of miles and in the most inhospitable of locations, walls like this were built, restored and maintained, all by hand, and they endure to this day. Truly awe-inspiring.

Wednesday 8th August

The temperature hits a high of 35 degrees around lunchtime today, so I decide a slightly quieter day is called for. I head for the picturesque Beihai Park behind the Forbidden City, where a white pagoda rises mole-like from the Jade Island in the middle of the central lake. The water is full of Beijingers on pedalos. I feel equally energetic by the time I get to the top of the island – the marvellous view over the lakes and the sprawling hutong is reward enough for the sweat pouring from my forehead. A group of four Chinese twenty-somethings ask me to join them in posing for a photograph, seemingly in each of the 32 possible configurations, but I am in distinctly no rush, and enjoy the chance to practise my Chinese. I feel it is embarassing that the hotel’s talking mynah bird knows more phrases than I do, but it is improving. Mindful of meeting the Cambridge group tomorrow to travel south to Linyi, I spend the hottest hours of the day resting and doing some preparation work for my lecture course. The Guizhou restaurant I chosen for my final dinner in Beijing turned out to have been closed, so I trusted pot luck, and found a place specialising in the cuisine of Xinjiang in the far northwest. Unexpectedly, the meal is accompanied by intermittent belly-dancers and a optimistically enthusiastic guitarist. The food is somewhat less louche, the house special dapanji is a spicy chicken casserole. It is always easy to exaggerate such things, but my ‘small portion’ genuinely would have fed a party of four and left room to spare. I barely make it past the rim of the bowl before declaring defeat and trudging back heavily laden through Dongzhimen.

Thursday 9th August

I squeeze in a quick trip to the Olympic Park before leaving Beijing. For the first time since arriving it is a brilliantly sunny morning, which is somewhat unfortunate since the park is an entirely exposed concrete esplanade. The Bird’s Nest stadium is very striking though, as you wander through the beams which are somehow both disarranged and artful. Opposite, beside the Water Cube, is the food tent – dumplings and noodles as far as the eye can see! I go for steamed pork versions, before a bizarre dessert that describes itself as fried ice cream.

Then it’s time to join the gang at Beijing Nanzhan. The plan to meet is slightly fraught as the station is absolutely enormous (comparable to the Forbidden City on the overhead map) and is the home to six KFC’s, the agreed rendezvous point. Eventually everyone makes it in time for the high speed train south. It’s refreshing to catch up with the familiar faces at 300 km/h. There are 18 of us, so a bus seating 15 is sent to pick us up from the nearest station for the two hour run into Linyi. Only the driver gets a seatbelt. I’m just glad to get a seat. Not that many places are open in Linyi at 9.30, so we end up with our guides at a corner diner in the centre of town. There is confusion about whether the bowl of warm soy milk that everyone receives is a starter, a soup or a dessert. Matters improve with an onion omelette and further dumplings. The accommodation at the university is exciting. My roommate David and I are surprised to find a water-cooler and a widescreen television, yet there are no cupboards, or any other furnishings. The previous occupants have left us a small gift: a string bag of garlic shoved down the back of the TV stand. We spend a slightly futile twenty minutes attempting to swat mosquitos before turning in.

Cambridge Linyi Summer School 2012 – Part One – Travel and Beijing

Posted on August 6, 2012 by dominicyeo

Saturday 4th August

Painfully early start to Heathrow for the start of this Far Eastern mathematical adventure. In the cause of economy, I’m flying on Finnair with a six hour stop in Helsinki. At this point I should mention how grateful we all are for the generous donation from an anonymous Hong Kong businessman which means this part of the trip has been covered. It turns out to be entirely possible to slip into the town centre for a few hours, rather than stay confined in the clean but rather sterile Finnish airport. The weather is beautiful, with not a cloud in the sky as I stop for freshly grilled salmon on the harbourside then wander round the stylish waterfront shops, the two cathedrals and a sprawling park with a stunning greenhouse complex at its centre. The now scorching conditions do nothing to deter the legions of stallholders attempting to shift arctic fox stoles and reindeer fur throws. I return on the regular airport shuttle bus and head for the gate, albeit two hours early, but unbelievably there is an almost infinite supply of flat sofa-chairs, so I can settle down with Fifty Shades of Grey inconspicuously stored on my Kindle. In many ways, Finland has been an excellent, if brief, preparation for China. Firstly, the language is completely unintelligible. Secondly, I stand out like a black sheep amongst the perfect Nordic specimens, at least until the rest of the passengers turn up for my Asian flight. On the other hand, the price of everything here is absurd. Nothing plausible for lunch comes to less than 10 Euros. I’m informed that might well supply several three-course dinners in Beijing… In any case though, my stay here is short, and I’m on the evening flight East.

Sunday 5th August

I get some sleep leaning against the bulkhead, but am still disastrously tired as I yawn my way through border control at 6am Beijing time. I can’t quite face rush hour right now, so have a snooze in the arrivals lounge before making my way across town. I realise I am being royally ripped off by a taxi driver, who refuses to turn on the meter, but I fail to be demanding enough at the appropriate moment. I think he realises that I realise, and looks suitably sheepish, so I only pay a quarter and he seems happy enough. My room contains a bed, which right now is all I want. After a nap, I catch up on some of the Olympics on Chinese TV while I sort my life out. Evidently I missed the British Gold rush, but unfortunately since none of the remarkable medal haul lay in table tennis or badminton, it’s hard to find any relevant highlights. Later, I head out for a stroll through North-East Beijing. It doesn’t take too long to get used to the humidity and the traffic. I’d been apprehensive about the logistics of crossing the road, when right turns are allowed at all times, but as in Vietnam, it seems that if you just keep going at constant velocity the mopeds will swerve around you. I end up at Gui Jie, the ‘Ghost Street’, and location of hundreds of neon-lit, red-lanterned restaurants facades. Amid the imprenetable character displays, I pick one at random. My phrasebook Chinese and frantic gesticulation on both sides is enough to produce a beer and a serving of the Sichuan speciality, Gongbao chicken, with a worrying mountain of chillis and peppercorns piled in a corner. I proceed with caution.

Monday 6th August

Breakfast is a further adventure. I’ve been a massive fan of the jiaozi dumplings at Dojo in Cambridge for ages, and something similar appears here – a bit odd at 8am. Truly odd, however, are the thousand-year eggs, which are pickled raw in mud (thankfully for only two weeks or so) until the yolk turns a dark green-black and the whole thing carries an aroma of the stable. I’m sure they are an acquired taste. I have not acquired this taste yet. On the other hand, the selection of exotic fruit is excellent, and I always approve of plenty of fish in the morning.

Thus fortified, I descend into the efficient underground realm of the Beijing metro to make my way to Tiananmen Square. It is grey but enormous. Even with thousands of visitors you still feel isolated. I wander round Mao’s Mausoleum, but the queue deters me from paying my respects up close. Instead, across the small moat, and under his famous portrait which gazes down on visitors entering the South Gate of the Forbidden City. The crowd meanders through the collection of gates, hall and palaces that make up the residence of the two dynasties worth of emperors and their extensive entourages. Everywhere there is red and blue, and the copper of the elegant roofs. Some of the most interesting sights are to be found in the less grand arcades and more intimate quarters ranging around the gardens at the back of the complex. In many ways the life of the Emperor doesn’t sound all that fun. From as young as three years old, they had a daily schedule of rituals, sacrifices and administrative meetings, with only the court officials and the intriguing eunuchs who guarded the concubines for company. The best bit in a way was the view from the top of the Coal Hill Park opposite, looking down through the lingering mist (or possibly smog…) at the intricate layers that made up the fascinating enclosed city.

One of the more surprising aspects of today’s sightseeing was how few international tourists there are here. The overwhelming majority of the enthusiastic camera-pointers were Chinese. It felt nice, and a pleasant novelty after the likes of Rome and Istanbul to be with the locals even during the most stereotypical of tourist activities. Dinner tonight was much more of a success. On a terrace by the Houhai lake, a picture menu made life much easier, and I enjoyed my whole roasted duck Sichuan-style, even after the disconcerting moment where I discovered the charred remains of what had once evidently been the head, lurking under a pile of peppercorns.