Bob

by Stubborn Mule on 5 February 2015 · 4 comments

Last year I wrote on a couple of occasions about the Sleeping Beauty problem. The problem raises some tricky questions and I did promise to attempt to answer the questions, which I am yet to do. Only last week, I was discussing the problem again with my friend Giulio, whose paper on the subject I published here. That discussion prompted me to go back to the inspiration for the original post: a series of posts on the Bob Walter’s blog. I re-read all of his posts, including his fourth post on the topic, which began:

I have been waiting to see some conclusions coming from discussions of the problem at the Stubborn Mule blog, however the discussion seems to have petered out without a final statement.

Sadly, even if I do get to my conclusions, I will not be able to get Bob’s reaction, because last week he died and the world has lost a great, inspirational mathematician.

Bob was my supervisor in the Honours year of my degree in mathematics and he also supervised Giulio for his PhD. Exchanging emails with Giulio this week, we both have vivid memories of an early experience of Bob’s inspirational approach to mathematics. This story may not resonate for everyone, but I can assure you that there are not many lectures from over 25 years ago that I can still recall.

The scene was a 3rd year lecture on Categories in Computer Science. Bob started talking about stacks, a very basic data structure used in computing. You should think of a stack of plates: you can put a plate on the top of the stack, or you can take one off. Importantly, you only push on or pop off plates from the top of the stack (unless you want your stack to crash to the floor). And how should a mathematician think about a stack? As Bob explained it, from the perspective of a category theorist, the key to understanding stacks is to think about pushing and popping as inverse functions. Bear with me, and I will take you through his explanation.

Rather than being a stack of plates, we will work with a stack of a particular type of data and I will denote by X the set of possible data elements (X could denote integers, strings, Booleans, or whatever data type you like). Stacks of type X will then be denoted by S. Our two key operations are push and pop.

The push operation takes an element of X and a stack and returns a new stack, which is just the old stack with the element of X added on the top. So, it’s a function push: X ×  → S. Conversely, pop is a function  → X ×  which takes a stack and returns the top element and a stack, which is everything that’s left after you pop the top.

So far, so good, but there are some edge cases to worry about. We should be able to deal with an empty stack, but what if we try to pop an element from the empty stack? That doesn’t work, but we can deal with this by returning an error state. This means that we should really think of pop as a function pop → X × I, where I is a single element set, say {ERR}. Here the + is a (disjoint) union of sets, which means that the pop function will either return a pair (an element of X and a stack) or an error state. This might be a bit confusing, so to make it concrete, imagine I have a stack s = (x1, x2, x3) then

pop((x1, x2, x3)) = (x1, (x2, x3))

and this ordered pair of data element xand (shorter) stack (x2, x3) is an element of X × S. Now if I want to pop an empty stack (), I have

pop(()) = ERR

which is in I. So pop will always either return an element of X × S or an element of I (in fact, the only element there is).

This should prompt us to revisit push as well, which should really be considered as a function push: X × S + I → S which, given an element of X and a stack will combine them, but given the single element of I will return an empty stack, so push(ERR) = ().

The key insight now is that pop and push are inverses of each other. If I push an element onto a stack and pop it again, I get back my element and the original stack. If I pop an element from a stack and push it back on, I get back my original stack. Extending these functions X × ensures that this holds true even for the edge cases.

But if push and pop are inverses then X × S + I  and S must essentially be the same—mathematically they are isomorphic. This is where the magic begins. As Bob said in is lecture, “let’s be bold like Gauss“, and he proceeded with the following calculation:

X × S + I = S

I = SX × S = S × (I – X)

S = I / (I – X)

and so

S = I + X + X2 + X3 + …

The last couple of steps are the bold ones, but actually make sense. The last equation basically says that a stack is either an empty stack, a single element of X, an ordered pair of elements of X, an ordered triple of elements of X and so on.

I’d known since high school that 1/(1-x) could be expanded to 1 +  + x2 + x3 + …, but applying this to a data structure like stacks was uncharted territory. I was hooked, and the following year I had the privilege of working with Bob on my honours thesis and that work ultimately made it into a couple of joint papers with Bob.

I haven’t seen Bob face to face for many years now, but we have occasionally kept in touch through topics of mutual interest on our blogs. While I have not kept up with his academic work, I have always considered him more than just a brilliant mathematician. He was a creative, inspirational, radical thinker who had an enormous influence on me and, I know, many others.

RFC Walters, rest in peace.

{ 4 comments }

Musical Education

by Stubborn Mule on 9 November 2014 · 76 comments

Musical EducationOn our longer family drives I take an old iPod crammed with even older music. Usually I take requests, and almost inevitably the children choose They Might Be Giants, and preferably the tracks Fingertips and Particle Man. But, our last trip was different. Instead I took the opportunity to the children some exposure to artists formative in the history of popular music. There is nothing like a grand plan to pass the time on the freeway.

