Adventures in Mathematics

Currently, I am taking CPSC 302 at UBC which is Numerical Approximations in Linear Algebra.

So far, the course has taught me about round-off and convergence errors as well as machine eta and the floating point representation. Next, we covered methods for solving f(x) = 0 such as the bisection method (using the Intermediate Value Theorem) as well as Newton's Method and the Secant Method. The assignment had us modifying the Newton's Method to become more robust, that is, if the solution did not improve by more than 0.5, we would switch over to the bisection method to obtain a tighter bound on the root and use the Newton's Method with the new bounds.

What I want to talk about today is that during our lesson in matrices (the 3rd section of the course), we were talking about permutations and what they were useful for. One thing that is good about a permutation is for the stability of an algorithm, say the Gauss Elimination algorithm. We started to talk about how permutations are not only good for stability of algorithms, but also for reducing the number of operations needed to reduce a matrix into a lower triangular form so that we can apply backward substitution to the matrix. The example given in class was










and our permuted matrix was







What we did first was we analyzed the sparsity of the L matrix of the LU decomposition of this matrix. What we saw was that L was an upper triangular matrix with the lower half all non-zeros (in general). However, looking at the permuted matrix, the L matrix would only have the 3 entries located in the 4th row. Given that the L matrix of the permuted matrix had less non-zero elements, the work needed to reduce the matrix into lower triangular form would be less than the work needed to reduce the un-permuted matrix.

Then, our prof showed us something just mind-blowing. He showed that the matrix can be represented in graph form. So, for example

For the first matrix,

















And for the permuted matrix,











What these two graphs are saying is that there are elements (1,3), (1,2), (1,4) , (3,1) , (2,1), (4,1) in the un-permuted matrix. And for the permuted matrix, it is saying the same thing, only for different elements (3,4), (4,1), etc. Following the Gaussian Elimination for our first matrix, we see that we are trying to eliminate, in a sense, the connection between node 1 and node 2 (ie. in the first matrix, we are trying to get rid of the 5). But doing the row operation will fill the rest of row 2 and we destroy the zeros that we had in the row. In a sense, using Gaussian Elimination on the first column will fill the matrix so that it no longer has any zeros in the lower half. If we were to look at that in terms of the graph, we are building more connections between the nodes (and thus, more work is needed to eliminate those connections).

However, when we look at the permuted matrix, again, we use row operations following the Gaussian Elimination algorithm but instead of filling our matrix, we don't. Our row operations never turn any zero element into a non-zero element - all the non-zero elements are changing, but since they were non-zero anyway, this doesn't change our graph. What this means is that no new connections are being built as we are applying row operations to the permuted matrix (aka we are not increasing the amount of work needed to change the permuted matrix into a lower triangular matrix).

It's amazing what applications of mathematics can overlap to provide us with different and interesting perspectives.

Games Night - Oct. 5 2007

Last night was our first (but certainly not last) official game night. Normally we play board games after dinner or kayaking or what not but last night was just all about the board games. Linda and I co-hosted the event and I am definitely looking forward to having another games night some time in the near future with more people and different board games.

Things started with us waiting for Kevin and his friend Ken to come by and during that time we were watching a special edition of Deal or No Deal. Given my previous post on Deal or No Deal, there is a great deal of mathematics behind the game and behind your decisions on continuing or leaving. Deal or No Deal had a special version of its game going on and this special game added a million dollar briefcase for every contestant that did not win the million dollars. For example, the first contestant would have 1 one million dollar briefcase and if he/she did not win, the second contestant would have 2 one million dollar briefcases and so on. The episode that we watched was in the middle of the 5th contestant and funnily, it went down to the last 3 briefcases and she accepted the banker's offer of 300,000 at that point. After the briefcases were open though, it turned out that she had chosen a million dollar briefcase and if she had gone on, she would have won the million dollars. We then proceeded to watch the 6th contestant go down to 3 briefcases and again, accept the banker's offer of about 300,000.

I realized that at some point, if the contestants continued to not get one million dollars, the number of briefcases would be saturated with one million dollars and strangely, after eliminating 6 briefcases in the beginning, it would probably be in your best interest to accept the banker's offer. For example:

There are 26 cases and suppose we have 25 cases with one million dollars and the 26th case has one cent (which in our calculations will basically be negligible)

We assume for simplicity that in our choices for the briefcase, we do not choose the penny briefcase. If we do choose the penny briefcase, the banker can't offer anything less than one million dollars (or he can, but we just wouldn't accept the offer since we know with 100% certainty that we should just keep going on and get the last briefcase with our one million dollars in it)

