The infinite lottery

Probability is a mathematical subject where the application of the results to the real world remains controversial, and different schools of thought flourish.

Littlewood, in his Miscellany, discusses this, and comes firmly to the conclusion that probability theory can say nothing about the real world, and that a pure mathematician should “wash his hands of applications”, or if talking to someone who wants them, should say something along the lines of “try this; it is not my businesss to justify [it]”. However, later in the book, in the section on large numbers, he is happy to estimate the odds against a celluloid mouse surviving in Hell for a week. (Probably he would have argued that this is not the “real world”.)

That said, almost all mathematicians regard Kolmogorov’s axioms as the basis for probability theory. Littlewood says that “the aspiring reader finds he is expected to know the theory of the Lebesgue integral. He is sometimes shocked at this, but it is entirely natural.”

I had a project student this year who wrote about developing probability theory for non-classical logics such as intuitionistic or paraconsistent logic. I certainly learned a great deal about non-classical logic from supervising the project, for which I am very grateful to her; I might say more about this later. What I have to say below has nothing to do with her project, but the idea was sparked by a section in one of the papers she unearthed in her literature search. This is, perhaps, my small contribution to the foundations of probability theory.

Kolmogorov’s axioms say, in brief, that probability theory is measure theory on a space with total measure 1. In more detail, the ingredients are (Ω,F,p), where

  • Ω is a set, which probabilists might call the sample space, but I rather like the philosophers’ term for this, the set of possible worlds;
  • F is a σ-algebra of subsets of Ω that is, F is non-empty, contains Ω, and is closed under complementation and countable unions;
  • p is a function from F to the real numbers satisfying
    • p(S) is non-negative for all S in F;
    • p(Ω) = 1;
    • p is additive over countable disjoint unions; that is, if the sets Si are pairwise disjoint for iN, then p(∪Si) = Σp(Si).

The paper in question is “Kolmogorov’s axiomatization and its discontents”, by Aidan Lyon, in the Oxford Handbook of Probability and Philosophy. Section 4 of the paper takes Kolmogorov’s axioms to task because they cannot model a lottery with a countably infinite number of tickets, which is fair in the sense that each ticket has the same chance of winning.

Right from the start, this struck me as odd. One of the themes of mathematical philosophy is that mathematicians are not careful enough in their work, and accept arguments without sufficient scrutiny. The proportion of people who support some form of constructivism is probably much higher among philosophers of mathematics than among mathematicians. (Typically, they reject proof by contradiction: a proof of a theorem must be a construction which demonstrates the theorem, it is not enough to show that assuming that the theorem is false leads to a contradiction.)

But here, it seems to be the other way around. I cannot imagine any construction which would actually implement a fair lottery with a countably infinite number of tickets. To point the contradiction, Kolmogorov’s axioms have no difficulty in handling the result of tossing a fair coin countably many times. This generates the set of all countable 0-1 sequences, interpreting 1 as “heads” and 0 as “tails”. Now the measure on this set is the standard product measure induced from the measure on {0,1} where each of the sets {0} and {1} has probability 1/2.

Here is the argument that a fair countable lottery is not possible. The sample space is the countable set of tickets. (Said otherwise, there is a possible world in which any ticket is the winning ticket.) We want all these outcomes to have the same probability p. Now the sample space Ω is the union of the singleton sets {Ti} for iN, which are pairwise disjoint; so, by countable additivity, if we add up p a countable number of times, the result should be 1. But this is not possible, since if p = 0, then the sum is 0, whereas if p > 0, then the result is infinite.

(The first part of this argument generalises to the fact that a countable union of null sets (sets with probability 0) is a null set.)

The difference between the two situations, it seems to me, is that I can imagine a mechanism that allows a coin to be tossed infinitely often. If we are going to have infinite processes in mathematics, this seems a fairly harmless one. But I am unable to visualise a fair method of picking one lottery ticket from a countable set. One could try the following: For each ticket, toss a fair coin infinitely often to generate the base 2 expansion of a real number in the unit interval; then the winner is the ticket whose number is the largest. Trouble is, there may not be a largest; the set of chosen numbers has a supremum but possibly no maximum.

Another way of describing the same process is like this. Take a fair coin, and toss it once for each ticket. Any ticket which gets tails is eliminated, those which get heads remain. Repeat this process until a single ticket remains, continuing into the transfinite if necessary (but there is no guarantee that this will happen!)

