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 ;)