Math | nklein software

Ask a simple question… August 8th, 2009
Patrick Stein

Ask a simple question, spend the next forty minutes sifting through integral tables. Earlier, I took some code that was uniformly selecting points from a square centered at the origin and converted it to code using points from a normal distribution. For my purposes, I used a standard-deviation for the normal distribution that was half of the in-radius of the box. It wasn’t at all exact in any way.

What if I wanted to be exact? Suppose I wanted to switch from points uniformly distributed in a box to points from a normal distribution while maintaining the expected distance from the selected point to the origin.

What exactly is the expected distance from a selected point to the origin if one picks each coordinate for the point from a uniform distribution on the range [-1,+1]? Let’s start with the one-dimensional case. The probability density is $\frac{1}{2}$ everywhere. So, the answer is $2 \int_{r=0}^1 \frac{1}{2} r dr = \frac{1}{2}$ as we would expect.

(image created in Lisp using Zach's Vecto library) How about two dimensions? This is immediately more awkward. The one-dimensional disk looks exactly like the one-dimensional square. In two dimensions, the disk and square are quite different. We either have to integrate over the square and calculate the radius of each point, or we have to integrate over increasing radii and be careful once we get to the in-radius of the square. (image created in Lisp using Zach's Vecto library)

I originally chose to try to integrate over the square. The probability density is $\frac{1}{4}$ everywhere. This means the expected radius is $\int_{y=-1}^1 \int_{x=-1}^1 \sqrt{x^2+y^2} dx dy$ . This gets to be no fun very fast since the inner integral comes out with a logarithm in it. I mean, do you want to finish this integral?

$\int_{y=-1}^1 \left.\left( \frac{1}{2} x \sqrt{x^2 + y^2} + \frac{1}{2} y^2 \ln \left( x + \sqrt{x^2 + y^2} \right)\right)\right|_{x=-1}^1 dy$
It may be easy. I didn’t want to mess with it. I suppose once you evaluate the $x$ terms, it reduces a fair bit (if I did that all right):
$\int_{y=-1}^1 \left( \sqrt{1 + y^2} + \frac{1}{2} y^2 \ln \left( \frac{1 + \sqrt{1 + y^2}}{-1 + \sqrt{1 + y^2}} \right) \right) dy$
I still don’t want to touch it.

So, how about integrating over the radii? Again, the probability density is $\frac{1}{4}$ everywhere. This makes the expected radius:

$\int_{r=0}^1 \frac{1}{4} \cdot 2 \pi r dr + \int_{r=1}^{\sqrt{2}} \frac{1}{4} \cdot 8 \left( \frac{\pi}{4} - \arccos \frac{1}{r} \right) dr$
With a little massaging, you can move the $\frac{\pi}{4}$ from the second integral into the first instead:
$\int_{r=0}^{\sqrt{2}} \frac{1}{4} \cdot 2 \pi r dr - \int_{r=1}^{\sqrt{2}} \frac{1}{4} \cdot 8 \arccos \frac{1}{r} dr$
This is hardly consolation though. Here is where we get lost in our table of integrals for the better part of an hour.

And, this is only the two-dimensional case! In my original problem, the ambient space was 32-dimensional. My, oh my.

Axiom of Choice Joke: Now for Sale August 7th, 2009
Patrick Stein

There’s an old math joke that goes like this: The Axiom of Choice is obviously true. The Well-Ordering Theorem is obviously false. And, Zorn’s Lemma is just too complicated to be sure. It is a joke because it is easy to prove that they are equivalent.

For a month now, I have wanted to turn that joke into a Sign Language for Mathematicians picture. I finally got to it this evening. You can see the result on the right.

You can purchase it on a t-shirt or mug over at Zazzle, if you like.

The intuition

I am going to try to paraphrase the Axiom of Choice, the Well-Ordering Theorem, and Zorn’s Lemma to try to give you a sense of why each statement in the joke seems intuitively correct.

Suppose that I have infinitely many boxes. Each box contains one red ball and one blue ball. You can, with or without the Axiom of Choice, pick one ball from each box unless you are colorblind. If you are colorblind, you need the Axiom of Choice to pick one ball from each box even if you don’t care what color that ball is. What a wacky world it would be if a colorblind person could not pick a ball from each of these boxes. So, obviously, the Axiom of Choice should be true.

Suppose you have all of the real numbers from zero to one including both zero and one. If I asked you to give me the smallest number you’ve got, you could hand me the zero. Now, if I asked you to give me the smallest number you’ve got, you’re stuck. What the Well-Ordering Theorem says is that there is some way we could sort your collection of numbers so that no matter how many of them I take away (so long as I don’t take them all), you will never get stuck. It seems crazy that you can just shuffle your collection of numbers to keep me from thwarting you.