Littlewood gives an argument which shows that, if we really want a countable fair lottery, we have to give up either finite additivity or the property that the probability of the whole space Ω is 1. Take the following countable pack of cards: each card has consecutive natural numbers written on its two sides, and the number of cards bearing the numbers n and n+1 is 10n. There are two players, Alice and Bob. A card is chosen randomly from the pack and held up between them, so that each can see one side, and they are invited to bet at evens that the number on their side of the card is smaller than the number on the other side. If Alice sees the positive integer n, it is ten times as likely that the number on the other side is n+1 than that it is n−1. So she should bet. Bob reasons in the same way. So each has the expectation of winning.

Littlewood describes this as a “paradox”; I think it is rather more than that.

Lyon claims that it is not necessary to be able to imagine a mechanism in order for the objection to Kolmogorov’s axioms to be valid. I don’t think I agree.

Anyway, Lyon describes a possible solution of using non-standard real numbers as probabilities, so that the probability of picking a ticket in the lottery is a suitable infinitesimal with the property that adding it countably many times gives 1. But he rightly remarks that there are problems with this solution: lack of uniqueness of non-standard models and inability to name the elements.

When I read this, it struck me that there was a potentially nicer answer to the question: use John Conway’s surreal numbers as probabilities. These numbers are explicitly defined and named; morever there is a unique surreal number 1/ω with the property that adding it to itself ω times will give 1.

Conway’s number system comes out of his general framework for game theory, desribed in his book On Numbers and Games. The first account of it was the mathematical novel Surreal Numbers by Don Knuth; he describes two backpackers who unearth an ancient tablet bearing the signature “J.H.W.H. Conway” and giving the rules for the construction of Conway’s number system, and their elation and frustration as they decipher the tablet and try to prove the assertions on it.

Has anybody seen a treatment of probability using Conway’s surreal numbers? It seems to me that in order to have such a treatment, one would presumably need to modify the notion of “null set”, to address the fact that the union of countably many “null sets”, such as the lottery tickets with probability 1/ω, may not be null; there may be difficulties lurking here. The problem of inventing a mechanism for the lottery still remains, but maybe closer inspection of the way the surreal numbers are generated would suggest a method.

Actually, the sting in the tail of this story is that there are some absolutely classical mathematical results which assign “probabilities” to sets of natural numbers. For two famous examples, which incidentally lead to the same value,

  • the probability that a natural number is squarefree is 6/π2;
  • the probability that two natural numbers are coprime is 6/π2.

This uses a completely different notion of probability. The statements in question really assert that the proportion of natural numbers up to n which are squarefree (or the proportion of pairs which are coprime) tends to the limit 6/π2 as n→∞.

Advertisements
Posted in exposition | Tagged , , , , | 1 Comment

Success stories

The London Mathematical Society’s “Success stories” project has officially launched; the webpage is here.

I thought the aim was to tell the world that mathematics is a great career by recounting the stories of people who have some interesting success to tell about. Well, that is part of it, but it seems to have another aim, which is to provide role models for groups under-represented in the profession. Of course you cannot speak against this aim, but looking at the web page you might get the impression that, while most mathematicians in the UK are male, most of the successful ones are female.

Enough negativity: it is a site well worth browsing, and the people represented there have interesting stories to tell. We are all people, and mathematicians are as varied as any group of people; there is something to celebrate, and this website does it. Take a look!

And to declare an interest: you will find my success story there also.

Posted in the Web | Tagged | Leave a comment

From permutation groups to model theory

I cannot resist a conference with a title like this! But in this case, there is another very important reason to attend.

In the mid-1970s, when I began being interested in infinite permutation groups (I had been a strictly finite person before that point), I soon came to realise that I would need to know some model theory. As I have told elsewhere on this blog (for example, here, here and here), I learned it by volunteering to give the second-year lectures on logic in Oxford. I was also helped by Graham Higman’s advanced class on the Ryll-Nardzewski theorem (also proved at the same time by Engeler and by Svenonius), which says (in one formulation) that a countable first-order structure is determined up to uniqueness by the first-order sentences it satisfies together with the condition of countability if and only if its automorphism group is what is now called oligomorphic. In other words, in this situation at least, (first-order) axiomatisability is equivalent to a very high degree of symmetry. This is one of my very favourite theorems in mathematics.

Soon afterwards, Dugald Macpherson (whose undergraduate degree in Oxford was in Mathematics and Philosophy – he had been my student at Merton College) began his DPhil under my supervision. As with many of my students, he taught me much more than he learned from me; he contributed more than anyone else to the study of oligomorphic permutation groups, and has subsequently done much more in model theory and permutation groups, including work on o-minimality and on simplicity of automorphism groups.

