Saturday's Guardian newspaper feature about Julian Assange contained an amusing quote from a friend from his university days (Assange studied mathematics amongst other subjects): "I've often heard it remarked in the press that Julian has some idiosyncrasies. The people who make such remarks tend not to have hung around mathematics departments very much."
It's perhaps not surprising that mathematicians are associated with eccentricity. We love to tell stories about the idiosyncrasies of Erdos and Godel. Alexander Masters' recent book about the mathematician Simon Norton, The Genius in my Basement is an outstanding reflection on the biographer's art which doesn't do much for the public image of mathematicians. On the other hand, fictional mathematicians who are leading characters in novels such as Iain Banks's The Steep Approach to Garbadale and Ann Lingard's The Embalmer's Book of Recipes are reasonably normal people.
Are mathematicians more eccentric than other creative people? I suspect not: I am sure one can find just as many writers, painters, composers, actors, ... Is it perhaps just the abstract nature of our subject, and the difficulty of talking about the technicalities to non-mathematicians (or even mathematicians who specialise in different areas) which results in a focus on eccentricity? We can't tell our non-mathematical friends about a mathematician's brilliant ideas so we end up talking about their amusing eccentricities.
I'm not sure how far I have convinced myself!
A very occasional blog about maths things which interest me.
Monday, 27 August 2012
Wednesday, 8 August 2012
Maths history and anecdotes
I have been meaning to write something in response to two recent blog posts on history of mathematics and anecdote. Dennis Des Chene (aka "Scaliger") wrote "On bad anecdotes and good fun" and Peter Rowlett responded with "Mathematics: a culture of historical inaccuracy". I'm also grateful to Thony Christie of the always excellent The Renaissance Mathematicus blog, whose Twitter comment brought Scaliger's blog to my attention.
Scaliger writes about the anecdote that Euler spouted a piece of mathematical nonsense claiming to prove the existence of God, embarrassing Diderot in front of the Empress. The anecdote, as commonly told, is far from true, so why do mathematicians still tell without qualification? Rowlett wonders about the role of such anecdotes, which are arguably part of the culture of mathematics, in training mathematicians.
These are deep issues. I love anecdotes. I like serious history, too, but I am useless as a historian because I don't know enough. Whenever I have worked on historical topics, I have found that, the more I research, the less I feel able to say anything because I am increasingly aware that I do not know enough of the story. I admire both historians, who as a result of years of study are able to enlarge our understanding, and popular writers, who can so often find interesting angles on history without being intimidated as I am by the knowledge of their limitations.
Anecdotes appeal to me when they seem to tell me something, and I don;t think this is always entirely illusory. It doesn't take much thought to see that most anecdotes are constructions. As a teenager I bought a book of literary anecdotes which began with the rather rude "Switter Swatter" story about Sir Walter Ralegh (which is the subject of a contemporary round you can watch being performed here.). Is this anecdote true? It's documented at the time, but how did it get into the public domain? Only, presumably, from Sir Walter himself, and I don't take as gospel any stories by young men about their romantic successes. So despite its impeccable historical credentials I have some scepticism about this story. Most anecdotes are spread because they show someone in a good (perhaps self-depreciating) light (or because they present a negative image of someone's enemy.
Constructions may not be accurate. In his cricket report in last Saturday's Guardian, Vic Marks tells the story of the Durham wicket-keeper Chris Scott, who in 1994 dropped Brian Lara, the best batsman in the world, when he had made 18. Scott (Marks, being a good journalist, adds "it is said"!) moaned "I bet he goes on to get a hundred". Lara in fact went on to 501 not out, the highest score ever made. It's quite likely that Scott made exactly this comment at the time, and I'm not suggesting that this story is not exactly true as it stands. But even if he didn't say it at the time, he might afterwards have said something like "When I dropped him I thought that it would be just my luck if he made another hundred", and in the telling the story at some stage changed to "Scott said at the time that ...". The way memory works seems to be that we reconstruct our memories rather than retrieving them, and anecdotal memories get rewritten so that we come to "remember" what happened in the revised form. Consequently one should interpret even the most "authentic" anecdotes as a slightly idealised form of history.
What I would argue, I guess, is that anecdotes are valuable in passing on the culture of mathematics. We don;t need to express uncertainty about their "truth" because we should all know that anecdotes are not exactly true. When I first read the Euler story as a teenager I may have believed it to be literally true,.but as I became more experienced in such matters I realised that a more nuanced understanding was required. It's good that the background is now readily accessible, but we want to train young mathematicians who can read a story like this and enjoy it without necessarily believing it!
Academics apply rigour when they need to. Having been at an Oxbridge high table when World Cup football was being discussed, I can say with certainty that rigorous thinkers in one field don't necessarily bring the same quality of analysis of other matters. We all apply different standards of rigour in different parts of our lives: that's part of being human.
A final comment: I don't believe it is only mathematicians who take a cavalier approach to the history of their subject. All disciplines and professions have their cultures, built on anecdote and dubious history. Mathematics is no different in that respect.
Scaliger writes about the anecdote that Euler spouted a piece of mathematical nonsense claiming to prove the existence of God, embarrassing Diderot in front of the Empress. The anecdote, as commonly told, is far from true, so why do mathematicians still tell without qualification? Rowlett wonders about the role of such anecdotes, which are arguably part of the culture of mathematics, in training mathematicians.
These are deep issues. I love anecdotes. I like serious history, too, but I am useless as a historian because I don't know enough. Whenever I have worked on historical topics, I have found that, the more I research, the less I feel able to say anything because I am increasingly aware that I do not know enough of the story. I admire both historians, who as a result of years of study are able to enlarge our understanding, and popular writers, who can so often find interesting angles on history without being intimidated as I am by the knowledge of their limitations.
Anecdotes appeal to me when they seem to tell me something, and I don;t think this is always entirely illusory. It doesn't take much thought to see that most anecdotes are constructions. As a teenager I bought a book of literary anecdotes which began with the rather rude "Switter Swatter" story about Sir Walter Ralegh (which is the subject of a contemporary round you can watch being performed here.). Is this anecdote true? It's documented at the time, but how did it get into the public domain? Only, presumably, from Sir Walter himself, and I don't take as gospel any stories by young men about their romantic successes. So despite its impeccable historical credentials I have some scepticism about this story. Most anecdotes are spread because they show someone in a good (perhaps self-depreciating) light (or because they present a negative image of someone's enemy.
Constructions may not be accurate. In his cricket report in last Saturday's Guardian, Vic Marks tells the story of the Durham wicket-keeper Chris Scott, who in 1994 dropped Brian Lara, the best batsman in the world, when he had made 18. Scott (Marks, being a good journalist, adds "it is said"!) moaned "I bet he goes on to get a hundred". Lara in fact went on to 501 not out, the highest score ever made. It's quite likely that Scott made exactly this comment at the time, and I'm not suggesting that this story is not exactly true as it stands. But even if he didn't say it at the time, he might afterwards have said something like "When I dropped him I thought that it would be just my luck if he made another hundred", and in the telling the story at some stage changed to "Scott said at the time that ...". The way memory works seems to be that we reconstruct our memories rather than retrieving them, and anecdotal memories get rewritten so that we come to "remember" what happened in the revised form. Consequently one should interpret even the most "authentic" anecdotes as a slightly idealised form of history.
What I would argue, I guess, is that anecdotes are valuable in passing on the culture of mathematics. We don;t need to express uncertainty about their "truth" because we should all know that anecdotes are not exactly true. When I first read the Euler story as a teenager I may have believed it to be literally true,.but as I became more experienced in such matters I realised that a more nuanced understanding was required. It's good that the background is now readily accessible, but we want to train young mathematicians who can read a story like this and enjoy it without necessarily believing it!
Academics apply rigour when they need to. Having been at an Oxbridge high table when World Cup football was being discussed, I can say with certainty that rigorous thinkers in one field don't necessarily bring the same quality of analysis of other matters. We all apply different standards of rigour in different parts of our lives: that's part of being human.
A final comment: I don't believe it is only mathematicians who take a cavalier approach to the history of their subject. All disciplines and professions have their cultures, built on anecdote and dubious history. Mathematics is no different in that respect.
Sunday, 29 July 2012
Proof that I am a *pure* mathematician
I have always been drawn towards pure, rather than applied, mathematics. As a student I had no feel for mechanics: I could solve the equations but I had no physical intuition. I always felt out of my depth in any kind of applied mathematics, whereas I felt at home with abstract pure mathematics.
Now when I teach mathematics I have sometimes regretted my preference. I see the value of physical applications; I enjoy reading about relativity and quantum theory, and feel that I have gained some understandings of these topics to which, thirty years ago, I couldn't relate at all.
Now I have been looking at Mark Levi's two marvellous books, The Mathematical Mechanic and Why Cats Land on Their Feet. These are books about mechanics. The former uses physics to "prove" pure mathematical propositions, for example using an argument about a rotating fishtank to "prove" Pythagoras's Theorem. (The inverted commas reflect my pure mathematical reluctance to accept that physics can be used in this way!) The latter presents physical paradoxes and their resolution - for example, if, sitting in a seat attached rigidly to the frame of a spacecraft which is stationary in outer space, I push a balloon away from me, what happens to the spaceship?
These books are wonderful. Despite my comment about physics and proof above, I find the contents beautiful and astonishing. But they are also over my head. I have to read carefully and think deeply to get the point, and I need to be told why the paradoxes in the second volume are paradoxical because my physical understanding is so limited I don't "get" it easily.
So what these books confirm is that I have very little intuition about the physics of the world around us. Had I had a different upbringing that might not have been the case, but I have to accept that my mathematical talents do not extend at all to mechanics. I don't particularly regret that - the pleasure of pure mathematics compensates - except when I realise that my appreciation of Levi's books is so limited. I feel as I imagine someone would respond to Matisse who knew the paintings only from monochrome reproduction - there is much to enjoy but I will never be able fully to appreciate them.
This helps me understand why I enjoy quantum theory. I can't do mechanics because I have no physical intuition - but quantum theory makes a nonsense of our intuitions so my weakness isn't a problem!
Can I finish by encouraging any reader to seek out Levi's books, if you don't already know them. If you're an applied mathematician you'll love them; pure mathematicians will also find things to wonder at. Even if I can't fully appreciate them, I can still admire and enjoy.
Tuesday, 17 July 2012
Maths and technology - from the HE Maths Ideas Exchange
This post is late because I spent an exciting but exhausting weekend in Sheffield, first at the CETL-MSOR conference on mathematics teaching in HE and then at the Ideas Exchange weekend organised by Peter Rowlett of the MSOR Network. Both were extremely productive, not just for the inspiring presentations but also for the informal discussions with colleagues from across the sector. I'm very grateful for the valuable and productive conversations I've had over the last few days, and especially to Dagmar Waller and Peter Rowlett for organising these events.
The Ideas Exchange provides an opportunity for each participant to put forward, in five minutes, an idea for subsequent discussion with sympathetic colleagues. It was suggested that this might be something which one had tried and wished to share, an idea that one was planning to implement and wanted advice on, or a mad suggestion that, with refinement and suggestions from others, might just turn into something workable. This was the second such Ideas Exchange weekend - my report on the first was published in MSOR Connections (and one of the best pieces of news from the CETL-MSOR Conference is that Connections will continue). That they work so well is due to the openness and friendliness of the participants: it's a delight to spend time with people so committed to teaching mathematics effectively.
There is a lot I could write about from both events (and much that I have still to digest). But this post will focus one of my "ideas" - not actually mine at all, in fact.
At my University's teaching and learning conference one speaker mentioned a proposal that every degree course should have a compulsory final year module on "how new technology will change this subject" or something similar. (I didn't catch the name of the person to whom this proposal was attributed.) Should maths degrees contain such a module?
The Ideas Exchange provides an opportunity for each participant to put forward, in five minutes, an idea for subsequent discussion with sympathetic colleagues. It was suggested that this might be something which one had tried and wished to share, an idea that one was planning to implement and wanted advice on, or a mad suggestion that, with refinement and suggestions from others, might just turn into something workable. This was the second such Ideas Exchange weekend - my report on the first was published in MSOR Connections (and one of the best pieces of news from the CETL-MSOR Conference is that Connections will continue). That they work so well is due to the openness and friendliness of the participants: it's a delight to spend time with people so committed to teaching mathematics effectively.
There is a lot I could write about from both events (and much that I have still to digest). But this post will focus one of my "ideas" - not actually mine at all, in fact.
At my University's teaching and learning conference one speaker mentioned a proposal that every degree course should have a compulsory final year module on "how new technology will change this subject" or something similar. (I didn't catch the name of the person to whom this proposal was attributed.) Should maths degrees contain such a module?
My first reaction was that it would be hard to make a case to colleagues for dropping their favourite courses in Complex Analysis or the Analytical Algebraic Topology of Locally Euclidean Parametrization of Infinitely Differentiable Riemannian Manifolds or whatever. These courses obviously give students skills and techniques which are immediately valuable to a wide range of employers in a way which thinking about possibly applications of technology and mathematics could not possibly match.
But should our maths graduates be thinking more about how technology will change mathematics? I think there is a case. For one thing, new technology such as apps on mobile devices are making like better in many small (and some big) ways. I'd like our maths graduates to be among the leaders in this field, but I'm not sure that our teaching particularly promotes this kind of creative thinking. I'm also struck that, despite many university mathematicians' preference for chalk and blackboards, IT is changing maths in ways which we don't articulate to our students. At BMC last year Sir Timothy Gowers noted that Wikipedia is an invaluable tool for mathematicians, greatly facilitating the practice of our subject. In his recent LMS Popular Lecture Sir Timothy talked about the emergence of computers as research assistants. He, Terence Tao and many others use blogs as a tool for mathematical collaboration, and Gowers's Polymath project is perhaps shows how mathematics will be done by humans in the years before the field is taken over by creative computer research mathematicians.
It certainly seems to me that my childhood view of mathematics as an individual activity, which was perhaps only rarely a reality (Andrew Wiles?), is no longer tenable: technology is making mathematics an increasingly collaborative venture. And we should perhaps be making more of this in our undergraduate teaching.
Monday, 9 July 2012
Mathematics and Tennis
Now that a fascinating fortnight at Wimbledon has finished, it's perhaps appropriate to consider the contributions that the mathematics of tennis made to our enjoyment. I've read long ago (I forget where) an analysis that shows that the scoring system at tennis - dividing the match into games and sets - is remarkably effective at maximising the interest for spectators, creating points of excitement throughout the match: simply counting up the total points won wouldn't be nearly so exciting. As I recall, the argument is that this is why tennis attracts a bigger audience than other racket sports.
The opening chapter of Julian Havil's wonderful book Nonplussed presents three tennis paradoxes. The best (most surprising) of these is that if you are playing a strong server (the probability that the server wins a point on their serve is just over 90%) then you are more likely to break serve from 40-30 or 30-15 down than you are at love all. (There is an assumption that the probability of winning the point is independent of the score.)
Of course in any knock-out tournament, even if the better player wins every match it is by no means certain that the top two players will meet in the final. If they are in the same half of the draw, they meet earlier and, in a random draw with 2^n players, the probability of that is (2^(n-1)-1)/((2^n)-1) which is only just under 1/2. Seeding addresses this problem. But seeding can create its own issues. Suppose we have three top players, equally good, all some way better than any of their other competitors. Then two will be in the same half of the draw, and the third will have double the chances of winning of each of the other two. If this victory is then used to determine the seeding for the next tournament, that player will carry this advantage forward, and will win more tournaments than their equally-good adversaries.
The system for challenging line-calls brings in a new dimension. In each set each player can make at least three challenges when they believe a ball was wrongly called out (or in). Successful challenges don't count, but unsuccessful ones are deducted from the allowance of three. If the call is shown to be wrong, then depending on the circumstance the point is replayed or the point is won by the player challenging. The challenge must be played immediately - if you think the ball was out and you return it, you've lost your right to challenge.
How sure do you have to be that the call was wrong before you should challenge? There are obviously a lot of factors that influence the decision. How many challenges one has left - presumably one wants one in reserve for the dubious call in the decisive game still to come. The stage of the set - if the set is almost finished and you haven't used any challenges, there is little to be gained by saving them. The importance of the point - if the disputed call is resulting in a crucial service break you might challenge even if you are sure the call is correct! The gain from a successful challenge - if you are going to win, rather than lose, a point, the challenge is more worthwhile than if you are going to replay it. Yesterday Andy Murray challenged a call that his first serve was out - would that be a better challenge than a second serve called out? I would guess that the threshold estimate of probability of success before you challenge is strongly affected by all these circumstances.
There are other factors too. Sometimes you might just want a moment to regroup, and it might be worth using a challenge just to get a short break. And how do you decide whether to challenge or to play the ball? If you think your opponent's shot is just out, but you can return it, do you stop and challenge or do you play on? The decision must be made instantly!
It would be fascinating to now how much professional tennis players think about these things when using their challenges. I doubt if they do probability calculations in their heads, so do they have heuristics and if so, how good are they? Are some players better tacticians in using challenges than others?
The opening chapter of Julian Havil's wonderful book Nonplussed presents three tennis paradoxes. The best (most surprising) of these is that if you are playing a strong server (the probability that the server wins a point on their serve is just over 90%) then you are more likely to break serve from 40-30 or 30-15 down than you are at love all. (There is an assumption that the probability of winning the point is independent of the score.)
Of course in any knock-out tournament, even if the better player wins every match it is by no means certain that the top two players will meet in the final. If they are in the same half of the draw, they meet earlier and, in a random draw with 2^n players, the probability of that is (2^(n-1)-1)/((2^n)-1) which is only just under 1/2. Seeding addresses this problem. But seeding can create its own issues. Suppose we have three top players, equally good, all some way better than any of their other competitors. Then two will be in the same half of the draw, and the third will have double the chances of winning of each of the other two. If this victory is then used to determine the seeding for the next tournament, that player will carry this advantage forward, and will win more tournaments than their equally-good adversaries.
The system for challenging line-calls brings in a new dimension. In each set each player can make at least three challenges when they believe a ball was wrongly called out (or in). Successful challenges don't count, but unsuccessful ones are deducted from the allowance of three. If the call is shown to be wrong, then depending on the circumstance the point is replayed or the point is won by the player challenging. The challenge must be played immediately - if you think the ball was out and you return it, you've lost your right to challenge.
How sure do you have to be that the call was wrong before you should challenge? There are obviously a lot of factors that influence the decision. How many challenges one has left - presumably one wants one in reserve for the dubious call in the decisive game still to come. The stage of the set - if the set is almost finished and you haven't used any challenges, there is little to be gained by saving them. The importance of the point - if the disputed call is resulting in a crucial service break you might challenge even if you are sure the call is correct! The gain from a successful challenge - if you are going to win, rather than lose, a point, the challenge is more worthwhile than if you are going to replay it. Yesterday Andy Murray challenged a call that his first serve was out - would that be a better challenge than a second serve called out? I would guess that the threshold estimate of probability of success before you challenge is strongly affected by all these circumstances.
There are other factors too. Sometimes you might just want a moment to regroup, and it might be worth using a challenge just to get a short break. And how do you decide whether to challenge or to play the ball? If you think your opponent's shot is just out, but you can return it, do you stop and challenge or do you play on? The decision must be made instantly!
It would be fascinating to now how much professional tennis players think about these things when using their challenges. I doubt if they do probability calculations in their heads, so do they have heuristics and if so, how good are they? Are some players better tacticians in using challenges than others?
Monday, 2 July 2012
The LMS Popular Lectures - Gowers and Penrose
Last week was exceptionally busy, but one highlight was the opportunity to hear two of today's greatest mathematicians, Sir Timothy Gowers and Sir Roger Penrose, deliver the London Mathematical Society's Popular Lectures in central London. (There is another opportunity to hear them in Birmingham on 26 September, and the lectures are normally made available on DVD).
This was a wonderful opportunity to hear two top mathematicians talking about their views of mathematics. Both talks took their theme from the Turing centenary, a reminder of just how important a contribution Turing made to the culture and practice of contemporary mathematics.
Gowers was talking about the possibility of computers becoming mathematicians, in the sense of creating and proving theorems. He was particularly interesting in his analysis of two fairly well-known mathematics puzzles which can be solved by the right insight. What Gowers did here was to show how these insights can be understood, not as a sudden creative spark from nowhere, but as the consequence of an understandable line of mathematical thinking. This was fascinating, and empowering: these kind of insights don't need incomprehensible strokes of brilliant genius but could be accessible if you think hard enough about the problem.
Gowers predicted that in 50 years time computers will be able to do mathematical research better than humans. He didn't discuss how mathematicians will react to this. If pure mathematics can be created by humans, will people still want to do it? This kind of mathematics is already an esoteric pursuit: if one is doing world-leading pure mathematics it is unlikely that more than a small number of people are actively engaging with your work. If computers are doing it better, will human mathematicians still see it as a worthwhile activity to devote their life to?
Penrose talked about consciousness. His argument, as I understand it, is that human consciousness is not subject to the limitations that Godel's Theorems show apply to formal systems, and that we need a new theory that goes beyond quantum theory in order to understand consciousness. He presented a toy model universe to show that the universe need not be computable - the toy model certainly proved that it is possible to have uncomputable universes - but I am unconvinced by his arguments.
Although I am not qualified to disagree with Penrose, who knows much more and has thought much more deeply about these subjects than I do, I don't think his arguments are valid. I do not understand why he thinks Godel's Theorems do not apply to human thought. His assertion seems to be based on a claim that humans can always jump "outside the system" to see implications that are not formally consequences of a logical system, so there can be no "Godel sentence" that is true but which human consciousness cannot prove to be true. I don't understand why he can be confident of this, so I don't see that consciousness presents a problem for quantum theory. Nor do I share the worries he expressed that the Measurement Problem in quantum theory. Everett's interpretation, that we view only one branch of the universal wavefunction, seems to me to be a perfectly logical solution to the Measurement Problem - we don't have to accept it, but it does show that a solution is possible, in the same way that Penrose's toy model uncomputable universe makes its point.
Regardless of whether .I was persuaded by the speakers, this was an exciting and stimulating evening which kept a huge audience engaged for the whole of a long evening. Well done the LMS!
This was a wonderful opportunity to hear two top mathematicians talking about their views of mathematics. Both talks took their theme from the Turing centenary, a reminder of just how important a contribution Turing made to the culture and practice of contemporary mathematics.
Gowers was talking about the possibility of computers becoming mathematicians, in the sense of creating and proving theorems. He was particularly interesting in his analysis of two fairly well-known mathematics puzzles which can be solved by the right insight. What Gowers did here was to show how these insights can be understood, not as a sudden creative spark from nowhere, but as the consequence of an understandable line of mathematical thinking. This was fascinating, and empowering: these kind of insights don't need incomprehensible strokes of brilliant genius but could be accessible if you think hard enough about the problem.
Gowers predicted that in 50 years time computers will be able to do mathematical research better than humans. He didn't discuss how mathematicians will react to this. If pure mathematics can be created by humans, will people still want to do it? This kind of mathematics is already an esoteric pursuit: if one is doing world-leading pure mathematics it is unlikely that more than a small number of people are actively engaging with your work. If computers are doing it better, will human mathematicians still see it as a worthwhile activity to devote their life to?
Penrose talked about consciousness. His argument, as I understand it, is that human consciousness is not subject to the limitations that Godel's Theorems show apply to formal systems, and that we need a new theory that goes beyond quantum theory in order to understand consciousness. He presented a toy model universe to show that the universe need not be computable - the toy model certainly proved that it is possible to have uncomputable universes - but I am unconvinced by his arguments.
Although I am not qualified to disagree with Penrose, who knows much more and has thought much more deeply about these subjects than I do, I don't think his arguments are valid. I do not understand why he thinks Godel's Theorems do not apply to human thought. His assertion seems to be based on a claim that humans can always jump "outside the system" to see implications that are not formally consequences of a logical system, so there can be no "Godel sentence" that is true but which human consciousness cannot prove to be true. I don't understand why he can be confident of this, so I don't see that consciousness presents a problem for quantum theory. Nor do I share the worries he expressed that the Measurement Problem in quantum theory. Everett's interpretation, that we view only one branch of the universal wavefunction, seems to me to be a perfectly logical solution to the Measurement Problem - we don't have to accept it, but it does show that a solution is possible, in the same way that Penrose's toy model uncomputable universe makes its point.
Regardless of whether .I was persuaded by the speakers, this was an exciting and stimulating evening which kept a huge audience engaged for the whole of a long evening. Well done the LMS!
Saturday, 23 June 2012
In praise of Knuth - the joy of algorithms
Since I am taking part in a Turing-related Lates evening at the Science Museum on Wednesday 27 June, in which my contribution will look at a curious mathematical algorithm and its applications in computing, I have been thinking about some of the algorithms I have used in programming, and this post will describe one particular favourite (not the algorithm I will be demonstrating on Wednesday).
I used to be a keen bridge player. Sometimes in competitions hands were "computer-dealt" and people noticed that the card distributions seemed to be less regular than in hands shuffled and dealt physically. Good players even adjusted their play according to whether the hand was dealt by a human or a computer. The moral is that human shuffling isn't perfectly random.
Anyway, I wanted to programme the shuffle of a pack of cards so that I could use computers to explore strategies for playing various forms of patience ("solitaire" to Americans). In particular a student project verified that the probability of clock patience coming out is indeed 1/13, as I had proved as a schoolboy. How do you get a computer to shuffle a pack of cards (or equivalently to generate a random permutation of the numbers 1 to 52, or more generally 1 to n)? (In this post I am using "random" to mean that all possibilities are equally likely, which is what one hopes for in shuffling cards.)
I thought the obvious approach was to generate successive random (equally likely) integers between 1 and n, simply rejecting those that had already been drawn. As we go through the shuffle, we are more and more likely to generate random numbers corresponding to cards already dealt, so towards the end it can take a long time to find an undealt card - when there is only one number left to be drawn, the probability of hitting it is only 1/n and the expected number of draws required to get it is n. In practice this algorithm seemed to work OK for a pack of 52 cards - the probability that it takes an absurdly long time to get the last few cards is in fact quite small, and some clumsy ad hoc adjustments could improve it. The result was a messy piece of code which might take some time to complete the shuffle for a large pack.
Then a colleague (thanks, Don) told me about Knuth's shuffling algorithm (which it turns out is a variation of one devised by Fisher and Yates before the computer era). It's beautiful. To shuffle n cards, you simply do the following: for i between 1 and n, we successively swap card i with a random card in the pack. It's easy to see that the result is a random permutation of the pack and that all possible permutations are equally likely. We have a simple algorithm, very easy to programme, that generates a random shuffle in a fixed number of steps.
One of the joys of mathematics can be finding that there is a beautiful, simple solution to a problem on which one has spent a lot of time working with messy, unsatisfactory methods. This was such an example. I remember how happy I felt when I learned about this algorithm!
Of course, the downside is that I am reminded that people like Knuth always seem to produce beautiful, simple algorithms in contrast to my clumsy efforts. It's a bit like watching Messi play football - how many can aspire to play like that? - except that I am left with the frustrating feeling that I should have been able to come up with the algorithm myself. Luckily perhaps I have now reached an age where I can appreciate beautiful mathematics without beating myself up over my failure to do it for myself.
I used to be a keen bridge player. Sometimes in competitions hands were "computer-dealt" and people noticed that the card distributions seemed to be less regular than in hands shuffled and dealt physically. Good players even adjusted their play according to whether the hand was dealt by a human or a computer. The moral is that human shuffling isn't perfectly random.
Anyway, I wanted to programme the shuffle of a pack of cards so that I could use computers to explore strategies for playing various forms of patience ("solitaire" to Americans). In particular a student project verified that the probability of clock patience coming out is indeed 1/13, as I had proved as a schoolboy. How do you get a computer to shuffle a pack of cards (or equivalently to generate a random permutation of the numbers 1 to 52, or more generally 1 to n)? (In this post I am using "random" to mean that all possibilities are equally likely, which is what one hopes for in shuffling cards.)
I thought the obvious approach was to generate successive random (equally likely) integers between 1 and n, simply rejecting those that had already been drawn. As we go through the shuffle, we are more and more likely to generate random numbers corresponding to cards already dealt, so towards the end it can take a long time to find an undealt card - when there is only one number left to be drawn, the probability of hitting it is only 1/n and the expected number of draws required to get it is n. In practice this algorithm seemed to work OK for a pack of 52 cards - the probability that it takes an absurdly long time to get the last few cards is in fact quite small, and some clumsy ad hoc adjustments could improve it. The result was a messy piece of code which might take some time to complete the shuffle for a large pack.
Then a colleague (thanks, Don) told me about Knuth's shuffling algorithm (which it turns out is a variation of one devised by Fisher and Yates before the computer era). It's beautiful. To shuffle n cards, you simply do the following: for i between 1 and n, we successively swap card i with a random card in the pack. It's easy to see that the result is a random permutation of the pack and that all possible permutations are equally likely. We have a simple algorithm, very easy to programme, that generates a random shuffle in a fixed number of steps.
One of the joys of mathematics can be finding that there is a beautiful, simple solution to a problem on which one has spent a lot of time working with messy, unsatisfactory methods. This was such an example. I remember how happy I felt when I learned about this algorithm!
Of course, the downside is that I am reminded that people like Knuth always seem to produce beautiful, simple algorithms in contrast to my clumsy efforts. It's a bit like watching Messi play football - how many can aspire to play like that? - except that I am left with the frustrating feeling that I should have been able to come up with the algorithm myself. Luckily perhaps I have now reached an age where I can appreciate beautiful mathematics without beating myself up over my failure to do it for myself.
Subscribe to:
Posts (Atom)