So after choosing 6 briefcases in the beginning, our expected value is:

19 x (1,000,000) + 0.01 ~= 19,000,000

19,000,000 / 20 = 950,000.

The banker will then put out an offer. Since there is such a high chance that we chose a million dollar briefcase in the beginning, he should offer us something between 950,000 and 1,000,000. It is in his best interest to end the game so that we do not win the one million dollars in the end. If he can do this by offering money > expected value than he should and in essence, he would be cutting his losses (albeit a small amount for this one game). Often though, the banker wishes to prolong the game to cut our hourly wins (100,000 in one hour is less than 50,000 in 15 minutes) and he may offer us less money so that we continue on with the game.

Again, assuming we do not choose the penny briefcase, our expected value after choosing another 5 briefcases is:

14x(1,000,000) + 0.01 ~= 14,000,000.

14,000,000 / 15 = 933,333.

This has dropped 17,000 from our previous expected value. Strangely, continuing on in the game has cut our expected value.

I would really love to figure out how to calculate at what point the board would be 'saturated' but it seems like a calculating that I'm not sure I have time for now. Intuitively it would seem that after half the board is filled with million dollar briefcases then the briefcases we eliminate would have a > 50% probability of being the million dollars and we would get decreasing banker offers then.


Anyway, back to the Games Night :)

We started off the night with Cranium. It is an excellent game for those days that you feel like using your brain. If you haven't played the game before, it's a board game where you move your pieces and answer different questions, solve word puzzles, draw or sculpt to get an idea across or even act out a character or sing a song.

Some of the highlights of the game were:

- An axing motion interpreted as a golfing maneuver - "It HAS to be golf" even though the person doing the axing motion seemed like she was swinging a bat waist high rather than swinging a golf club hehe

- Blind drawings where both players often forgot to close their eyes while drawing

- A sculpture of a plunger that was very symbolic of something...

- Three guys getting a word puzzle. The hint for the puzzle was "A mom's break" and the answer of the anagram was Maternity Leave. Needless to say, the three guys did not get the answer.

- Word puzzles where nobody knew the definitions of strange words:
bailiwick, tmesis, (a vocab which meant a puck made out of frozen horse dung )


We also played Settlers of Catan. In brief, this game is a lot like risk but there are many notable differences. Each 'settler' team has settlements. Depending on the dice and where your settlements are on the game board, you gather resources which you can use to build roads, settlements, cities (upgraded settlements), or purchase discovery cards (which can add a lot of depth to the game such as giving victory points to the team, having a monopoly on a certain resource or gaining extra resources on its use). The board game also has a neutral robber piece that is moved every time a 7 is rolled.

The beginning was a bit hectic for us because we were trying to learn the game. Luckily, I was paired up with someone that thought like me in terms of strategy and resource allocation / use. At first, it seemed like one team had gained a monopoly on one resource and at the same time they had an incredible amount of resources as the die really was in their favour. After a few expansions though, our team began building a ton of roads and expanding into new territory. It also helped that we rolled a 7 a few times which helped us control where the robber would be. Another property of the robber is that whatever resource the robber is on, nobody gets. So for example, if you get stone on a roll of a 6 and the robber was on the stone, settlements / cities that were near that stone would get the stone resource. This quickly turned into a great advantage for our team as we quickly gained an incredible amount of resources, expanded and had a monopoly on one resource in particular (the robber blocking the other place that the other settlers could gain the one resource at). It's definitely an interesting game and a lot of trading of resources goes on - you can see then why it would help that settlers have a monopoly over a resource.

All in all, a pretty fun night even if we never got to play Apples to Apples. Next time though ;)

A look at a hard Sudoku

So I thought it would be useful for people to learn how to do the wonderful and amazing sudoku in newspapers and stuff. Well, okay, so it isn't very useful, but at least you won't get stuck or have to guess any more.

A bit of a background on how I learned: I think one day I just saw this sudoku puzzle and I read the rules which are fiendishly simple. I then proceeded to logically think out where all the numbers should be. After a while, I used several different techniques (they all have names at this point and I even read about these 'advanced' techniques in order to get better not realizing that I was already using these techniques that I had come up with on my own)

Anyway, here's a step by step look at a hard sudoku found on websudoku.com.


So here is the start, it looks pretty normal for a sudoku doesn't it?