Now Dugald is 60, and the occasion is being celebrated by a conference at the International Centre for Mathematical Sciences in Edinburgh, from 17 to 21 September this year. I will certainly be there. It looks like a super conference; many of the things I talk about here will be discussed at the meeting. The invited speakers are Peter Cameron (St Andrews), Zoé Chatzidakis (ENS, Paris), Gregory Cherlin (Rutgers), Richard Elwes (Leeds), David Evans (Imperial College), Ehud Hrushovski (Oxford), Martin Liebeck (Imperial College), Dugald Macpherson (Leeds), Angus Macintyre (QMUL), Peter Neumann (Oxford), Jaroslav Nešetřil (Charles Uni., Prague), Anand Pillay (Notre Dame), Cheryl Praeger (Uni. West. Australia), Charlie Steinhorn (Vassar), Pierre Simon (Berkeley), Slawomir Solecki (Cornell), Katrin Tent (Münster), Simon Thomas (Rutgers), John Truss (Leeds).

The web page for the conference is at http://www.icms.org.uk/permutationgroups.php. Space is limited, and registration closes on 8 June (or maybe 9 June), so apply now! There is a registration form available from the web page.

See you there!

Posted in events, history | Tagged , , , | Leave a comment

RA position in St Andrews

We are looking for a postdoctoral research assistant on the project “Bi-synchronizing automata, outer automorphism groups of Higman–Thompson groups, and automorphisms of the shift”. The Principal Investigator is Collin Bleak; I am the co-I.

The project involves an interesting mix of algebra, analysis and combinatorics: the description mentions “infinite groups of homeomorphisms […] automorphism groups of shift spaces, automata groups, the extended family of R. Thompson groups, enumerative combinatorics, and/or GAP coding”.

If you think this might be for you, details are at https://www.vacancies.st-andrews.ac.uk/.

Posted in Uncategorized | Tagged , , , , , , | Leave a comment

The Royal Society of Edinburgh

RSE

I have been to the Royal Society of Edinburgh twice in the last two weeks, for different reasons.

Yesterday it was for my induction as a Fellow, along with forty-odd others. One of the things that we were told was that the RSE is trying to diversify its membership, and it is no longer true that all the new Fellows are 70-year-old male professors; but there are still a few of us, doing what we do best.

We were encouraged to spread the word about the RSE and the good things it does, so here is my small contribution.

The RSE was founded by royal charter from George III in 1783. It differs from many national academies in the diversity of interests of its Fellows: it is not just a scientific society like the Royal Society of London, although it is true that academics in the science subjects predominate. Academics in the humanities and social sciences, public figures, business people, authors and artists all figure. Indeed, probably the best-known President ever was Sir Walter Scott, whose towering monument you pass on the way to the RSE premises from Waverley Station in Edinburgh.

Among its other functions, the RSE gives entirely non-partisan advice on matters of national interest to the Scottish government.

Before the induction ceremony we were given a tour of the building, whose chief treasures are large portraits of famous people, mostly former presidents. Here are a few of them: Michael Atiyah, Thomas Brisbane, David Brewster, P. G. Tait, and D’Arcy Thompson. (Which of these was not RSE President?)

RSE Presidents

Brisbane gave his name to the city where I was an undergraduate for four years (educated in a system based on the Scottish system). According to our guide, he took the job as Governor of New South Wales because he was an astronomer and was interested in viewing the Southern stars. But he was not the worst governor of New South Wales, although there are probably fewer things named after him than either his predecessor Lachlan Macquarie or his successor Ralph Darling. (Incidentally, in Australia he is Thomas Brisbane but the RSE calls him Makdougall Brisbane.)

My previous visit two weeks ago was for a lecture on the new Queensferry Crossing, given by Naeem Hussain, the global leader of bridge design at Arup, who had designed it. It was a good lecture, inspiring and humorous by turns. He told us that he first came to the UK in 1964, went for a holiday in Scotland, saw the then-new Forth Road Bridge, and thought to himself, “I wish I could have designed that bridge”. So, fifty years later, he got his chance. Designing a third bridge to stand beside the two iconic bridges already there was an aesthetic as well as an engineering challenge, as he acknowledged; the new bridge, like the one on the other side (the nineteenth-century Forth Bridge) has three cantilever points, while the one in the middle is suspended from two points. Moreover, although politicians boast that the bridge towers are the highest such in the UK, Naeem would rather stress how low they are. (He made them as low as the engineering would allow, and used slim pillars rather than the more common A, H or diamond shapes, so as not to overwhelm visually the other two bridges.)

