I do. I think numbers are wonderful; because they provide one of the best frameworks for doing mathematics, an endeavour that is close to my heart*; because they themselves are the prototypical example of a purely imaginary construct which nevertheless models the world remarkably well; because they are rigid, structured, and ordered, but from them spring complexity of such dizzying and breath-taking scope that you cannot help but be awed by it.
Showing posts with label maths. Show all posts
Showing posts with label maths. Show all posts
Monday, 15 October 2012
Wednesday, 2 May 2012
A little more colouring-in
(This is a follow-up post to this one, where I introduced you to the wonderful world of Graph Theory)
Wednesday, 25 April 2012
Maths is just colouring-in, really!
Well, blog posts are just like buses, it seems - you wait ages for one, and then when they do come, they're a bit disappointing and rushed! Wait, no, hang on...
Today, I want to talk to you about some maths. Specifically, a branch called Graph Theory, which was the module that kept me sanest during my final year at Uni, primarily because it involved a lot of drawing pretty pictures (a fact which all my geographer friends were quick to take advantage of!).
In Graph Theory, a graph isn't something like this:
it's more like this:
A "graph" in graph theory terms is a collection of points (or "vertices") joined by lines (or "edges"). Graph theorists study various properties of graphs - the minimum number of edges that must be crossed to get between two vertices, the average number of edges meeting at vertices, and so on. Since these graphs can provide very good models for road layouts and computer networks, you can see how the ability to concisely gather information about them could be useful - but, mostly, we just do it 'cos they're pretty (both mathematically and visually!)
I'm going to talk about something called a Ramsey number, and outline a simple but elegant proof. This is something where you can follow along at home, kids! Grab a pen and paper and meet me back here! Actually, better make that at least two pens (of different colours), though three would be even more helpful.
Got 'em? Good.
Right, first of all, draw yourself a hexagon - that's a six-sided regular shape, that looks like this:
(Do your best to make the corners sharply defined, rather than curves - it'll make your life easier later on.)
Congratulations, you've drawn your first graph! Technically, this called C6, (the C stands for "cyclic", since, as you can see, it resembles a circle in that you can go round in turn and return to your starting place) and there are various things that we could learn from examining it, but I have more a more interesting result in my sights.
Now join each vertex to every other vertex with a straight line. This should end up looking like this (where the vertices have been highlighted in blue):
What you have drawn is called the "complete graph on 6 vertices", or K6 for short. For any number n, Kn is simply n vertices with each one joined to every other. K1 is just a single vertex, K2 is a line joining two vertices, K3 is a triangle, K4 is a square with the diagonals filled in, and so on, as shown below:
Now, to introduce the Ramsey numbers, I first have to introduce the notion of graph colouring. This is just as it sounds - a colouration of a graph is a drawing of it where all of the edges have a particular colour. So, for instance, this is a colouring in red, blue, and green, on an (incomplete) graph of 20 vertices;
and this is a colouring in 7 colours (we would say a "7-colouring") of K8
(Note that it doesn't matter that the vertices of this graph aren't arranged around the points of an octagon - graph theory only cares about the connectedness (or unconnectedness) of points, not their relative positions. K3 is still K3 whether it's represented as a small scalene triangle, or an equilateral triangle the size of the galaxy)
Now (and don't worry, I'll come back and explain this later), we define the Ramsey number R(m) as being the smallest number n such that, for any 2-colouring of Km, there will always be a monochromatic Kn.
Phew...what on earth does that mean! Well, let's start off with a simple example. Let's try to find R(2) - that is, the smallest number n such that, if we link up all n vertices with either red or blue lines, we'll either have a red K2 or we'll have a blue K2. Well, since K2 is just a single edge, if there's more than one vertex in our graph, there's bound to be either a red or a blue K2, otherwise we haven't coloured it all - but if there's only one vertex in our graph, there are no edges (nothing to link to!), so no K2. So R(2) is 2.
Let's get a bit more adventurous. What's R(3)? Well, it's clearly bigger than 3 - as long as you don't use the same colour to draw all three sides of the triangle, you won't end up with a monochromatic triangle in your colouration. Similarly, we can 2-colour K4 (remember, a square with the diagonals drawn in) without making a mono-K3 - for instance, draw the outside square in red and the diagonals in blue.
This post is dragging on a little, so I'll set you a question to ponder and give the answer (and proof) in the next post - what is R(3)? If you think you know it, try to consider how you'd prove it - how can you prove, for instance, that there isn't a satisfactory 2-colouring on a smaller complete graph? I'll warn you now, while sketching out some ideas will help, trying to prove a result by exhausting all possible colourations will take you a while - there are, for instance, 378 possible colourations of K8* , so you'll be there for a while! I'll give the solution and proof next time.
* - where xCy is the choose function, there are 8C2 = 28 edges (for each of the eight vertices, there is precisely one edge for every way of choosing two of them), and so, since there is one colouration for every way of choosing a colour for each of these, there are 28C2 = 378 colourations. For mathematicians - yes, I'm aware that I've double-counted isomorphic colourations, but if you're seeking a solution by brute force exhaustion like this, it's appropriate to warn of an appropriate upper bound!
EDIT: I tried to get a definitive answer on the number of 2-colourings of K8 by using Wolfram Alpha, a "computational knowledge engine". The results were...less than satisfactory:
Today, I want to talk to you about some maths. Specifically, a branch called Graph Theory, which was the module that kept me sanest during my final year at Uni, primarily because it involved a lot of drawing pretty pictures (a fact which all my geographer friends were quick to take advantage of!).
In Graph Theory, a graph isn't something like this:
it's more like this:
I'm going to talk about something called a Ramsey number, and outline a simple but elegant proof. This is something where you can follow along at home, kids! Grab a pen and paper and meet me back here! Actually, better make that at least two pens (of different colours), though three would be even more helpful.
Got 'em? Good.
Right, first of all, draw yourself a hexagon - that's a six-sided regular shape, that looks like this:
Congratulations, you've drawn your first graph! Technically, this called C6, (the C stands for "cyclic", since, as you can see, it resembles a circle in that you can go round in turn and return to your starting place) and there are various things that we could learn from examining it, but I have more a more interesting result in my sights.
Now join each vertex to every other vertex with a straight line. This should end up looking like this (where the vertices have been highlighted in blue):
What you have drawn is called the "complete graph on 6 vertices", or K6 for short. For any number n, Kn is simply n vertices with each one joined to every other. K1 is just a single vertex, K2 is a line joining two vertices, K3 is a triangle, K4 is a square with the diagonals filled in, and so on, as shown below:
(Note that it doesn't matter that the vertices of this graph aren't arranged around the points of an octagon - graph theory only cares about the connectedness (or unconnectedness) of points, not their relative positions. K3 is still K3 whether it's represented as a small scalene triangle, or an equilateral triangle the size of the galaxy)
Now (and don't worry, I'll come back and explain this later), we define the Ramsey number R(m) as being the smallest number n such that, for any 2-colouring of Km, there will always be a monochromatic Kn.
Phew...what on earth does that mean! Well, let's start off with a simple example. Let's try to find R(2) - that is, the smallest number n such that, if we link up all n vertices with either red or blue lines, we'll either have a red K2 or we'll have a blue K2. Well, since K2 is just a single edge, if there's more than one vertex in our graph, there's bound to be either a red or a blue K2, otherwise we haven't coloured it all - but if there's only one vertex in our graph, there are no edges (nothing to link to!), so no K2. So R(2) is 2.
Let's get a bit more adventurous. What's R(3)? Well, it's clearly bigger than 3 - as long as you don't use the same colour to draw all three sides of the triangle, you won't end up with a monochromatic triangle in your colouration. Similarly, we can 2-colour K4 (remember, a square with the diagonals drawn in) without making a mono-K3 - for instance, draw the outside square in red and the diagonals in blue.
This post is dragging on a little, so I'll set you a question to ponder and give the answer (and proof) in the next post - what is R(3)? If you think you know it, try to consider how you'd prove it - how can you prove, for instance, that there isn't a satisfactory 2-colouring on a smaller complete graph? I'll warn you now, while sketching out some ideas will help, trying to prove a result by exhausting all possible colourations will take you a while - there are, for instance, 378 possible colourations of K8
* - where xCy is the choose function, there are 8C2 = 28 edges (for each of the eight vertices, there is precisely one edge for every way of choosing two of them), and so, since there is one colouration for every way of choosing a colour for each of these, there are 28C2 = 378 colourations. For mathematicians - yes, I'm aware that I've double-counted isomorphic colourations, but if you're seeking a solution by brute force exhaustion like this, it's appropriate to warn of an appropriate upper bound!
EDIT: I tried to get a definitive answer on the number of 2-colourings of K8 by using Wolfram Alpha, a "computational knowledge engine". The results were...less than satisfactory:
Saturday, 3 March 2012
Pilindrome
[Warning: this blog post contains mathematical notation. Continue at your own risk]
[edit: It's by no means clear that the A(i) are mutually exclusive, which renders this proof dodgy - though you can consider the events B(i), that the sequence up to i is a palindrome but contains no shorter palindromes, which are mutually exclusive, and have (I believe) the same probability, yielding the same result]
I recently rediscovered the truly excellent Abstruse Goose, a webcomic in the same vein as XKCD - reflections on a life more nerdy. Their (currently) latest comic piqued my interest - of course, π isn't a palindrome, since it's endless, but there are related questions that are intriguing.
I was particularly interested in determining whether π could be definitively stated to contain a palindromic elision - that is, some point at which, if you chopped it off there, the first digits of π (without decimal point) would read 314159265...562951413. A quick google turned up the following question, involving a reply from someone who clearly knows more about the relevant areas of maths than I do - I never took measure theory, and number theory and probability weren't my strong points. Still, I thought there would still be something interesting that I could tinker about with.
Since the question of π's normality[1] is apparently both important to the question, and an unsettled matter, I thought I'd transfer the question to a random sequence, since they're a bit more well-behaved. Note that below I'm investigating the question of whether truncating this sequence at some point will generate a palindrome, rather than the somewhat-looser question of whether the sequence will contain a palindrome at some point[2].
However, the "answer" that I got out doesn't seem intuitively right (for one thing, I was expecting a series that converged to 1), so I'm by no means staking my mathematical reputation on this - if anyone with a better grasp on the mathematics spots an error, please, by all means point it out!
Since this blog is meant to be accessible to non-nerds, I've done my best to provide a line-by-line commentary below so those without a mathematical education can follow along.
(Note that I'm not counting single digits as palindromes here, because that's a) silly and b) boring)
1. Let xi be an infinite random sequence, xi ∈ [9] ∀i
2. Let a finite sequence y1, y2, ... yn-1, yn, be called palindromic if yi = yn-i ∀i
3. We seek the probability that ∃n s.t. xi≤n is palindromic
4. Let A(n) be the event that x1, x2, ..., xn-1, xn is palindromic. Then we seek ℙ[j=2U∞ A(j)]
5. ℙ[A(j)] = 10 -floor(j/2)
6. ℙ[j=2U∞ A(j)] = j=2Σ∞10 -floor(j/2) = 2 j=1Σ∞10 -j
∴ Probability sought is 0.2̇
Apologies for the horrible horrible formatting - I haven't yet found a way to write LaTeX or similar on blogger, if anyone knows of one, please let me know!
Right, walkthrough time:
1. The subscript "i" is the index of the sequence. For instance, x1 would be the 1st number in the sequence, x52 the 52nd, and so on. [n] is a shorthand notation for "the set of numbers less than or equal to that number" - so [9] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. The symbol ∀ means "for all" - so this statement is saying "whichever number you choose for i, xi will be a whole number between 0 and 9 inclusive"
2. This is defining what we mean by "palindromic" in terms of mathematical notation.
3. That symbol ∃ means "there exists" - i.e., we are looking for the probability that there is a number n such that, if we chop off the sequence at the nth number, it will form a palindrome.
4. The double-struck P (this font is sometimes called "Blackboard Bold") stands for "probability". The "U" symbol stands for "Union" (essentially, "combining" various events), and the sub- and super-script means that we are taking the union from j=2 to infinity. That is, we are looking for the probability that any truncation of the sequence (of length two or more) will be a palindrome.
5. This is stating the probability of the truncation at the nth digit being a palindrome. "floor" is a function that gives the smallest whole number less than or equal to the argument - so floor(2.5) is 2, but floor(3) is 3. The explanation for this probability is as follows; in order for a sequence to be a palindrome, we need the second half of the numbers (rounded down) to match the first half. The probability of any one number matching its partner is 1/10 (as there are 10 digits to choose from), so the probability of all of them matching is (1/10)floor(j/2) - and since (1/10) can be represented as 10-1, this gives the probability given above.
6. Putting a bar over a symbol or expression in maths is a common way of expressing "not/negation". In this case, since A(n) is the probability of the n-truncated sequence being a palindrome, A(n) is the probability of it not being a palindrome. If p is the probability of an event happening, then 1-p is the probability of that event not happening.
7. The spikey-E shape on the right-hand side here is called "Sigma". It represents repeated addition - in this case, "add up all values of 10 -floor(j/2) from j=2 upwards". We can do this because the probabilites of A(n) are mutually exclusive - that is, the probability of either one of them occurring is the addition of both of their probabilities. Since floor(2n/2) = floor(2n+1/2), this is equal to twice the addition with the floor and division-by-two removed.
The dot over the 2 means "repeating" - that is, the probability is 0.22222...
So, in summary, the maths above, in which I can't find a problem, gives us a 0.2222... probability of any given random sequence of numbers having a palindromic. In hindsight, and having benefitted from the added insight afforded by having to explain my working, I'm less uncomfortable with this answer than I was before - an answer of 0 would have been non-sensical, as clearly some random sequences exist with a palindromic truncation, but so would 1 as there "do" exist infinite sequences not containing palindromes. In fact, the construction of palindromes is quite artificial, so you would expect them to be reasonably rare. 0.222... therefore seems a sensible value for this probability.
It's amazing how quickly I've lost my fluency with maths, and especially probability - I could still remember all the pertinent details and get it done, but with none of the fluidity that I used to have! Definitely need to keep my brain in gear somehow...the iTunes U courses that have been recommended might be a good idea!
Anyway, I hope you've enjoyed this jaunt through maths...I'm at home right now, and our dinner guest has just appeared, so I must away!
[1] A "normal" number is one in which every possible digit (from 0 to 9, in the decimal system) occurs with the same density (i.e. has the same "chance" of occurring), every pair of digits has an equal density, every triple has an equal density, every string of four digits has an equal density, and so on. Confusingly, the vast majority of numbers that we encounter outside of a maths degree are not normal, because they are either integers ("whole numbers"), or terminating decimals (e.g. 5.324, as opposed to a non-terminating decimal like 7.3333333...). A little thought will show that neither of these can be normal, since they only have a finite number of digits to play with, and so they could not fulfil all of the conditions - trivially, it cannot be true that an integer with n digits contains all (n-1)-length digit strings with equal density, because there is only room for two such strings.
[2] Indeed, this is certain to happen in an infinite random sequence. Consider the fact that dd is a palindrome for any digit d. Then we seek the probability that the sequence contains any dd. The probability that any digit pair is any dd is 1/10 (the first digit can be chosen freely, and there is a one in ten chance that the next digit matches), so the probability they do not match is thus 9/10. The probability that not a single pair of digits in the sequence match is (9/10)*(9/10)*(9/10)*..., which tends to 0. So the probability that the sequence contains a matching pair (which are a palindrome) is 1.
[edit: It's by no means clear that the A(i) are mutually exclusive, which renders this proof dodgy - though you can consider the events B(i), that the sequence up to i is a palindrome but contains no shorter palindromes, which are mutually exclusive, and have (I believe) the same probability, yielding the same result]
I recently rediscovered the truly excellent Abstruse Goose, a webcomic in the same vein as XKCD - reflections on a life more nerdy. Their (currently) latest comic piqued my interest - of course, π isn't a palindrome, since it's endless, but there are related questions that are intriguing.
I was particularly interested in determining whether π could be definitively stated to contain a palindromic elision - that is, some point at which, if you chopped it off there, the first digits of π (without decimal point) would read 314159265...562951413. A quick google turned up the following question, involving a reply from someone who clearly knows more about the relevant areas of maths than I do - I never took measure theory, and number theory and probability weren't my strong points. Still, I thought there would still be something interesting that I could tinker about with.
Since the question of π's normality[1] is apparently both important to the question, and an unsettled matter, I thought I'd transfer the question to a random sequence, since they're a bit more well-behaved. Note that below I'm investigating the question of whether truncating this sequence at some point will generate a palindrome, rather than the somewhat-looser question of whether the sequence will contain a palindrome at some point[2].
However, the "answer" that I got out doesn't seem intuitively right (for one thing, I was expecting a series that converged to 1), so I'm by no means staking my mathematical reputation on this - if anyone with a better grasp on the mathematics spots an error, please, by all means point it out!
Since this blog is meant to be accessible to non-nerds, I've done my best to provide a line-by-line commentary below so those without a mathematical education can follow along.
(Note that I'm not counting single digits as palindromes here, because that's a) silly and b) boring)
1. Let xi be an infinite random sequence, xi ∈ [9] ∀i
2. Let a finite sequence y1, y2, ... yn-1, yn, be called palindromic if yi = yn-i ∀i
3. We seek the probability that ∃n s.t. xi≤n is palindromic
4. Let A(n) be the event that x1, x2, ..., xn-1, xn is palindromic. Then we seek ℙ[j=2U∞ A(j)]
5. ℙ[A(j)] = 10 -floor(j/2)
6. ℙ[j=2U∞ A(j)] = j=2Σ∞10 -floor(j/2) = 2 j=1Σ∞10 -j
∴ Probability sought is 0.2̇
Apologies for the horrible horrible formatting - I haven't yet found a way to write LaTeX or similar on blogger, if anyone knows of one, please let me know!
Right, walkthrough time:
1. The subscript "i" is the index of the sequence. For instance, x1 would be the 1st number in the sequence, x52 the 52nd, and so on. [n] is a shorthand notation for "the set of numbers less than or equal to that number" - so [9] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. The symbol ∀ means "for all" - so this statement is saying "whichever number you choose for i, xi will be a whole number between 0 and 9 inclusive"
2. This is defining what we mean by "palindromic" in terms of mathematical notation.
3. That symbol ∃ means "there exists" - i.e., we are looking for the probability that there is a number n such that, if we chop off the sequence at the nth number, it will form a palindrome.
4. The double-struck P (this font is sometimes called "Blackboard Bold") stands for "probability". The "U" symbol stands for "Union" (essentially, "combining" various events), and the sub- and super-script means that we are taking the union from j=2 to infinity. That is, we are looking for the probability that any truncation of the sequence (of length two or more) will be a palindrome.
5. This is stating the probability of the truncation at the nth digit being a palindrome. "floor" is a function that gives the smallest whole number less than or equal to the argument - so floor(2.5) is 2, but floor(3) is 3. The explanation for this probability is as follows; in order for a sequence to be a palindrome, we need the second half of the numbers (rounded down) to match the first half. The probability of any one number matching its partner is 1/10 (as there are 10 digits to choose from), so the probability of all of them matching is (1/10)floor(j/2) - and since (1/10) can be represented as 10-1, this gives the probability given above.
6. Putting a bar over a symbol or expression in maths is a common way of expressing "not/negation". In this case, since A(n) is the probability of the n-truncated sequence being a palindrome, A(n) is the probability of it not being a palindrome. If p is the probability of an event happening, then 1-p is the probability of that event not happening.
7. The spikey-E shape on the right-hand side here is called "Sigma". It represents repeated addition - in this case, "add up all values of 10 -floor(j/2) from j=2 upwards". We can do this because the probabilites of A(n) are mutually exclusive - that is, the probability of either one of them occurring is the addition of both of their probabilities. Since floor(2n/2) = floor(2n+1/2), this is equal to twice the addition with the floor and division-by-two removed.
The dot over the 2 means "repeating" - that is, the probability is 0.22222...
So, in summary, the maths above, in which I can't find a problem, gives us a 0.2222... probability of any given random sequence of numbers having a palindromic. In hindsight, and having benefitted from the added insight afforded by having to explain my working, I'm less uncomfortable with this answer than I was before - an answer of 0 would have been non-sensical, as clearly some random sequences exist with a palindromic truncation, but so would 1 as there "do" exist infinite sequences not containing palindromes. In fact, the construction of palindromes is quite artificial, so you would expect them to be reasonably rare. 0.222... therefore seems a sensible value for this probability.
It's amazing how quickly I've lost my fluency with maths, and especially probability - I could still remember all the pertinent details and get it done, but with none of the fluidity that I used to have! Definitely need to keep my brain in gear somehow...the iTunes U courses that have been recommended might be a good idea!
Anyway, I hope you've enjoyed this jaunt through maths...I'm at home right now, and our dinner guest has just appeared, so I must away!
[1] A "normal" number is one in which every possible digit (from 0 to 9, in the decimal system) occurs with the same density (i.e. has the same "chance" of occurring), every pair of digits has an equal density, every triple has an equal density, every string of four digits has an equal density, and so on. Confusingly, the vast majority of numbers that we encounter outside of a maths degree are not normal, because they are either integers ("whole numbers"), or terminating decimals (e.g. 5.324, as opposed to a non-terminating decimal like 7.3333333...). A little thought will show that neither of these can be normal, since they only have a finite number of digits to play with, and so they could not fulfil all of the conditions - trivially, it cannot be true that an integer with n digits contains all (n-1)-length digit strings with equal density, because there is only room for two such strings.
[2] Indeed, this is certain to happen in an infinite random sequence. Consider the fact that dd is a palindrome for any digit d. Then we seek the probability that the sequence contains any dd. The probability that any digit pair is any dd is 1/10 (the first digit can be chosen freely, and there is a one in ten chance that the next digit matches), so the probability they do not match is thus 9/10. The probability that not a single pair of digits in the sequence match is (9/10)*(9/10)*(9/10)*..., which tends to 0. So the probability that the sequence contains a matching pair (which are a palindrome) is 1.
Subscribe to:
Posts (Atom)