Good Math, Bad Math

The End of Defining Chaos: Mixing it all together

Sun, 07 Feb 2010 19:35:49 -0500

The last major property of a chaotic system is topological mixing. You can think of mixing as being, in some sense, the opposite of the dense periodic orbits property. Intuitively, the dense orbits tell you that things that are arbitrarily close together for arbitrarily long periods of time can have vastly different behaviors. Mixing means that things that are arbitrarily far apart will eventually wind up looking nearly the same - if only for a little while.

Let's start with a formal definition.

As you can guess from the name, topological mixing is a property defined using topology. In topology, we generally define things in terms of open sets and neighborhoods. I don't want to go too deep into detail - but an open set captures the notion of a collection of points with a well-defined boundary that is not part of the set. So, for example, in a simple 2-dimensional euclidean space, the contents of a circle are one kind of open set; the boundary is the circle itself.

Now, imagine that you've got a dynamical system whose phase space is defined as a topological space. The system is defined by a recurrence relation: s_n+1 = f(s_n). Now, suppose that in this dynamical system, we can expand the state function so that it works as a continous map over sets. So if we have an open set of points A, then we can talk about the set of points that that open set will be mapped to by f. Speaking informally, we can say that if B=f(A), B is the space of points that could be mapped to by points in A.

The phase space is topologically mixing if, for any two open spaces A and B, there is some integer N such that f^N(A) ∩ B &neq; 0. That is, no matter where you start, no matter how far away you are from some other point, eventually, you'll wind up arbitrarily close to that other point. (Note: I originally left out the quantification of N.)

Now, let's put that together with the other basic properties of a chaotic system. In informal terms, what it means is:

Exactly where you start has a huge impact on where you'll end up.
No matter how close together two points are, no matter how long their trajectories are close together, at any time, they can suddenly go in completely different directions.
No matter how far apart two points are, no matter how long their trajectories stay far apart, eventually, they'll wind up in almost the same place.

All of this is a fancy and complicated way of saying that in a chaotic system, you never know what the heck is going to happen. No matter how long the system's behavior appears to be perfectly stable and predictable, there's absolutely no guarantee that the behavior is actually in a periodic orbit. It could, at any time, diverge into something totally unpredictable.

Anyway - I've spent more than enough time on the definition; I think I've pretty well driven this into the ground. But I hope that in doing so, I've gotten across the degree of unpredictability of a chaotic system. There's a reason that chaotic systems are considered to be a nightmare for numerical analysis of dynamical systems. It means that the most miniscule errors in any aspect of anything will produce drastic divergence.

So when you build a model of a chaotic system, you know that it's going to break down. No matter how careful you are, even if you had impossibly perfect measurements, just the nature of numerical computation - the limited precision and roundoff errors of numerical representations - mean that your model is going to break.

From here, I'm going to move from defining things to analyzing things. Chaotic systems are a nightmare for modeling. But there are ways of recognizing when a systems behavior is going to become chaotic. What I'm going to do next is look at how we can describe and analyze systems in order to recognize and predict when they'll become chaotic.

Read the comments on this post...

A Crank among Cranks: Debating John Gabriel

Thu, 04 Feb 2010 12:13:15 -0500

So, remember back in December, I wrote a post about a Cantor crank who had a Knol page supposedly refuting Cantor's diagonalization?

This week, I foolishly let myself get drawn into an extended conversation with him in comments. Since it's a comment thread on an old post that had been inactive for close to two months before this started, I assume most people haven't followed it. In an attempt to salvage something from the time I wasted with him, I'm going to share the discussion with you in this new post. It's entertaining, in a pathetic sort of way; and it's enlightening, in that it's one of the most perfect demonstrations of the behavior of a crank that I've yet encountered. Enjoy!

I'm going to edit for formatting purposes, and I'll interject a few comments, but the text of the messages is absolutely untouched - which you can verify, if you want, by checking the comment thread on the original post. The actual discussion starts with this comment, although there's a bit of content-free back and forth in the dozen or so comments before that.

Read the rest of this post... | Read the comments on this post...

Cantor Crankery and Worthless Wankery

Fri, 29 Jan 2010 08:48:10 -0500

Poor Georg Cantor.

During his life, he suffered from dreadful depression. He was mocked by his mathematical colleagues, who didn't understand his work. And after his death, he's become the number one target of mathematical crackpots.