As the joke mentions, Zorn’s Lemma is complicated. On the one hand, Zorn’s Lemma says that if you took the genealogy of all people born in the last 8,000 years, then there exists at least one person with no ancestors born in the last 8,000 years. On the other hand, Zorn’s Lemma says that you didn’t need to shuffle your numbers so that you could still give me the smallest number in your hand after I took away the zero.

How it looks on a t-shirt

90% Accuracy Fails July 27th, 2009
Patrick Stein

Bruce Schneier pointed out this BBC News article about the base rate fallacy. In that article, they consider a Terrorist Detector that is right 90% of the time. Given that the test signals a positive for someone, how sure are you the person in question is a terrorist?

The gist of the math

Well, the math in that article is confusing. They say the answer is about 0.3%. But, they later do a diagram that makes it look like 1 in 100,000 to me. Further, they tacitly assume that while 10% of the time the test will identify a non-terrorist as a terrorist, it will never miss a real terrorist.

Regardless, the goal of the article is to show Bayes’s Theorem in action for something that has a low prior probability. In layman’s terms, if something is really, really unlikely, then you are very bad off if your test is only really good. It’s really unlikely that any given person is a terrorist. As such, if your test thinks every tenth person is a terrorist, your test is almost never right when it thinks it has found a terrorist.

In the article, they ask for help describing this fallacy in ways that will drive the point home to people on a gut level. I can kind of see how one could miss the idea in cancer screening. But, with terrorism?

The real world

Remember the last time you were on a plane? [Okay, I do… it was last Thursday.] You were sitting there with about a hundred fellow passengers. How many of them do you think were terrorists? My guess is that you were pretty sure (even before the flight took off) that zero of them were terrorists. How many of them bombed your flight? I’m pretty sure that number was zero (and not just because you wouldn’t be reading this otherwise). How many of you did the test think were terrorists? About ten.

What proportion of hundred-passenger flights would the test think are terrorist-free? Fewer than one in every 35,000 flights. Buy a lottery ticket if you’re on a flight where this (hypothetical) test thinks there are no terrorists because it just may be your lucky day.

To do the full analysis, you have to consider how many of those 35,000 flights really do have terrorists on them. But, it should be blatantly obvious to everyone that the answer is way, way under 34,999.

What is a terrorist, anyway?

This brings up another question that I always have when people start talking about detecting terrorists or the number of terrorists in the U.S., etc. When is someone a terrorist? If Khalid Sheikh Mohammed were traveling to Hawaii for some R&R, is he a terrorist? would the test detect him? should he be allowed on the plane?

Detecting terrorists is often talked about like detecting diseases and such. But, really, it is about detecting intentions. Intentions are far more evanescent than microbes.

“Visualizing Quaternions” by Andrew J. Hanson July 10th, 2009
Patrick Stein

Sunday night, I finished reading Visualizing Quaternions by Andrew J. Hanson. Unfortunately, the events of the week have kept me from writing this summary sooner. I feel like it would have been longer had I written it Monday. Alas, let’s play the cards in front of me.

This is a wonderful book. In addition to having gobs and gobs of useful content, it is a fine specimen of book design. The layout and illustrations are tremendous.

It tends to go from well-written, conversational passages that explain things in great detail to terse passages that mean nothing if you’re not a tensor-analysis whiz. But, even if you skim the parts that assume you know things you don’t, there’s still lots of book here to read.

There is even a nice appendix about Clifford algebras which folds in nicely with the complex number, quaternions, Clifford algebra posts that I’ve made here recently. If you do three-dimensional simulations or you like a good mathematical read, you should give this book a look.

Clifford Algebras for Rotating, Scaling, and Translating Space July 6th, 2009
Patrick Stein

In (very much) earlier articles, I described:

Today, it is time to tackle rotating, translating, and scaling three-dimensional space using Clifford algebras.

Three dimensions now instead of two

Back when we used Clifford algebras to rotate, translate, and scale the plane, we were using the two-dimesional Clifford algebra. With the two-dimensional Clifford algebra, we represented two-dimensional coordinates $(x,y)$ as $xe_1 + ye_2$ . It shouldn’t surprise you then to find we’re going to represent three-dimensional coordinates $(x,y,z)$ as $xe_1 + ye_2 + ze_3$ .

As before, we will have $e_1e_1 = 1$ and $e_2e_2 = 1$ . Similarly, we will have $e_3e_3 = 1$ . In the two-dimesional case, we showed that $e_1e_2 = -e_2e_1$ . By the same logic as the two-dimensional case, we also find that $e_1e_3 = -e_3e_1$ and $e_2e_3 = - e_3e_2$ . We could potentially also end up multiplying $e_1$ , $e_2$ , and $e_3$ all together. This isn’t going to be equal to any combination of the other things we’ve seen so we’ll just leave it written $e_1e_2e_3$ .

Read the rest of this entry ⇒

nklein software

software development and consulting

Ask a simple question… August 8th, 2009
Patrick Stein