A bunch of people, in a room

Partly in a bid to keep the interest of the small band of readers I appear to have gained since my last post, and partly out of sheer laziness, I am again going to dispense with serious mathematics this week, and instead discuss what interesting things can be said about: some people, in a room.

In his Guardian column last Saturday, after having unleashed the full extent of his fury at some poor unsuspecting tabloid for getting a statistic slightly wrong (don’t get me wrong, the media needs more people like him) Ben Goldacre mentions in passing that if there are at least 23 people in a room, the probability that 2 of them will have the same birthday is over 50%.  This is known as “the birthday paradox”, and while not technically being an actual paradox, it is highly counterintuitive, as probabilistic results often tend to be.  The counterintuitivity comes from the fact that people tend to assume the question is: “if I am in a room with some people, what is the probability of someone having the same birthday as me?” If there are 22 other people, then this gives only 22 possibilities.  But if we don’t specify the actual birth-date, the number of pairs of people, and hence the number of possible birthday-matches, becomes$23\choose 2$(the number of ways of choosing 2 things from 23 things), which is 253.  It is quite easy to believe that there is some likelihood of one of these pairs of people having the same birthday.

The reason that “the birthday paradox” has been given a name and a whole Wikipedia page (not that this is necessarily a sign of importance!) is because it has significance outside of the realm of mere speculation about people in a room.  For example, we could replace the people with randomly chosen integers, and consider the likelihood that an integer is chosen that is equal to one of the preceding ones.   In fact, the same theory used to solve the birthday problem is used in cryptography.  A “hash function” is a function which takes a block of data as an input, and returns a small – usually just one number – “hash value”.  It is appended to the block of data being transmitted, and used as a convenient way to check that the data has not been corrupted or tampered with in any way.

Now, clearly it is desirable for the function to be defined in such a way as to maximise the likelihood of the hash value changing if the data is modified in any way, and this means minimizing the probability that two different sets of data give the same hash key.  So, given a bunch of data-blocks, what is the probability that two of them will return the same hash key?  This is pretty much just the birthday question couched in different terms, and the hash function is optimized using exactly the same kind of probabilistic methods as those used to solve the birthday problem.  There is even a cryptographic attack known as the “birthday attack”, in which hackers/fraudsters/etc. set out to exploit the system by using the theory in reverse to find two sets of data which produce the same hash key.

The fact that seemingly trivial problems can have such far-reaching consequences goes some way to validating the idle speculation that mathematicians are so fond of.   An ability to analogize effectively is probably one of the most important tools for understanding mathematics; personally I often find that I need to think about a concept from various different perspectives before I find one way of viewing it that I truly understand and will remember.

Take the next following interesting nugget of information, which is called the Friendship Theorem (much nicer than birthday attack):

Given a group of people (who may or may not be in a room), if every pair of people has exctly one friend in common, then there must be one person who is a friend of everyone.

This is not necessarily counterintuitive, but it is certainly not obvious either.  Think about it…you have a party, and given any pair of people, there is one other person they both know.  Then there is definitely someone there who knows everyone (probably you).  Amazing!  And, as with the birthday paradox, this kind of statement can be very useful in a range of contexts.  In mathematics, the friendship theorem is usually given in terms of graph theory.  A graph in this sense is just a collection of dots (called vertices), with some of them connected to each other by lines (called edges).  It is one of the easiest mathematical objects to grasp, and is the natural abstraction of a huge range of situations involving things and the interactions between them.  A graph could represent an electrical circuit, an infrastructure system, a network of computers…the list is endless.  So the usual statement of the friendship theorem is:  given a graph in which any two vertices have a common neighbour, there is one vertex connected to all the rest.  We can specialise this to the above situation, by letting the vertices represent people, and by joining two vertices by an edge if those two people are friends.   But it is easy to see how statements like this about graphs can have a wide range of applications, both within pure mathematics, and in “the real world”.

Here is another theorem about people who may or may not be in a room together, this time called the “theorem on friends and strangers”:

In any group of 6 people, either at least 3 of them are mutual strangers (ie. none know any other), or at least 3 of them are mutual acquaintances (each knows every other).

This is not obvious at all, but the proof is so simple that I can write it down here in a few lines:

Suppose the 6 people are called: A, B, C, D, E, F.  Consider person A.  Either he knows at least 3 people, or he doesn’t know at least 3 people (think about it).  Suppose he knows 3 people, and let these people be B, C and D.  If any of these 3 people know each other, then these 2 – along with person A – are 3 people that all know each other.  If none of them know each other, then B, C, and D are 3 people who don’t know each other.    The same argument works the other way around (if we assume to start with that A doesn’t know 3 people), and so either way we have 3 mutual friends, or 3 mutual acquaintances.

I think that’s enough facts about people in a  room.  Unfortunately knowing them will probably not enhance your appreciation of being in a room with people, and in fact it is likely that talking about this sort of thing will make people leave the room.  There isn’t very much you can say about one person in a room, so I’d advise against it.

4 Responses to A bunch of people, in a room

1. Pedant strikes again:

in the Friendship theorem, you forgot to say that every pair of people have *exactly* one common friend…