So to start off, I like to use what I think is called the 'hammer' method. Basically its looking at a single number and easily eliminating all the squares but one to have that number inside a square. It's just a very simple strategy to get numbers quickly - on the easy puzzles, you can solve the whole puzzle using this method, contrastingly, on the hard puzzles, you can only
get a few before you are stuck.











So here we are now with the hammer method completed (well I didn't really double check, but most of its there). Now that we're stuck, we have to rely on a bit of logic now to help us. As many sudoku puzzlers realize, after a certain point, all the numbers just fall into place and from there its extremely easy. Its about getting there one number at a time though so take it slow.










Now take a look at the circles. We can see from the rows, columns and squares that no 3 can be in any of the circles. So the 3 must be in the last available square in the left middle.













After filling in the 3, we can now take a look at the right middle square where the 6 8 9 2 are all circled. From all the circled numbers, we can see that only one number can go into the middle of the right middle square: 4.














Filling in more numbers (like the 3 in the right top square on top of the 6) helps us out even more. Again, we keep applying the hammer method to help us 'hammer' out more and more numbers. Each time we fill in a new number, we can go back to the hammer method to see if any new numbers are revealed.











If we look at the rectangled box, the row is missing a 1, 6 and 7. Immediately to the left of the 4 though, the 6 and 7 cannot possibly be located there because no number can repeat in the same box, row or column. So the 1 must be beside the 4.













Again more hammering out gives us the 1 in the top right corner. Now, lets take a look at the right top square and the row encased in the rectangle. We know from the square that we are missing a 5 and a 8 so in that row, the 5 and 8 (though we do not know which is which) cannot possibly be anywhere else and thus, we can fill in the 7.









Now because we have filled in so many numbers, the hammering starts to get easier and easier.
















And at this point, we have reached the point where everything now moves forward at a very rapid rate.















And finally you solved that hard one! Now you can do those hard ones in the newspapers.

Expected Value: Deal or No Deal

You must have seen this new game on t.v. Its called "Deal or No Deal" and its hosted by Howie Mandel. The premise of the game is simple and copied from http://en.wikipedia.org/wiki/Deal_or_No_Deal:

Deal or No Deal involves a contestant, a host/presenter, a banker, and a number of briefcases (or boxes), with each having a different (and initially unknown) value. Each game starts with the contestant selecting one of the cases—this first case's value is not known until the game ends. During the rest of the game, the contestant opens the rest of the cases, one at a time, revealing its value. Each time after a specified number of cases are opened, the banker offers the contestant a certain amount of money to end the game. If the contestant takes an offer, the game ends, otherwise the contestant ends up with the money from the first case.


The first time I watched the game, I realized that there was an amazing application of mathematics here in the form of expected value. Expected value comes up in many situations, especially in poker which I play sometimes in my spare time. I think that with the suspense of the briefcases and the fact that people can earn quite a bit of money through such a simple concept has made this game quite popular.

So, as the wikipedia entry says, the banker offers the contestant a certain amount of money to end the game. This can be illustrated as follows, though not the exact numbers.

Say the contestant has 4 briefcases left: $1, $2, $750,000, $100,000. Now, the banker usually offers the expected value or the probability of picking each briefcase X the value of the briefcase. To illustrate in a simpler example, if I flipped a coin and gave you $2 every time it came heads, the expected value would be: (0) x (0.5) + ( $2 ) (0.5) = $1. So you would expect to gain $1 every throw. This concept is more important in poker where these situations occur more frequently, but what isn't so intuitive is that every throw, even the throws where you didn't earn any money (the coin came up tails), you would win $1. In fact, even when the coin comes up heads, you actually win $1 and not the $2 you get.

A bit of a sidetrack, but when two people with 1000 chips each have KK and AA in no-limit holdem and get it allin preflop, AA expects to win about 80% of the time. This means that of the 2000 chips in the pot, AA wins 1600 chips every time it is up against KK. When KK goes up against AA, it wins 20% of the 2000 chips or 400 chips, every single time.

Back to Deal or No Deal now, we want to see what the expected value of the briefcases are at that point because we can compare this value to the value that the banker offers. If the banker offers more money, we should stop because by playing on, we do not expect to get more money. If the banker offers less money, we should (usually) go on, because we expect more money by playing on. So, with the 4 briefcases above, we can do a simple calculation to see what kind of money we expect if we choose a briefcase.

Basically, we want to choose the briefcases that hold either the $1 or $2. There is a 50% chance in choosing one of these briefcases. So, with the 4 briefcases above, we have an expected value of:

(1/4) x ($1) + (1/4) x ($2) + (1/4 ) x ($750,000) + (1 /4) x ( $1,000,000) = $437,500

We ignore the small $1 and $2 terms (and most of the time we can 'ignore' briefcases in our calculations like $1000 and $5000 compared to the larger $300,000 and $500,000 briefcases; we're really just interested in seeing how much expected value the larger briefcases give us)

So if at that moment, the banker offers us (and in the late stages of the game, he will sometimes offer more money than expected) $450,000 then the math tells us to accept the banker's offer. The offer is more than what we expect if we went on so we should stop right now. This is analogous to the choice of $3 every time I didn't flip a coin and $4 for every time I flipped a coin and it showed heads. Hopefully everyone would choose to get the$3 off of me because in the long run the expected value of this situation (100%) x ($3) > ( 50%) x ( $4) or 3 > 2. So back to the example, we have $450,000 compared to $437,500 and so we'd make more money in the long run. Of course, this in the long run. If millions of people got to this same situation, they would all make money by accepting the banker's offer of $450,000.

Of course, a lot of people when they get to that point want to keep going because they may be greedy, or have some sort of intuition that they chose the $1,000,000 briefcase in the beginning. I think this is what makes the game exciting - the thrill of gambling. But if you always make the right decision, you'll earn money. Think about it this way, if you decided to, even once, choose the coin flip for 4$ instead of getting the sure $3 every time, you would theoretically lose $1. It is possible that you do gain the extra dollar for winning that one time, but remember, when you take that coin flip, you expect $2. Since you don't play the game over and over though, you really just have this one shot at the money and maybe thats why people do gamble, because right now, they only have one chance at getting more money.

So if you're ever on Deal or No Deal, whats your expected value?

The Extreme Cases are Extremely Important

A few weeks ago, I finished a Phil 339 class at UBC. Phil 339 is the Philosophy of Arts, that is, what is the definition of art and what makes things in general art. For example, there is an intentional definition of art which states that art is anything that is intended to be art. If you think about it for a while though and as with any definition of art now in existence, there is an example where intuition does not seem to agree with the definition. For example, with this definition comes the fact that anybody can create art, not just artists as long as they have the right intention. A kid who draws a picture with crayons for their parents depicting their whole family has the right intention - he wants to make the art aesthetically pleasing so that he can please his parents with the drawing. If this is the intention, then that picture is art.

What I noticed, and this may be obvious, is that whenever we encountered new definitions of art, we would always look at the extreme cases as counterexamples. For instance, in this intentional definition of art - and the papers we wrote used these exact examples - there are several cases where the intentional definition of art seems to fail or is a bit muddled.

One example is in the case of Duchamp's Fountain or Warhol's Brillo Boxes. For those not familiar with either, Duchamp's Fountain is a urinal that was taken by Duchamp, signed R. Mutt and then placed on a pedestal in a museum. Warhol took a Brillo Box, which is just a cardboard box that is mass produced, and made it art. In both of these examples, it is the artist's intention to make these art, but it seems weird does it not? Anyone can take a urinal and have the intention to make it art and in a sense, recreate Duchamp's Fountain. Or take any object and make it art.

Another example is things like souping up cars or motorcycles. The owner intends for this car to be aesthetically pleasing, but this does not make the car art. It seems he has the right intention - he paints the car with care and adds-on different accessories all to make the car look good. Intuitively, this is not art, even though it has the right intention.

Since we always consider the extreme cases in this class, it started to get me thinking about other times where we use extreme cases to either prove or disprove something. Of course, the one example that came to my mind first was calculus and finding the maximum point. In order to find the maximum point, we need to take a look at where the curve has a derivative equal to zero AND we need to consider the boundary values (the extreme cases). If nowhere along the curve is the derivative zero, we take a look at the boundary values and find the maximum there.

It seems that we as humans are always interested in what happens at the very extreme end of things. Physicists first discovered black holes and the physics behind a black hole. They then wanted to figure out the boundary of the black hole or the event horizon. In physical terms, what was happening at the event horizon?

I was listening on the radio the other day about drug testing on animals. I agree that it is horrible, but then I thought about how many lives the research saves. Let's say that drug testing on animals is bad, in fact, absolutely terrible. What if a scientist had a vaccine for HIV say, and needed to test it on animals in order to make sure it worked. If there is no other alternative, what would you say? I'm not trying to say that animal testing is good or bad, but rather, these extreme cases really force you to take a side on an issue and even if you are strongly for or against that issue, it seems that there are very extreme examples which can make you jump sides.