Skimming through the albums, I decided that the best of The Jam would be a good place to start. It went down surprisingly well. Even our eldest, who generally prefers electronica, responded well to Eton Rifles. Marking that up as a success, the next choice was the best of Madness. This was more familiar territory, as they already knew (and loved) I Like Driving in My Car. Again it was successful.

Although this was a good start, it was not systematic, depending as it did on swift scanning through the albums on the iPod. So I have now begun to assemble a playlist on Spotify with a name as grandiose as its aim: Musical Education. The rules are simple but tough:

  1. Four representative tracks each (no more) are selected from major artists in the history of popular music.
  2. Each track must be from a different studio album. If the artist does not have at least four albums, refer step three. Singles not released on an album are also eligible.
  3. Single tracks can be included for important artists lacking the catalogue breadth for four essential tracks.

The playlist has nearly reached 150 tracks and includes artists such as The Doors, The Animals, James Brown and Prince. Inevitably, some choices reflect my own interests. My taste in Krautrock ensures the appearance of Kraftwerk, but in their defence I point to their appearance at the Tate and MOMA in recent years. Other choices may not have the endorsement of the artworld, but surely the sheer persistence of Mark E. Smith in continuing his post-punk aesthetic justifies a place for The Fall (Update: also The New Yorker rates The Fall highly too). As for XTC, well my own obsessions may be tilting the scales of significance. But perhaps not.

For some artists, choosing only four tracks is extremely difficult. Four David Bowie tracks…how? But rules are rules. Fortunately the toughest choice is taken away from me. The Beatles are not on Spotify, so they are ruled out on a technicality.

I have been road testing the list and there have been some surprises. The middle child has developed a strong interest in The Beach Boys, particularly God Only Knows (and that’s not just because of the BBC version), while the eldest has expressed a visceral dislike for James Brown. I did expect some bumps in the road of this musical journey: after all the boys refuse to let me play Nick Drake in the car (maybe one day they will learn they are wrong). Still, I am now getting requests for Hit the North, so something must be working.

This musical education is a work in progress, so I need help from all of you. Are there any big names I have missed? Let me know in the comments. Not all of the lists in the list are my own favourites, so I may have missed an essential track. Comments are open below, so please jump in!

 

{ 76 comments }

Sleeping Beauty – a “halfer” approach

29 September 2014

If you read the last post on the Sleeping Beauty problem, you may recall I did not pledge allegiance to either the “halfer” or the “thirder” camp, because I was still thinking my position through. More than a month later, I still can’t say I am satisfied. Mathematically, the thirder position seems to be the […]

56 comments Read the full article →

Sleeping Beauty

26 August 2014

For the last couple of weeks, I have fallen asleep thinking about Sleeping Beauty. Not the heroine of the Charles Perrault fairy tale, or her Disney descendant, but the subject of a thought experiment first described in print by philosopher Adam Elga as follows: Some researchers are going to put you to sleep. During the two days […]

28 comments Read the full article →

Getting Australia Post out of the red

19 June 2014

John Carmody returns to the Mule in his promised second guest post and takes a close look at Australia Post’s profitability with some (ahem) back-of-the-envelope calculations. There are many forms of communication which underpin the function and productivity of a modern society like Australia. Despite the Cassandra-commentary from Mr Ahmed Fahour (the well-paid CEO of Australia Post), regular mail […]

1 comment Read the full article →

The government’s medical fairyland

14 June 2014

For the first time in a while, John Carmody returns to the Stubborn Mule with the first of two guest posts. He argues that the government’s proposed medical “co-payments” do not add up. The government continues to flounder about many details of its budget and part of the reason is a lack of stated clarity […]

2 comments Read the full article →

Government spending

20 May 2014

Before, during and after this month’s budget, Treasurer Joe Hockey sounded dire warnings about Australia’s “budget emergency”. Amidst this fear-mongering, it was a pleasant relief to come across a dissenting view. In a recent interview on 2SER Dr Stephanie Kelton (Department of Economics at the University of Missouri in Kansas City) argued that the government budget is very […]

16 comments Read the full article →

Randomness revisited (mathsy)

21 April 2014

My recent randomness post hinged on people’s expectations of how long a run of heads or tails you can expect to see in a series of coin tosses. In the post, I suggested that people tend to underestimate the length of runs, but what does the fox maths say? The exploration of the numbers in this post draws on […]

2 comments Read the full article →

Do Daleks use toilet paper?

18 April 2014

I have been watching some (very) old Doctor Who episodes, including the first ever serial featuring the archetypal villains, the Daleks. In this story, the Daleks share a planet with their long-time enemies, the Thal. After a war culminating in the denotation of a neutron bomb, both races experience very different mutations. The Daleks have […]

6 comments Read the full article →

Randomness

6 April 2014

With three children, I have my own laboratory at home for performing psychological experiments. Before anyone calls social services, there is an ethical committee standing by (their mother). This evening, I tried out one of my favourites: testing the perception of randomness. Here is the setup: I gave the boys two pieces of paper and […]

4 comments Read the full article →