Geomagnetism, Runways, and Sea Turtles

In the past month or so I have seen several news articles about the Earth’s magnetic field, which got me interested in modeling and analyzing it.  It started with reports that some airports in Florida were renumbering some of their runways to account for changes in the magnetic field.  One of the latest summary articles can be found here.  Most runways in the U.S. are identified by a number from 1 to 36, indicating the approximate magnetic heading (in degrees, divided by 10) on which airplanes take off or land.  For example, a north-south runway would be marked 18 at the north end for takeoffs and landings to the south, and marked 36 at the south end for takeoffs and landings to the north.  As the magnetic declination in a region changes over time, so does a runway’s magnetic heading.

Despite some amusing religious speculation about this being a sign of the end of days (see here), this is nothing new.  Wikipedia has a convenient animated GIF showing the changes in magnetic declination over the last 400 years or so.

The Sun-Sentinel article linked above describes these changes in a rather interesting way, stating that “magnetic north, the point at the top of the Earth that determines compass headings, is shifting its position at a rate of about 40 miles per year.”  This seems like a slightly misleading way to characterize the effect on compass headings.  The absolute position of the pole does not really mean much to a person trying to navigate with a compass.  I think a more useful metric is the change in magnetic declination over time.  For example, the following plot shows how much your compass heading changed between 2000 and 2010:

Change in declination from 2000 to 2010 (deg).

The changes in most of the U.S. are relatively minor, on the order of one degree or so, although you can see the more extreme behavior in Canada nearer the magnetic north pole.

The second interesting bit of news from just last week involved scientists studying how loggerhead turtles use their sense of the Earth’s magnetic field for navigation… but in a slightly more interesting way than you might think.  A good detailed Discovery blog post is here.

The idea is rather simple to state: in addition to using magnetic declination to provide a sense of direction, loggerhead turtles seem to use magnetic inclination together with overall field intensity to sense their location as well.  (Inclination is the angle between the magnetic field vector and the local level plane tangent to the Earth ellipsoid.)  That is, the turtles “map” magnetic inclination and field intensity into latitude and longitude to figure out where they are, then use magnetic declination as a “compass” in the usual way to find the desired direction to swim to get there.

The blog post makes the interesting comparison with the “longitude problem” of marine navigation in the 18th century, solved with robust and accurate timekeeping.  How much information does the magnetic field vector– not just its declination, but its precise direction including inclination, and overall magnitude– provide about your position, at least within certain regions of the Earth’s surface?

Following is a plot showing magnetic inclination over the Earth.  The two reference points mentioned in the turtle study were at approximately the same latitude, one near Puerto Rico, where inclination is approximately 44.5 degrees, and the other near the Cape Verde Islands off the coast of Africa, where inclination is only 14 degrees.

Magnetic inclination (deg).

These plots were made using my Java implementation of the International Geomagnetic Reference Field; source code may be downloaded at the usual location here.

• Langel, R. A. “The Main Field.” Rpt. In Geomagnetism Vol. 1. Ed. J. A. Jacobs. London: Academic Press, 1987. 249-512.

Counting Connections

A couple of weeks ago I began a course at work on computational topology.  The introduction included the definition of a topological space, which, briefly, is a set and a collection of subsets of that includes the empty set and the set itself, and is closed under (arbitrary) unions and (finite) intersections.  To illustrate the idea, the instructor used the simple example of a set with just 3 points.  He presented the class with 11 different examples of collections of subsets of , and asked us to identify which collections were topological spaces and which did not satisfy the closure properties above.  (See here for a graphical view of similar examples.)

I have a bad habit of always trying to count things.  Forget about the topology connection for a moment; since 11 seemed like a strange, rather specific number, it occurred to me to wonder whether this made up all possible collections of subsets, or if not, how many more are there?  Answering these questions involves some interesting mathematics, including what I suppose is my favorite theorem of all, if I were ever pressed to pick one.

First, we must be precise about what we are counting.  Given a set with elements, how many different collections of subsets of are there?  It depends on what we mean by “different.”  There are distinct collections of subsets, but this counting assumes, for example, that the collection {{}, {a}, {a,b,c}} is distinct from the collection {{}, {b}, {a,b,c}}, when for our purposes we don’t really care about the distinction between a and b.

What we want, then, is to group collections of subsets together under a suitable equivalence relation, and count equivalence classes.  This gets tricky, because the equivalence classes do not all have the same size.  Fortunately, there are some very powerful tools available, including the Orbit-Stabilizer Theorem, Burnside’s Lemma (actually due to Frobenius), and Polya’s Theorem, all of which are applications of the very useful idea of group action on a set.

I won’t bother with the rather tedious calculations here.  The punch line is that there are not just 11 but 20 different collections of subsets.  However, a separate calculation yields that exactly 9 of these collections correspond to topological spaces, so it turns out that the instructor’s original examples included all of these, with just a couple of “failures” thrown in.

Finally, as a result of this exercise, I learned about another interesting application of this same counting problem to switching theory.  Computing the first few terms of the sequence of numbers of collections of subsets of elements, and checking the Online Encyclopedia of Integer Sequences, we find sequence A003180, which also counts the number of Boolean functions of variables, unique up to permutation of the inputs.  In hindsight, this makes sense; we can represent particular input values to a Boolean function as the subset of inputs that are true (or 1), and characterize a particular Boolean function by the collection of (subsets of) inputs for which the output is true (or 1).

Happy Valentine’s Day

Card Puzzle, Part 2

The motivation for last week’s puzzle was, of all things, casino blackjack.  Consider the following common situation: several players sit at a blackjack table, all playing individually against the same dealer from a common shoe.  All of the players at the table are “experts” who know how to play the game.  They all know when to stand, when to hit, etc…. except for one.

