The Two-Box Paradox - what does random mean?

John Barrow finished his marvellous talk to the IMA London Branch this week with  a baffling paradox.  I can pick either of two boxes and  keep the contents of the one I choose.  I am told that one box contains twice as much money as the other.

Suppose I choose box A, and on opening it I find that it contains an amount x.  I am asked if I wish to switch.  What is the expected outcome?  It is equally likely that I have chosen the smaller or the larger amount.  If I stick with my choice, I gain x.  If I switch, my expected gain is 1/2.(x/2) + 1/2(2x), which is 5x/4, a higher number, so my rational choice is to switch.  But that applies whatever the value of x, so regardless of what I find when I open the box, I am going to switch.  So why didn't I just choose box B in the first place?  Well, because the same argument would have required me to switch to A on opening that box.

(A variation could allow the sums to be negative, with the same rule.  In that case logic tells me I stick if I find that x is negative and switch if x is positive.)

Apparently this paradox was attributed to Schrodinger by the mathematician J.E. Littlewood, who mentions it in his Miscellany..

Professor Barrow addressed the apparent paradox by saying that it assumes that money is infinitely divisible. But that is not the case: if we are dealing in notes and I find that box A contains £1, I know that must be the smaller amount because there is no smaller value of money that box A could contain.  That is a valid point, but it doesn't seem to me to be a wholly satisfying resolution.

Suppose the boxes contains not money but quantities of gold, so that there is no limit to how far it can be divided.  Then there is no lowest possible value.  Of course, in our physical world, matter cannot be divided infinitely, but in an infinite universe with different laws of physics one could postulate that gold is infinitely divisible and then how do we resolve the paradox?  I don't quite believe that the Two-Box Paradox is proof that the laws of the Universe must be based on an atomic theory, so that infinite divisibility is impossible.

Coincidentally I had asked students an apparently very different problem (taken from Chris Maslanka's column in the Guardian a few weeks ago).  If I choose three consecutive integers randomly, what is the probability that their product is divisible by 48?  I'll leave that for you to solve: the answer is in one sense quite straightforward, but in another it is problematic.

What is the probability that a randomly chosen integer is divisible by 7?  You might think it is obviously one in 7.  One of my mathematical heroes, the group theorist William Burnside, got involved in a bitter argument with R.A. Fisher over exactly this question.  If you choose an integer randomly from the set {1,2,3,4,5,6,7,8, 9,10,11,12,13,14,15,...} it looks as if there is a one in seven chance that it is a multiple of 7.  But we can also write the set of all integers as {1,7,2,14,3,21,4,28,5,35,6,42,8,49,9,56,10,63,11...}, alternating numbers not divisible by 7 with those which are.  This is again the set of positive integers: we can see that every positive integer is listed.  But every second integer in the list is divisible by 7, so it looks like the probability that a random integer is a multiple of 7 is as high as 1/2.

Choosing from infinite sets is problematic.  It's not that an event with probability 0 cannot happen - it can.  Spin a bicycle wheel and let it come to rest: the bottom-most point is a random point of the circumference. There are infinitely many points on the circumference (in a non-atomic universe, anyway) so the probability that the wheel came to rest on that point was 0. So either an event of probability 0 has happened or the wheel cannot stop spinning.  And there is no such thing as perpetual motion!

But choosing a random integer from the infinite possibilities presents problems.  If all integers are equally likely, then the possibility that the chosen integer n is less than, say, one million, is infinitesimally small.  The probability that it is less than one googol, or one googolplex, is still infinitesimally small.  It's inconceivable that a random integer could be identified by name (or in any other way) in the lifetime of the universe so far.  With probability one, n has more digits than one could write using all the atoms in the universe.  So finding out whether n is divisible by 7 is not really a sensible question.  The "divisible by 48?" problem I mentioned above needs to be specified much more carefully (and then the intuitive answer is correct).

To work out the true odds in the case of the Two-Box Paradox one needs to know how the contents of the boxes were chosen.  The paradox assumes the values are chosen from an infinite range, and that's where the problems lie.

Here's another one.  I have chosen a random number in the range [0,1].  What is the probability that it is rational?  A pure mathematician would say 0 - there are many more irrational numbers than rational.  But I've just tried this with my computer.  I'm using Excel: that surely has high enough precision for every practical purpose.  In ten million trials I have yet to generate an irrational number.  So the theoretical probability is 0 but my estimate from my experiments is 1.  Can computer simulation really be that inaccurate?

That may seem a frivolous example but I think it gets to the heart of the Two-Box paradox.  Random selection from infinite possibilities needs to be handled very carefully.

A slight indisposition for me, a disaster for Scottish football

On Tuesday I was mildly unwell - a seasonal cold, so I spent the day in bed.  This was a disappointment because I missed  a trip to Thorpe Park with our new students (and I was genuinely sorry to miss it, despite what you are probably thinking).  On Tuesday evening the Scottish football team played Belgium - a highly fancied squad - in Brussels in a World Cup qualifying match and - another disappointment for me - they lost 2-0.

If I had not been mildly unwell on Tuesday then Scotland would have beaten Belgium.   (1)

You may think that statement is unlikely, but it is absolutely true.  At least if you are a mathematician, that is.  By the rules of propositional logic, the proposition "If p then q" is true whenever q is false.  Since the proposition "I was not mildly unwell on Tuesday" is false, then statement (1) is true.

In fact, we can strengthen it.  This statement is also true:

If I had not been mildly unwell on Tuesday, then Scotland would have beaten Belgium 5-0.    (2)

And so is this one:

If I had not been mildly unwell on Tuesday, then Scotland would have beaten Belgium 6-0.    (3)

It might appear that statements (2) and (3) contradict each other.  They don't. They are both true, and their mutual truth merely confirms that the proposition "I was not mildly unwell on Tuesday" is false.  (Who needs doctor's notes?)