As I've mentioned before, I get a lot of messages either from or about Cantor cranks. I could easily fill this blog with nothing but Cantor-crankery. (In fact, I just created a new category for Cantor-crankery.) I generally try to ignore it, except for that rare once-in-a-while that there's something novel.

A few days ago, via Twitter, a reader sent me a link to a new monstrosity that was posted to arxiv, called Cantor vs Cantor. It's novel and amusing. Still wrong, of course, but wrong in an amusingly silly way. This one, at least, doesn't quite fall into the usual trap of ignoring Cantor while supposedly refuting him.

You see, 99 times out of 100, Cantor cranks claim to have some construction that generates a perfect one-to-one mapping between the natural numbers and the reals, and that therefore, Cantor must have been wrong. But they never address Cantors proof. Cantors proof shows how, given any purported mapping from the natural numbers to the real, you can construct at example of a real number which isn't in the map. By ignoring that, the cranks' arguments fail: Cantor's method still generates a counterexample to their mappings. You can't defeat Cantor's proof without actually addressing it.

Of course, note that I said that he didn't quite fall for the usual trap. Once you decompose his argument, it does end up with the same problem. But he at least tries to address it.

Read the rest of this post... | Read the comments on this post...

More about Dense Periodic Orbits

Tue, 26 Jan 2010 14:29:06 -0500

It's been quite a while since my last chaos theory post. I've been caught up in other things, and I've needed to do some studying. Based on a recommendation from a commenter, I've gotten another book on Chaos theory, and it's frankly vastly better than the two I was using before.

Anyway, I want to first return to dense periodic orbits in chaotic systems, which is what I discussed in the previous chaos theory post. There's a glaring hole in that post. I didn't so much get it wrong as I did miss the fundamental point.

If you recall, the basic definition of a chaotic system is a dynamic system with a specific set of properties:

Sensitivity to initial conditions,
Dense periodic orbits, and
topological mixing

The property that we want to focus on right now is the dense periodic orbits.

Read the rest of this post... | Read the comments on this post...

Zippers: Making Functional "Updates" Efficient

Wed, 13 Jan 2010 20:23:09 -0500

In the Haskell stuff, I was planning on moving on to some monad-related stuff. But I had a reader write in, and ask me to write another post on data structures, focusing on a structured called a zipper.

A zipper is a remarkably clever idea. It's not really a single data structure, but rather a way of building data structures in functional languages. The first mention of the structure seems to be a paper by Gerard Huet in 1997, but as he says in the paper, it's likely that this was used before his paper in functional code --- but no one thought to formalize it and write it up. (In the original version of this post, I said the name of the guy who first wrote about zippers was "Carl Huet". I have absolutely no idea where that came from - I literally had his paper on my lap as I wrote this post, and I still managed to screwed up his name. My apologies!)

It also happens that zippers are one of the rare cases of data structures where I think it's not necessarily clearer to show code. The concept of a zipper is very simple and elegant - but when you see a zippered tree written out as a sequence of type constructors, it's confusing, rather than clarifying.

Read the rest of this post... | Read the comments on this post...

The End Of The World is Coming in Just 501 Days!

Tue, 05 Jan 2010 11:46:02 -0500

A lot of people have been sending me links to a numerology article, in which yet another numerological idiot claims to have identified the date of the end of the world. This time, the idiot claims that it's going to happen on May 21, 2011.

I've written a lot about numerology-related stuff before. What makes this example particularly egregious and worth writing about is that it's not just an article on some bozo's internet website: this is an article from the San Francisco Chronicle, which treats a pile of numerological bullshit as if it's completely respectable and credible.

As I've said before: the thing about numerology is that there are so many ways of combining numbers together that if you're willing to spend enough time searching, you can find some way of producing any result that you want. This is pretty much a classic example of that.

Read the rest of this post... | Read the comments on this post...

Big Numbers and Air Travel

Mon, 04 Jan 2010 11:34:30 -0500

As you've surely heard by now, on christmas day, some idiot attempted to blow up an airplane by stuffing his underwear full of explosives and then lighting his crotch on fire. There's been a ton of coverage of this - most of which takes the form of people running around wetting their pants in terror.