This one player is a beginner and doesn’t know the game very well.  (Or perhaps she read one of the many books containing inaccurate information about the game.)  Worse yet, the beginner sits at “third base,” the chair closest to the dealer, and so everyone’s attention is focused on her hand as the last to be completed before the dealer turns over his hole card and completes his hand.

The beginner has twelve against the dealer’s six.  Twelve seems like a small number, so she hits, drawing a ten and busting.  The dealer then turns over his hole card, revealing a ten, and draws a five for a total of 21, taking money from the rest of the table as well.

One of the experts grumbles that the beginner “took the dealer’s bust card.”  That is, if she had stayed with her twelve like she was supposed to do, the dealer would have drawn the ten and busted instead of her, and she and the rest of the table would have won the hand.  But another player objects to this, claiming that the beginner’s decisions have no effect on the average return of any other player at the table.  Who is right?

Ok, so that is the setup, what does all of this have to do with last week’s puzzle?  As I will try to show, the original puzzle and the situation described above are essentially the same problem.  More importantly, in both cases, there is a nice intuitive argument for the solution, that I think may be more persuasive than more technical arguments, particularly in the case of casino blackjack.

First, recall the original puzzle: consider a standard, shuffled poker deck of 52 playing cards, of which 26 are red and 26 are black.  I place the deck face down on a table.  I will draw a card, one at a time, from the top of the pile and place it face up on the table for you to see whether it is red or black.  At some point before drawing the last card in the deck, you must say, “Stop.”  If the next card that I turn over is red, you win one dollar.  If it is black, you lose one dollar.  What is the optimal strategy for playing this game, and what is the probability of winning?

Let us approach the problem in a few different ways.  First, we can throw the computer at it; following is Mathematica code that computes the maximum possible probability of winning, by choosing the larger of the probability of stopping now or (recursively) the probability of drawing another card to continue the game:

v[0, b_] := v[0, b] = 0
v[r_, 0] := v[r, 0] = 1
v[r_, b_] := v[r, b] = Max[r / (r + b), r / (r + b) v[r - 1, b] +
                                        b / (r + b) v[r, b - 1]]
v[26, 26]

(As an aside, following is the same algorithm in MATLAB.  It is interesting to compare the two, noting which is easier to read and write, and why.  Functional programming and built-in pattern matching and memoization can be powerful tools.)

function p = v(r, b)

persistent q;
if isempty(q)
    q = nan(r,b);
end

if r == 0
    p = 0;
elseif b == 0
    p = 1;
elseif ~isnan(q(r,b))
    p = q(r,b); % retrieve previously computed value
else
    p = max(r / (r + b), r / (r + b) * v(r - 1, b) + ...
                         b / (r + b) * v(r, b - 1));
    q(r,b) = p; % save value for later retrieval
end

Running either of these two programs, we see that we can do no better than winning with probability 1/2.  But the really interesting observation is that we also can do no worse.  That is, even replacing Max[] with Min[] in the above code, actively trying to perform as poorly as possible, still yields an overall probability of winning equal to 1/2.  In other words, the game is fair no matter what strategy we follow.

Now that we know that the answer is simple, can we convince ourselves with a simpler argument than the brute force computer solution above?  To do this, consider the following very slight modification of the game: suppose that when you say, “Stop,” rather than turning over the next card from the top of the face down deck, I instead turn over the card from the bottom of the deck, and if it is red you win, black you lose.

Assuming that we can convince ourselves that this is the “same game” in some sense, then it is now much easier to see that our choice of strategy makes no difference in the average outcome, because it makes no difference even in the particular outcome for a given shuffled arrangement of cards in the deck.  Your payoff was determined by the shuffle of the cards before you even decided on a strategy, let alone before you got around to saying, “Stop.”

Coming back to the blackjack table now, it turns out that the resolution of the argument is the same, and for the same reason: the other players should not grumble at the beginner, because her strategy for removing cards from the shoe (or not) has no effect, on average, on the outcome of the dealer’s (and thus the other players’) hands.  There are a few technical details to consider that are described in this paper if you are interested, including the sense in which the original puzzle may be viewed as a special case of the more complex game of blackjack.

But I think the key point in the paper is relatively simple to explain and understand, and thus may be more persuasive than more technical arguments, particularly when dealing with a frustrated and possibly intoxicated blackjack player who just lost his money.  Specifically, suppose that we make a similar hypothetical change to the rules of the game: the cards for all of the players at the blackjack table are dealt from the top of the shoe as usual, but the cards for the dealer’s hand are dealt from the bottom of the shoe.  Just as with the original puzzle, I think this perspective makes it clearer that any one player’s choice of strategy does not affect the probabilities of the various outcomes of the dealer’s hand.

Card Puzzle, Part 1

This week’s post is a puzzle.  It is not even a relatively new puzzle… but I think it’s a good one, because the problem, and more precisely one of its several solutions, have an interesting relationship to some slightly more practical situations that I have been asked about recently.  (As a teaser, I recall being involved at least once in such a “practical” situation, that nearly escalated to physical confrontation.  It is strange the things that people feel strongly about.)

Before going into more detail, though, it has been suggested– correctly, I think– that I tend to spoil possibly interesting problems by including solutions in the same post.  To remedy that, following is just the statement of the problem.  Discussion is welcome in the comments; I will continue next week with my view of the problem and how I think it applies elsewhere.

Consider a standard, shuffled poker deck of 52 playing cards, of which 26 are red and 26 are black.  I place the deck face down on a table.  I will draw a card, one at a time, from the top of the pile and place it face up on the table for you to see whether it is red or black.  At some point before drawing the last card in the deck, you must say, “Stop.”  If the next card that I turn over is red, you win one dollar.  If it is black, you lose one dollar.

What is the optimal strategy for playing this game, and what is the probability of winning?