This was preceded by a trip to the Visitor Centre where we had a view of the three bridges, some models of the new one, and talks by the person who commissioned it, the engineer who built it, and a university professor who gave a very entertaining talk putting it into context. (Did you know that, when the Forth Road Bridge was designed, the only motorway in the UK was the Preston By-pass?)

Here are the bridges, taken last year from the Fife side, near Aberdour.

Three bridges

On that occasion, I was able to take a good look at the grant of arms to the RSE. The heraldic description includes the phrases

Per fess wavy Sable and Argent the scientific sign “D.N.A. Helix” fessways enhanced Gules and Azure

and

A celestial crown Or showing five mullets Argent

Do you know what “mullets” are in this context? (You might be able to cheat by looking at Wikipedia.)

Posted in events, history | Tagged , , | 1 Comment

London Combinatorics Colloquia

London

The second speaker at this year’s Queen Mary colloquium, János Pach, said at the start of his talk that he first came to Britain as a backpacker some years ago; at that time he never imagined that by now there would be enough combinatorialists here to fill the quite large Peston Lecture Theatre in the Graduate Centre.

He was kind enough to mention me as one of the people who had helped bring this about, but (quite rightly) attributed a lot of credit to Paul Erdős and Bill Tutte. He told Bruce Schechter’s story about how Erdős had changed the course of Western civilisation, which bears repeating, I think. Erdős, seeing which way the wind was blowing, left Hungary in 1934. His first stop was Cambridge, where he posed the problem of tiling a square with finitely many pairwise non-congruent squares. (There is some suggestion that Erdős thought that it would turn out to be impossible.) Four bright undergraduates, Brooks, Smith, Stone and Tutte, took up the challenge, and found an elegant method that led them to the existence of such a decomposition. This success inspired Tutte to change from chemistry to mathematics. At this he made enough of an impression that he was recruited for Bletchley Park, where he broke the Lorenz Sägefisch cipher used for strategic communications by the German high command, which according to some historians may have shortened the war by a couple of years.

Since I have started with János Pach’s talk, I will say more about it. His abstract on the website and in the conference book said, simply,

This will be the bestest talk ever.

An insert gave a much more detailed abstract. In his talk, he disclaimed all responsibility for the short abstract, but said it would probably be the best part of the talk, and that things would be downhill from here on. Not so, in fact; for me, his talk was the best of the day, even if it ran over time a bit. He was talking about the analogous problem for tiling an equilateral triangle with pairwise non-congruent equilateral triangles. He and Gabor Tardos have proved that there is no such tiling, by a remarkable proof, which begins with some elementary geometry, and then wheels in random walks and martingales!

Carsten Thomassen spoke first, and told us about several new results on flows on graphs, where the flow values are restricted to a subset F of an abelian group A. (Incidentally, Carsten used G for a graph and Γ for a group; I had to change Γ to A in my notes so as not to confuse myself.) As well as the set of non-zero elements of a finite abelian group, he considered cases such as the set of third (or fifth) roots of unity in the complex plane, or the unit sphere in 2- or 3-dimensional Euclidean space.

After lunch, we had a Ramsey theory talk from Paul Russell. He began by showing us that, if the natural numbers are finitely coloured, there is an infinite subset such that all sums of two distinct elements have the same colour. Can you make the same statement for all subsets? No, he showed us ingenious constructions which refute this. These can be extended to the integers, the rationals, and finite or countable dimensional vector spaces over the rationals; but in very large vector spaces, the constructions don’t work, and the assertion holds.

Katherine Staden talked about the induced version of Turán’s theorem, maximising the number of induced subgraphs of a graph which are isomorphic to your favourite graph F. (This corresponds to the complement of Turán’s theorem as usually stated.) The induced condition makes the problem much harder; the answer is not even known for the four-vertex path. She considered the case where F is complete partite (that is, there is a partition of the vertex set so that F has all edges between parts and none within parts). In this case, the extremal graphs are partite, and there are uniqueness and stability results, proved by turning the question into an algebraic optimisation problem.

Agelos Georgakopoulos (who had to pull out at short notice last year because of the birth of his baby) talked about some nice results on the analyticity of the percolation probability function above the critical point. The tools are old theorems of Weierstrass together with some combinatorics (inclusion-exclusion, estimates for the partition function). He began with a growth model for the mafia, having the remarkable property that there is a finite limit graph which occurs almost surely as a limit component.

