Sunday 28 October 2012

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.

Sunday 21 October 2012

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!

Sunday 14 October 2012

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.


Sunday 7 October 2012

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.