One thing which I've noticed, though, is that one aspect of this whole mess ties in to one of my personal obsessions: scale. We humans are really, really lousy at dealing with big numbers. We just absolutely have a piss-poor ability to really comprehend numbers, or to take what we know, and put it together in a quantitative way.

Read the rest of this post... | Read the comments on this post...

Academia vs Industry: an Updated Opinion

Wed, 23 Dec 2009 17:02:53 -0500

One thing that continually amazes me is the amount of email I get from readers of this blog asking for career advice. I usually try to just politely decline; I don't think I'm particularly qualified to give personal advice to people that I don't know personally.

But one thing that I have done before is shared a bit about my own experience, and what I've learned about the different career paths that you can follow as a computer science researher. About six months after I started this blog, I wrote a post about working in academia versus working in industry. I've been meaning to update it, because I've learned a bit more in the last few years. When I wrote the first version, I was a research staff member at IBM's T. J. Watson research center. Since then, I left IBM, and I've been an engineer at Google for 2 1/2 years. Having spent a couple of years as a real full-time developer has been a seriously educational (and humbling) experience. If you'd like to look at the original to see how my thinking has changed, you can find it here.

At least as a computer scientist, there are basically three kinds of work you can do that take advantage of a strong academic background like a PhD. You can go into academia and do research; you can go into industry and do research; or you can go into industry and do development. If you do the last, you'll likely be doing what's sometimes called advanced development, which is building a system where you've got a specific goal, where you need to produce something real - but it's out on the edge of what people really know how to do. You're not really doing research, but you're not doing run-of-the-mill programming either: you're doing full-scale development of systems that require exploration and experimentation.

I'm going to talk about what the differences are between academic research, industrial research, and advanced development in terms of the basic tradeoffs. As I see it, there really five fundamental areas where the three career paths differ:

Freedom: In academia, you've got a lot of freedom to do what you want, to set your agenda. In industrial research, you've still got a lot of freedom, but you're much more constrained: you actually need to answer to the company for what you do. And in AD, you're even more constrained: you're expected to produce a particular product. You generally have a decent amount of freedom to choose a product to work on, but once you've done that, you're pretty much tied down.
Funding: In academia, you frequently need to devote huge amounts of your time to getting funding for your work. In industrial research, there's still a serious amount of work involved in getting and maintaining your funding, but it's not the same order of magnitude as in academia. And in AD, you don't really need to worry about funding at all.
Time and Scale: Academic projects frequently have to be limited in scale - you've got finite resources, but you can plan out a research agenda years in advance; in industrial work (whether research or AD), you've got access to resources that an academic can only dream of, but you need to produce results now - forget about planning what you'll be doing five years from now.
Results: What you produce in the end is very different depending on which path you're on. In academic research, you've got three real goals: get money, publish papers, and graduate students. In industry, you're expected to produce something of value to the company - whether that's a product, patents, reputation, depends on your circumstances - but you need to convince the company that you're worth what they're paying to have you. And in AD, you're creating a product. You can publish papers along the way, and that's great, but if you don't have a valuable product at the end, no number of papers is going to convince anyone that your project wasn't a failure.
Impact: what kind of affect your work will have on the world/people/computers/software if it's successful.

Read the rest of this post... | Read the comments on this post...

Friday Random Ten, 12/18

Fri, 18 Dec 2009 20:47:46 -0500