What this tells us is that mathematical language sometimes does not agree with everyday language. Many people would question the truth of statement (1): in everyday language the sentence appears to have meaning.  In propositional logic if the antecedent ("I was not mildly unwell on Tuesday") is false then it has no bearing on any other proposition.  In English statement (1) implies a connection, and many people would regard the statement as meaningful (and false).  Mathematical logic suggests that this is misguided: when we move down one branch of the universal wave-function, it is meaningless to speculate on what might have happened on the branches not travelled.  It's very human to do so, and makes for good pub conversations, but ultimately we are wrong to imagine that statements like (1) are meaningful.

If only I had finished this post five seconds earlier, I would have won millions of pounds in the lottery!

Maths is everywhere - and nowhere

I'm very much looking forward to John Barrow's forthcoming talk to the IMA London Branch.  John is an excellent speaker whose talks are always entertaining and full of mathematical interest.  (As are his books, whether they are on the mathematics of sport, or cosmology and the infinite.)  His title is "Maths is everywhere".  I have no idea what examples he will be referring to, but I am sure they are fascinating.  The talk is on Tuesday October 23rd at University College, London: if you are in the area I strongly recommend it.  Details are on the IMA website.

The title "Maths is everywhere" is absolutely true, and the variety of maths that we use daily never ceases to impress me.  For example, in planning my journey to UCL next Tuesday I will be using graph theory (to plan my journey), statistics and probability (to allow for train delays), multi-objective optimisation (I want my route to be quick, convenient and cheap!).  Quite apart from all the engineering mathematics that has gone into the building of London's transport infrastructure, there is the massive effort of timetabling of trains and tubes (one of our recent graduates works in scheduling in the railway industry).  There is the mathematics of social networking which makes events like this possible, and the mathematics of weather forecasting which will help me make an informed decision as to whether I take an umbrella.  There's the mathematics of optics, without which I would have enormous difficulty navigating London, so dependent am I on my spectacles.  And the same mathematics will be used by the data projector which will project Professor Barrow's examples.

So mathematics certainly is everywhere.  That impresses me, but, since at heart I am a pure mathematician, I don't really care too much.  I still have an instinctive view that mathematics is about eternal truth, independent both of the physical world and of the human mind.  Seventeen would be prime if no being with the ability to count had ever existed.  Fermat's theorem that x^p and x have the same remainder when divided by p would be true in any universe that could possibly exist, regardless of the laws of physics.  I am increasingly aware that this view is naive and probably untenable, but that's what my heart tells me.  If there were no mathematicians, if there were no universe, mathematics would be no less true.

So mathematics is everywhere, but if there were nowhere for mathematics to be, it would still exist.

