Archive for the ‘ Mathematics ’ Category

Choosing data structures

I decided earlier in the week that I wanted to write an implementation of a general Markov chain in C; this is not particularly hard, but it does raise some interesting questions along the way—in particular, about data structures. A Markov chain really consists of two nested data structures: the set of the nodes in the list, and the set of outbound edges from each node; these structures serve vastly different purposes, as the order in which the nodes in the Markov chain are accessed depends on how edges are selected, but edges need to be sorted in a standard order so as to match how a Markov process functions. Accordingly, I found myself basing my decision on a few criteria:

Markov nodes:

  • Order of access not absolutely required to be stable
  • Key most likely in a totally ordered set
  • Minimizing access time a handy thought

Edge nodes:

  • Order of access paramount. Needs to remain stable.
  • Edges absolutely in a totally ordered set
  • Access time less important than order.

Based on these criteria, I arrived at two vastly different structures. For the Markov nodes, that “minimizing access time” led directly to thinking about trees, and thinking about how motion through a Markov chain happens led to considering a splay tree. A splay tree, if you’re unaware, is a binary search tree which has only one operation: splay. When you splay the tree, you modify its structure, bringing the node you are looking for (or the closest match) to the root of the tree. This has the handy property of keeping all the most frequently used nodes right in the top few levels of the tree, and still maintains an amortized O(log(n))—even with the slight probability that repeated splay operations will lead to it becoming a linked list.

To the contrary, the data structure I selected for the edges is a linked list, sorted from largest key to smallest key; in this case, I required that the structure remain stable, and furthermore that it have a particular order, with every node in a known position with regards to its value. Although search is an O(n) operation, it is doubtful a graph will have so many connections as to make that prohibitive, while at the same time maintaining a safe, regular, easy to traverse structure when running find_next_state().

By the by, the current code can be found in my Bitbucket repository, in markov.c and markov.h, respectively. They’re currently under rapid development and are nowhere near release-ready; I’m expecting the API to change significantly over the next few days.

It’s all a puzzle.

Mathematics and I have a curious relationship.

I’m a very audiovisual-oriented thinker. If I can truly visualise a problem, I can solve it. This is where physics and I have problems, because there are too many specialised methods, and visualisation can break down fairly easily. On the other hand, equations arrange themselves in my mind, graphs plot in my head, and all of this just fits.

That’s not to say math is easy. Quite the contrary; as I’m writing this in my notebook, I’m avoiding working on my homework, so I can develop some peace of mind before taking up the project again. No, what happens is exhaustion — mental exhaustion and unfamiliar concepts forming a vile brew that corrupts everything I’m working on.

So I go away, leave it behind, do something else, calm down, break the pieces up and set them aside in my mind, where they fade out and leave only a few pure concepts to be explored once I have some time to really look and see what I need. My physics professor last semester said it well: « Go home, drink a beer, relax for a while, and then try it again. »

Now, he was talking about the midterm exam, which I was going to do horribly on because for whatever reason, physics is no longer the area where I have strong analytic skills. (Just as an aside, I do miss physics, but I think Mathematics is a more sure route to my interests, and my enjoyment.)

I look at this state of « blockedness » as a symptom of too much work; really, there is such a thing. After classes, the last thing I needed to do was start working immediately. Unfortunately, today, I did that, and I set back my homework by at least an hour, if not more.

Editorial post-script: I got back to the rez and promptly solved the two remaining problems in about an hour, tops. This is being typed and posted a few weeks later, because I’m a lazy bastard.

It’s just a change of variables

So . . . sometimes a problem is very difficult to solve in one manner, so we look at it differently. All it takes is a change of variables, a different way of looking at the problem. Change the appearance, and you change the fundamental nature of solving the problem. It’s the same problem, it’s just gotten a lot easier. A lot of things in life just need the same method, looking at a problem through a different lens. If a particular situation is not susceptible to being broken down by one method of reasoning, change tacks and find a different angle to approach it. If you find you need to reëvaluate the situation later on, do it! Don’t allow your values to be fixed in a single manner, that is the death of creativity. Rigid values analysis breaks down with an application of a change of variables, and suddenly the reason for fluidity in values is apparent: adjusting to a shifting situation is difficult with a rigid values analysis – if you hold one dogmatic belief above all other reason, when something comes along that may require breaking that dogma, someone bound in a rigid value structure may not be able to adapt, while someone who allows adjustment is more capable of finding a solution outside their previous values analysis. This rigid values analysis can be seen especially in those who are strongly religious and gay, in religions which are disapproving of homosexuality (disapproving may be too light a word, in some cases.) They either need to be able to accept that not everything in their lives fits with what they have been told, or they will surely perish, or face what they consider their absolute doom. However, if you accept a little change of variables, suddenly that life-or-death dichotomy breaks down, and a clearer solution is evident.

It’s just a change of variables.

A blank slate

Today, I don’t have any specific thoughts for my blog. This is the empty space, the total void. On the one hand, I have nothing. On the other hand, this is where inspiration strikes.

I suppose I can talk about the null space.

The null space is a mathematical concept that is related to homogeneous linear equations in multiple variables; most specifically, a system of these equations. Now, a homogeneous equation is a linear equation of the form A _ 1 X _ 1 + A _ 2 X _ 2 + \cdots + A _ n X _ n = 0. For each linear equation A _ 1 X _ 1 + A _ 2 X _ 2 + \cdots + A _ n X _ n = B, there is an associated homogeneous equation, where B = 0. So, the null space is the solution to a system of these homogeneous equations; it is a set of values for X _ 1 , X _ 2 , \cdots , X _ n either as actual values or as a system of equations itself, in cases where one term is removed completely. I suppose that statement made no sense.

I’ll update this later and maybe rewrite portions. In any event, welcome to the true work of linear algebra.