Naftule's Dream, "Speed Klez": Naftule's Dream is a brilliant progressive klezmer band. I happen to love klezmer, but I think that anyone into jazzy prog rock would also enjoy them. They're terrific.
Oregon, "Celeste": Oregon is a band that I can't make up my mind about. They're a jazz trio, with most melodies played by a wonderful oboist. They tend to really push the boundaries - playing with unusual tonalities, really pushing the edge of the envelope with their improvisation. It's quite impressive. And yet, they frequently leave me feeling cold, like there's nothing under the technique.
The Flower Kings, "The rainmaker": Ok, you've heard me babble about the Flower Kings before. They're the best prog band in the world today, and quite possibly the best ever. They're wonderful, and I've yet to hear anything by them that I didn't absolutely love. Go buy their recordings.
Parallel or 90 degrees, "Jitters": Po90 has a new album! Po90 is Andy Tillison's original band. Tillison is the co-founder, with Roine Stolte from the Flower Kings, of The Tangent, another wonderful band. Po90 has been mostly inactive for quite a while - but they just came back with a new album, and it's absolutely terrific. It's interesting how different it is from the Tangent - Tillison is the primary composer for both, but they manage to have very different sounds. Highly recommended.
Do Make Say Think, "In Mind": fantastic post-rock. DMSY is one of the best at what they do. If you like Godspeed or Mt. Zion, you should enjoy DMST.
Isis, "False Light": More fantastic post-rock, but from a very different style. Where DMST is post-alternative, Isis is sort of post-metal. The vocals take a bit of getting used to, but the overall quality of the music makes it worth the effort.
The Clogs, "Tides of Washington Bridge": Still more fantastic post-rock, from still another style. As you can tell, I'm a very big post-rock fan. Part of what I love about it is the breadth of the genre - it ranges from almost classical like the Clogs, to almost thrash, like Isis - and yet, it also manages to have a common form that makes it post-rock. The Clogs are one of my two favorites from the classical side of the genre. (The other being "Rachel's".)
Red Sparrowes, "Buildings Began to Stretch Wide Across the Sky": iTunes seems to be in a post-rock mood. Red Sparrowes are another terrific group, from the same stylistic family as DMST.
Bach, "Wiewohl Mein Herz in Traenen Schwimmt", from the St. Matthew Passion: In my opinion, Bach is quite simply the finest composer who ever lived. And the St. Matthew Passion is probably my favorite of his compositions. It's a work of sheer musical perfection. Music just doesn't get any better than this. If you can listen to this and not be moved, then you have no heart.
Thinking Plague, "Consolamentum": Every time Thinking Plague comes up in a FRT, I manage to get something about them wrong. Their guitarist either has a Google alert set up, or he reads my blog, because he shows up and patiently corrects my errors. I think of Thinking Plague as a very unusual post-rock group; lot's of people try to categorize them differently, because exactly what they are is a bit hard to pin down. They've got a very unique style that really isn't much like anything else I've ever heard. They work with odd tonalities, sometimes verging on atonal; they've got vocals, but the voice isn't a lead, it's treated as just another instrument in the mix. It's not the easiest thing to listen to - but if you like interesting, complex, beautiful music that doesn't stick with conventional tonality, then these guys are amazing. I found a couple of youtube clips to include below the fold to give you a taste.

Read the rest of this post... | Read the comments on this post...

ID Garbage: CSI as Non-Computability

Mon, 14 Dec 2009 10:43:48 -0500

An alert reader pointed me at a recent post over at Uncommon Descent by a guy who calls himself "niwrad", which argues (among other things) that life is non-computable. In fact, it basically tries to use computability as the basis of Yet Another Sloppy ID Argument (TM).

As you might expect, it's garbage. But it's garbage that's right up my alley!

It's not an easy post to summarize, because frankly, it's pretty incoherent. As you'll see when we starting looking at the sections, niwrad contradicts himself freely, without seeming to even notice it, much less realize that it's actually a problem when your argument is self-contradictory!

To make sense out of it, the easiest thing to do is to put it into the context of the basic ID arguments. Bill Dembski created a concept called "specified complexity" or "complex specified information". I'll get to the definition of that in a moment; but the point of CSI is that according to IDists, only an intelligent agent can create CSI. If a mechanical process appears to create CSI, that's because the CSI was actually created by an intelligent agent, and embedded in the mechanical process. What our new friend niwrad does is create a variant of that: instead of just saying "nothing but an intelligent agent can create CSI", he says "CSI is uncomputable, therefore nothing but an intelligent agent can create it" - that it, he's just injecting computability into the argument in a totally arbitrary way.

Read the rest of this post... | Read the comments on this post...

Another Cantor Crank: Representation vs. Enumeration

Wed, 09 Dec 2009 15:36:07 -0500

I've been getting lots of mail from readers about a new article on Google's Knol about Cantor's diagonalization. I actually wrote about the authors argument once before about a year ago.

But the Knol article gives it a sort of new prominence, and since we've recently had one long argument about Cantor cranks, I think it's worth another glance.

It's pretty much another one of those cranky arguments where they say "Look! I found a 1:1 mapping between the natural and the reals! Cantor was a fool!"

Read the rest of this post... | Read the comments on this post...

What is math?

Mon, 07 Dec 2009 13:21:11 -0500