Why does it take so long to learn mathematics?

I'm teaching graph theory this year.  It was one of my favourite areas of mathematics when I was a student.  It contains many gems, ranging from with Euler's solution to the problem of the seven bridges of Konigsberg to the power of Ramsey's Theorem.  The arguments seem to me to be unusually varied, and often sufficiently elementary that great depth of study is not required.

I have had very little contact with graph theory in the time since I graduated.  As an undergraduate I used Robin Wilson's Introduction to Graph Theory, and I am now using it as the basis of my course.  I remember enjoying the book in my youth, and finding it approachable, but I don't remember finding the material as straightforward as it now seems.  (My students aren't finding it entirely straightforward, either, but that may be my fault.)

Why is this?  I don't think I'm a better mathematician than I was 35 years ago.  In terms of solving exam questions, I would not perform as I did when I was twenty.  Even with practice, I am sure I could not get back to that level, and not only because I no longer value that kind of cleverness enough to put the effort in.  I now have a much better general understanding of mathematics and how it all fits together, but I no longer have the ability to master detail that I once did.  

Perhaps Wilson's book (which has gone through four more editions since my undergraduate days) has improved, but, with all due respect to its distinguished author, I doubt if it has really changed sufficiently to make a difference.  (Pure mathematics doesn't change much: theorems that are proved generally remain proved, the Four-Colour Theorem notwithstanding.) 

Learning mathematics takes time, and it has always astonished me how much better I understand material when I go back to it, months or years later, than when I first studied it.  As John von Neumann is said to have told a student who complained that they didn't understand a piece of mathematics, "You don't understand mathematics, laddie, you get used to it."  Even if I haven't looked at Philip Hall's Marriage Theorem, for example, for 35 years, the proof seems much simpler to me now than it did when I was first immersed in the subject area. 

Perhaps I am misremembering my difficulties as a student: perhaps I didn't find it as difficult as I now remember it.  Certainly I had little understanding of how an area of mathematics fitted together: my learning at University consisted of reading strings of definitions and theorems, with little idea where it was all going, making sure I understood each result before going on to the next one, until, perhaps, in the last lecture of the course the lecturer would say something like "and so we have now classified all Lie algebras" and I would suddenly find out what the point of it all had been.  I now feel that I would have been a much more effective mathematician if I had read more superficially, skipping proofs until I understood the context, but since got good marks as an undergraduate I had no incentive to adopt what I now feel would have been a much better strategy.

But I think it is the case with mathematics, much more than with many other disciplines, that time is essential to understanding.   Things we struggle with become much simpler when we return to them months later.  This is why modularisation of mathematics studies is so pernicious.  Examining students in the same semester as they have learned an advanced mathematics topic is, I feel, grossly unfair.  It forces our exams to be superficial and makes it impossible to test deep understanding.  At least, although my graph theory course finishes in December, the exam is not till May.  I suspect my students don't like that, but they are likely to do much better than if they faced the same exam immediately after the final lecture.

Relatively Prime

Relatively Prime is a new maths podcast from Samuel Hansen.  I'm delighted that an early episode, The Toolbox, begins by discussing my favourite area of mathematics, game theory (the subject of my very first post in this blog).  Samuel interviews the eminent writer on game theory, Steven J. Brams, whose book The Presidential Election Game I devoured when it first came out many years ago.  Brams argues that Shakespeare had an intuitive understanding of game theory and discusses applications of the mathematics in Hamlet and Macbeth.

It is particularly fitting that game theory features in Relatively Prime because game theory contributed to the podcast's very existence.  Samuel raised the funding for Relatively Prime through Kickstarter, a crowd-sourcing scheme.  Various individuals pledged funds to make the project happen.  If Samuel reached his target funding before the deadline, these pledges would be called in; otherwise they would lapse.

I was keen that Relatively Prime should be funded.  I admired Samuel's previous work.  With Peter Rowlett, he is responsible for the excellent weekly Math/Maths Podcast which has, amazingly, now been going for over two years.  (In the interests of transparency I should note that I have contributed to this podcast on a couple of occasions.)  Even though Samuel is responsible for the incorrect abbreviation for "Mathematics" in the title of that podcast, I was prepared to consider making a small financial contribution to make Relatively Prime happen.