Finally, Nikhil Bansal spoke on the discrepancy problem: you have a family of subsets of a set, and you want to 2-colour the set so that each subset is as balanced as possible. There was a fairly recent breakthrough on this problem by Banaszczyk; Nikhil and his collaborators have found a simpler proof together with an algorithmic version which efficiently finds a colouring doing as well as the theory promises.

The weather is always beautiful for the London colloquia; this indeed goes back to the days when its predecessor used to be in Reading. It rained overnight but by morning the weather was fine again, a little cooler and a little clearer than the day before.

The second day, at LSE, featured an innovation: a poster competition, with a lot of entrants, which was judged by a subset of the speakers, and the prizewinners announced at the reception at the end of the day.

The first talk, by Perlis Sousi, was on random walks on dynamic percolation. People have considered random walks on the component containing the identity of graphs such as lattices (this component is infinite if the percolation probability is above the critical value). The new feature was letting edges change their status, independently of what it was before but with the same probability of being open; to make the question interesting, we assume that these changes are on a slower timescale than the movement of the random walker. (I wonder what would happen if you let the edges change faster but assumed some positive correlation between the new and old state of the edge.)

Patrice Ossona de Mendez has been working with Jarik Nešetřil and many others (incuding one of our hosts, Jan van den Heuvel) on sparsity in graph theory for some years now. They have developed two concepts of sparsity, called “bounded expansion” and “nowhere dense”, which turn out to be stable in the sense that a huge variety of alternative definitions come up with the same thing. He talked about five questions, concerning graph colouring, Hasse diagrams of posets, VC-dimension of families induced on subsets by vertex neighbourhoods, category theory, and first-order definability. Then he defined some new concepts called “structurally X”, where X is one of the two types of sparse graph; such graphs can be quite dense but many results about them (including complexity) work similarly to the sparse case. As usual with Patrice, it was an elegant talk, but there was rather a lot of material to take in.

After lunch, Sofia Lindqvist gave an assured performance on her result with Ben Green on monochromatic solutions to x+y = z2 in the natural numbers. They have found a phenomenon which to my knowledge has not been observed before: the answer is that they must exist for two colours, but can be avoided for three or more.

Maria Axenovich talked about induced arboricity. The arboricity of a graph is the least number of forests needed to cover all the edges of the graph. This is a well-understood parameter, and a theorem of Nash-Williams gives a formula for it. For induced arboricity, you require the subgraphs to be induced forests, which makes things far more complicated.

It is easy to see that a graph with maximum degree Δ can be coloured with Δ+1 colours (a sequential algorithm does this since there is always a colour available). Choosing a random colouring is different, and a Markov chain based on recolouring a vertex if possible requires at least Δ+2 colours (and it is conjectured that this is enough for the Markov chain, or “Glauber dynamics” as it is known, to be rapidly mixing. However, the best we knew until recently was a result of Vigoda that (11/6)Δ is enough for rapid mixing. Michelle Delcourt and her team have shaved a bit off this constant. Within a week of their result being announced, another team announced that with a different method they had shaved a bit more off.

The final talk, the Norman Biggs lecture, was given by Alexander Sidorenko, who pulled a remarkable rabbit out of a hat. He talked about two apparently unrelated areas: first, the largest Sidon set (containing no solutions of x+y = z+w), or set containing no subset summing to zero, or containing no arithmetic progression, in certain finite abelian groups. Last year there was an amazing breakthrough on the “no 3-AP problem” in abelian groups of exponent 3. The other problem was the “codegree Turán problem” for hypergraphs. He showed how results on the first type of problem can give substantially improved bounds for the second.

Posted in events | Tagged , , , , , , , | Leave a comment

Two a day

In the distant past, issues of a journal would appear every two or three months, and publication date was no more precisely defined than this; you would only know that your paper had appeared when you received the journal (if you had subscribed) or your reprints (if you have ordered any).

Now each paper has a date of its on-line publication. These dates are not a lot of use for establishing priority, since the arXiv already does this, but are necessary for filling in data on institutional repositories.

This week, I had two papers published on the same day, something I don’t think has happened to me before. One, with R. A. Bailey and Tomas Nilson, was in the Australasian Journal of Combinatorics, where publication means that it comes with volume, issue and page numbers (this is a diamond open access journal which only publishes on-line). The other, with Bertalan Bodor and Csaba Szabó, was in Algebra Universalis, and is now “first on-line” for an indefinite period.

I have discussed them here and here.

By coincidence, both are in memorial volumes, for Anne Street and Tamás Schmidt respectively.

Posted in publishing | Tagged , , , | 3 Comments