I've got a bunch of stuff queued up to be posted over the next couple of days. It's been the sort of week where I've gotten lots of interesting links from readers, but I haven't had time to finish anything!

I thought I'd start off with something short but positive. A reader sent me a link to a post on Reddit, with the following question:

Throughout elementary and high school, I got awful marks in math. I always assumed I was just stupid in that way, which is perfectly possible. I also hated my teacher, so that didn't help. A friend of mine got his PhD in math from Harvard before he was 25 (he is in his 40's now) I was surprised the other week when I learned he isn't particularly good at basic arithmetic etc. He said that's not really what math is about. So my question is really for math fans/pros. What is math, really? I hear people throwing around phrases like "elegant" and "artistic" regarding math. I don't understand how this can be. To me, math is add, subtract, etc. It is purely functional. Is there something you can compare it to so that I can understand?

This hits on one of my personal pet peeves. Math really is a beautiful thing, but the way that math is taught turns it into something mechanistic, difficult, and boring. The person who posted this question is a typical example of a victim of lousy math education.

So what is math? It's really a great question, and not particularly an easy one to answer.

Read the rest of this post... | Read the comments on this post...

Advanced Haskell Data Structures: Red-Black Trees

Mon, 30 Nov 2009 20:09:59 -0500

So, we've built up some pretty nifty binary trees - we can use the binary tree both as the basis of an implementation of a set, or as an implementation of a dictionary. But our implementation has had one major problem: it's got absolutely no way to maintain balance. What that means is that depending on the order in which things are inserted to the tree, we might have excellent performance, or we might be no better than a linear list. For example, look at these trees. As you can see, a tree with the same values can wind up quite different. In a good insert order, you can wind up with a nicely balanced tree: the minimum distance from root to leaf is 3; the maximum is 4. On the other hand, take the same values, and insert them in a different order and you get a rotten tree; the minimum distance from root to leaf is 1, and the maximum is 7. So depending on luck, you can get a tree that gives you good performance, or one that ends up giving you no better than a plain old list. Playing with a bit of randomization can often give you reasonably good performance on average - but if you're using a tree, it's probably because O(n) complexity is just too high. You want the O(lg n) complexity that you'll get from a binary tree - and not just sometimes.

To fix that, you need to change the structure a bit, so that as you insert things, the tree stays balanced. There are several different approaches to how you can do this. The one that we're going to look at is based on labeling nodes in ways that allow you to very easily detect when a serious imbalance is developing, and then re-arrange the tree to re-balance it. There are two major version of this, called the AVL tree, and the red-black tree. We're going to look at the red-black. Building a red-black tree is as much a lesson in data structures as it is in Haskell, but along with learning about the structure, we'll see a lot about how to write code in Haskell, and particularly about how to use pattern-matching for complex structures.

Read the rest of this post... | Read the comments on this post...

A Special Midweek Recipe: Ad-Libbed Cranberry Chutney

Thu, 26 Nov 2009 17:45:38 -0500

It's not saturday, but I've got a recipe that I needed to write down before I forget it, so you're getting an extra bonus.

I usually make a simple cranberry relish for thanksgiving. But it needs to be made a couple of days in advance. This year, I completely forgot about the cranberries until this morning. So I figured I needed to do something else. A good chutney sounded nice. I went hunting online, but couldn't find anything that sounded good, so I went ahead and ad-libbed. And the results were amazing - this is definitely the new cranberry tradition in the Chu-Carroll household. Sweet, tart, and spicy - it's a perfect compliment for the turkey. Read the rest of this post... | Read the comments on this post...

Creating User-Defined Types in Haskell

Mon, 23 Nov 2009 09:55:45 -0500

(This is an edited repost of one of the posts from the earlier version of my Haskell tutorial.)
(This file is a literate haskell script. If you save it as a file whose name ends in ".lhs", it's actually loadable and runnable in GHCI or Hugs.)

Like any other modern programming language, Haskell has excellent support for building user-defined data types. In fact, even though Haskell is very much not object-oriented, most Haskell programs end up being centered around the design and implementation of data structures, using constructions called classes and instances.

In this post, we're going to start looking at how you implement data types in Haskell. What I'm going to do is start by showing you how to implement a simple binary search tree. I'll start with a very simple version, and then build up from there.

Read the rest of this post... | Read the comments on this post...