So consider my situation last summer.  I was willing to contribute (a little) to the project, but wasn't sure my contribution would be necessary.  From my perspective, the ideal outcome would be that Samuel raised enough from other well-wishers, and I could enjoy the result without paying a penny.  But I would rather make a contribution than see the project fail.

No doubt many others are in the same position.  We can see how much has been pledged, and if five minutes before the deadline the project had been 5 dollars short, I would certainly have jumped in.  But if the project (which sought $8000) were $5000 short just before the deadline, then it's not worth my while wasting time pledging to a lost cause.  How do potential donors play it?

Well, I did what no doubt many others did - wait for some time to see what was happening.  With a few days to go , there were enough backers to show that there was some interest, but as the deadline day dawned the project was a long way short, but word of mouth was building up.  The last few hours were remarkably tense as the pledges started coming in, and suddenly the momentum built up and Samuel reached his target.  I was one of the many who contributed on the last day.  About 140 people, I think, contributed to Relatively Prime.

As a potential backer one uses game theory here to help achieve the desired outcome, which is that the project gets funded but one doesn't pay more than one's fair share when others were also willing to contribute.  How does it work?  Nothing significant is going to happen until fairly close to the deadline.  I think the  intuitive game theorist (like Shakespeare, apparently) would fix a maximum contribution they were prepared to make.  They would make a very small contribution at a relatively early stage, to encourage other potential backers by showing that there is some interest, and would then wait until a few hours before the deadline, perhaps committing a little more early on the final day but then hoping that others' contributions will come in.  At the last minute, if necessary, they would be prepared to go up to their limit if the target hasn't been reached, but they wouldn't throw all their money in early because that way other intending funders might be let off the hook.

Of course this game theory meant that if Samuel were to reach his target, it would happen at the very last minute (as indeed happened on 3 August last year).  The cost of all this game theory was a very nervous few days for Samuel when he was convinced his project would fail.  So it is entirely appropriate that Relatively Prime has opened with an illuminating discussion of this fascinating branch of mathematics.

A mathematical device

Thanks to an ingenious mathematical invention we can now tell the time in the garden.

(Added 22/9/12) It seems fairly accurate though I haven't found the switch for the British Summer Time setting yet.   Must be on the back where it's inaccessible!

Amazing mathematics - the abc conjecture

I heard earlier this week that the solution to an outstanding mathematical problem, the proof of the abc conjecture, has been announced.  (The proof is claimed by Shinichi Mochizuki of Kyoto University, and the ideas are so new and deep that it will take a long time for mathematicians to digest the work and be convinced of the validity of the proof, but the claim is being taken seriously.) Why did this news on Twitter make me happy?

You might think this would have been because it was a problem I have been thinking about for years, that I have attempted to solve myself, that I have lost sleep on.  Or perhaps because I am aware of the ramifications for mathematics, the new vistas that will be opened up, the new opportunities that will arise.

Well, I had heard of the abc conjecture.  Perhaps I once even knew what it was, but I had forgotten.  I have no knowledge of the subject area, the applications (if any) or the methods used.

Yet I am excited by the news of the possible proof!  How is it that a development about a problem which I know nothing about, which I couldn't even describe in the most general terms, can matter to me?

Well, here (from the excellent Wikipedia article on the conjecture) is a statement of the conjecture: it asserts that the answer to the following question is "yes":  "For every ε > 0, are there only finitely many triples of coprime positive integers a + b = c such that c > d^(1+ε), where d denotes the product of the distinct prime factors of abc?"  What does this mean?  Basically if the conjecture is true, then (as I understand it) it means that only exceptionally is the product of the prime factors of abc significantly less than c.

Now this is, frankly, quite an obscure statement about numbers, and I cannot envisage any life-changing applications.  What I find wonderful is that human minds like mine can prove this statement.  I cannot even begin to imagine how one would set about proving such a conjecture.  I still have an instinctive belief (which, rationally, I know is rather naive) that mathematical facts are true regardless of the nature of the human brain, the laws of nature, and so on: thirteen would still be a prime if the human race had never existed, if the laws of physics were totally different, if no sentient creature had ever come into being.  That a mind like mine can establish such necessary, deep facts is amazing, a glimpse of something much more true than anything else in our existence.