The Travelling Santa Problem

This is a problem that briefly entertains me each year around this time, because it's mathematical and I'm me.

The question is, "How fast does Santa have to go to visit all those homes?"  We're not going to assume he has to go down chimneys or anything like that; he just has to get to all of the homes.  But assuming that Santa is real, he is still subject to the laws of physics.  No getting around those.

The Travelling Santa Problem bears a distinct resemblance to another classic problem of computation, the Travelling Salesman Problem.  A typical statement of this problem (made as non-gender-specific as I can manage) goes as follows: A sales rep must visit the capital cities of all 48 contiguous states, in whatever order desired.  What order minimizes the total travel distance?  It doesn't matter whether the sales rep drives or flies; what matters is that there is a definite and known distance between any pair of capitals.

For small numbers of capitals, this problem is trivial.  Consider three cities: Sacramento CA, Carson City NV, and Phoenix AZ.  The air distances between these cities are S-C = 160 km, C-P = 930 km, and P-S = 1016 km (I got these figures from the City Distance Calculator at http://www.geobytes.com/citydistance.htm).  The sales rep, in order to minimize the total travel distance, should avoid the long Phoenix-to-Sacramento leg, and visit the cities in the order Sacramento, Carson City, Phoenix (or the reverse).

Adding a fourth city does complicate matters somewhat.  The cost of adding one city is three new distances.  If we add, say, Boise ID, the new distances are S-B = 712 km, C-B = 580 km, and P-B = 1179 km.  And instead of only three essentially different routes, there are now twelve: B-C-P-S, B-C-S-P, B-P-C-S, B-P-S-C, B-S-C-P, B-S-P-C, C-B-P-S, C-B-S-P, C-P-B-S, C-S-B-P, P-B-C-S, and P-C-B-S.  (There are twelve other orders, for a total of 4! = 24, but the other twelve are the reverse of those already listed, and are the same for the purpose of total distance.)  By exhaustive calculation, we find that the minimal path is B-S-C-P (or P-C-S-B), with a total length of 712+160+580 = 1452 km.

One thing that becomes quickly apparent about this problem is that you can't solve it just by picking the three shortest distances, because those three distances may not connect all of the cities, or do so in a path.  Instead, in this case at least, we had to try all the different routes and pick the shortest overall route.  In fact, the Travelling Salesman Problem is a so-called NP-hard problem; this ties it with a number of other problems whose solution times are all expected to increase exponentially with the size of the problem, barring some unexpected theoretical advance.

In the case of the Travelling Santa Problem, however, we are not interested in knowing how Santa knows what order to visit the homes, or even what order he actually visits the homes.  We just need to know, to a rough order of magnitude, how far he must travel to visit every home.

Let us consider that the current population of the Earth is about seven billion.  How many homes is that (if by home we mean any single living unit)?  There are some homes with lots of people in them, living as a unit; on the other hand, there many homes with only one person in them.  We probably would not be too far off if we assume an average of two people per home.  That would mean 3.5 billion homes to visit.

Now, if these 3.5 billion homes were evenly distributed across the surface of the Earth, which has a surface area of about 510 million square kilometers, each home would have to itself an average of about 0.15 square kilometers, which means the mean home-to-home distance would be about 0.4 km, and Santa would have to travel about 3.5 billion times 0.4 km, or about 1.4 billion km.  If we assume that Santa has to travel all that way in a single day (86,400 seconds), that means he must travel about 16,000 km/s, a little over a twentieth of the speed of light.  So, very fast (about 35 million mph), but at least doable in principle.

In truth, it's a bit better than that.  In the first place, most of the Earth's surface is water; only about 30 percent of it is land.  Of that, the polar lands, especially around Antarctica, are not readily habitable in the usual way, so that perhaps only about 25 percent of the Earth's surface has any appreciable habitation.  That cuts the total distance in half to about 700 million km, and the necessary speed to 8,000 km/s.

Even better, human homes are not evenly distributed across the 25 percent of the Earth's surface they cover, but are clumped together in towns, villages, and cities large and small.  We might consider a clump to be any collection of homes that are within 100 meters of at least one other home.  This means, among other things, that a single isolated home is considered to be a clump.

It's hard to know the exact number of such clumps in the world, but perhaps we would not be too far off if we let the average clump size be 350 homes.  In that case, the total number of clumps would be 3.5 billion, divided by 350, or 10 million clumps.  The average clump-to-clump distance would then be about 7 km, and the total clump-to-clump travel distance would be 10 million times 7 km, or 70 million km.  To that would have to be added the home-to-home travel in each clump of 350 homes.  If each pair of homes is separated by 100 meters, and there are 350 homes, then each clump requires an additional 35 km, times 10 million clumps, or 350 million km, for a grand total of 420 million km.  That cuts the necessary speed to just under 5,000 km/s.

Of course, 100 meters is just the maximum cutoff distance between homes in a clump.  The average distance would be rather smaller.  In a major city like New York, for instance, the average distance is probably closer to 10 meters; in other areas, the average might be smaller than that.  In that case, the total clump internal distance for 350 homes would be more like 3 or 4 km, for a total distance of 100 million km, with a required speed of about 1,200 km/s.

Finally, statistical studies show that if N clumps are randomly distributed over an area of about A = 130 million square kilometers (as we've assumed here), the unevenness caused by that random distribution creates some clumping in the clumps, so that the total clump-to-clump travel distance is given approximately by  √(NA/2) = √(650 million million square kilometers) = 25 million km, lowering the total distance to 60 million km, and the speed to 700 km/s.

That's still about 1.6 million mph—fast enough to go around the Earth in a single minute—so perhaps Rudolph better get going.

A Pair of Potter Poems (Picked by Peter Piper?)

Here are a couple of poems.  Sonnets again.  The schtick here is that they concern a pair of Harry Potter characters.  It should be trivial to figure out who they are (although it might require a dictionary for our younger readers).

(I admit I felt compelled to put these here so that the three of you coming from Ash's poetry blog don't feel like you got put on a bus to Hoboken, Nerd Jersey.)

emerge

The boy stepped forth and took his place beneath
the brim.  A minute passed, now two, then three,
within which time the shades of bravery
and justice armed their forces to the teeth.
Though all saw brav'ry take the palm and wreath,
it lay in waiting, seeming idly:
At length, his courage glowed for one to see,
demure, as though he'd drawn it from its sheath.
It wavered, unaccustomed to the light;
it felt about, uncertain of its tread.
Till blunt necessity called out its right,
to cleave the foul ophidian at its head.
Oh say! where night left off and day began,
to slumber off a boy and wake a man.


unreadable

He stands, a glower made inscrutable,
ambiguous.  He wreaths his honest thoughts
in coronets of random noise, in knots
of truths both blank and indisputable.
The swollen ranks, beneath his gaze, bear gloom.
Their dully thronging stride stamps out the time
left to his bitter charge, and neither rhyme
nor reason can forestall his chosen doom.
Though he may carp or cavil over weights
none else has will or wherewithal to bear,
that memory, besmirched, of onetime mates
does focus his poor genius in its glare.
So pity not the fool who plays the lie--
once! twice! now thrice!--to gamble and to die.

Copyright © 2011 Brian Tung

Why CPU Utilization is a Misleading Architectural Specification

MOAR Q-ING TREE PLZ.

Actually, this post only has a little to do with queueing theory.  But I can't help tagging it that way, just 'cause.

Once upon a time, before the Internet, before ARPANet, even before people were born who had never done homework without Google, computer systems were built.  These systems often needed to plow their way through enormous amounts of data (for that era) in a relatively short period, and they needed to be robust.  They could not break down or fall behind if, for instance, all of a sudden, there was a rush in which they had to work twice as fast for a while.

The companies that were under contract to build these systems were therefore compelled to build to a specified requirement.  This requirement often took a form something like, "Under typical conditions, the system shall not exceed 50 percent CPU utilization."  The purpose of this requirement was to ensure that if twice the load did come down the pike, the system would be able to handle it—that the system could handle twice the throughput that it experienced under a typical conditions, if it needed to.

One might reasonably ask, if the purpose was to ensure that the system could handle twice the load, why not just write the requirement in terms of throughput, using words something like, "The system shall be able to handle twice the throughput as in a typical load of work"?  Well, for one thing, CPU utilization is, in many situations, easier to measure on an ongoing basis.  If you've ever run the system monitor on your computer, you know how easy it is to track how hard your CPU is working, every second of every day.  Whereas, to test how much more throughput your system could handle, you'd actually have to measure how much work your CPU is doing, then run a test to see if it could do twice as much work without falling behind.  A requirement written in terms of CPU utilization would simply be easier to check.

For another thing, at the time these requirements were being written, CPU utilization was an effective proxy for throughput.  That is to say, in the single-core, single-unit, single-everything days, the computer could essentially be treated like a cap-screwing machine on an assembly line.  If your machine could screw caps onto jars in one second, but jars only came down the line every two seconds, then your cap-screwing machine had a utilization of 50 percent.  And, on the basis of that measurement, you knew that if there was a sudden burst of jars coming twice as fast—once per second—your machine could handle it without jars spilling all over the production room floor.

In other words, CPU utilization was quite a reasonable way to write requirements to spec out your system—once upon a time.

Since those days, computer systems have undergone significant evolution, so that we now have computers with multiple CPUs, CPUs with multiple cores, cores with multi-threading/hyper-threading.  These developments have clouded the once tidy relationship between CPU utilization and throughput.

Without getting too deep into the technical details, let me give you a flavor of how the relationship can be obscured.  Suppose you have a machine with a single CPU, consisting of two cores.  The machine runs just one single-threaded task.  Because this task has only one thread, it can only run in one core at a time; it cannot split itself to work on both cores at the same time.

Suppose that this task is running so hard that it uses up just exactly all of the one core it is able to use.  Very clearly, if the task is suddenly required to work twice as hard, it will not be able to do so.  The core it is using is already working 100 percent of the time, and the task will fall behind.  All the while, of course, the second core is sitting there idly, with nothing to do except count the clock cycles.

But what does the CPU report is its utilization?  Why, it's 50 percent!  After all, on average, its cores are being used half the time.  The fact that one of them is being used all of the time, and the other is being used none of the time, is completely concealed by the aggregate measurement.  Things look just fine, even though the task is running at maximum throughput.

In the meantime, while all of these developments were occurring, what was happening with the requirements?  Essentially nothing.  You might expect that at some point, people would latch onto the fact that computing advances were going to affect this once-firm relationship between CPU utilization (the thing they could easily measure) and throughput (the thing that they really wanted).

The problem is that requirements-writing is mind-numbing drudge work, and people will take any reasonable measure to minimize the numbness and the drudge.  Well, one such reasonable measure was to see what the previous system had done for its requirements.  What's more, those responsible for creating the requirements were, in many cases, not computer experts themselves, so unless the requirements were obviously wrong (which these were not), the inclination was to duplicate them.  That would explain the propagation of the old requirement down to newer systems.

At any rate, whatever the explanation, the upshot is that there is often an ever-diverging disconnect between the requirement and the property the system is supposed to have.  There are a number of ways to address that, to incrementally improve how well CPU utilization tracks throughput.  There are tools that measure per-core utilization, for instance.  And even though hyper-threading can also obscure the relationship, it can be turned off for the purposes of a test (although this then systematically underestimates capacity).  And so on.

But all this is beside the point, which is that CPU utilization is not the actual property one cares about.  What one cares about is throughput (and, on larger time scales, scalability).  And although one does not measure maximum throughput capacity on an ongoing basis, one can measure it each time the system is reconfigured.  And one can measure what the current throughput is.  And if the typical throughput is less than half of the maximum throughput—why, that is exactly what you want to know.  It isn't rocket science (although, to be sure, it may be put in service of rocket science).

<queueingtheory>And you may also want to know that the throughput is being achieved without concomitantly high latency.  This is a consideration of increasing importance as the task's load becomes ever more unpredictable.  Yet another reason why CPU utilization can be misleading.</queueingtheory>

The Strange Existence (and Subsequent Non-Existence) of Albert Cribbage

(a précis)

This is not a poem, not even a prose poem.  But it shares enough quirkiness with poems I enjoy for me to find it in the spirit of National Poetry Month, so in it goes.

I found this while I was going over some of my old writing projects.  I say "projects"; these were not for any kind of organized course or anything.  I wrote (as I still do) whenever I have a bit of idle time and am able to cobble together thoughts in any particular direction.  This one struck my fancy, and the précis tag was intended to remind me to extend it into a more protracted argument, which (of course) never happened.  Other ideas distracted, and continue to distract.

Anyway, without further ado, we present:

The Strange Existence (and Subsequent Non-Existence) of Albert Cribbage

Albert Cribbage had his dream, and he spent much of his life constructing her. Blessed with the world's longest serial lucid dream, he manufactured a perfect Woman over a period of years, taking as inspiration pictures from fashion magazines (the late 80s, which he preferred, much to the disgust of his "hipper'' friends), television commercials for beauty products, and several of the mainstream literary journals. He did, after all, want her to be well read.

At last he had completed her; all that remained to bring her to life (insofar as that was possible for her) was the Kiss. He went out and purchased fine satin sheets, and a royal purple bed cover set (limned in gold cord, of course). He settled into bed, and tried to go to sleep, with great difficulty, as he had never in his life been so excited.

At length, he managed to doze off. His dream began, as planned, with him approaching his soon-to-be-loved in his bed. He leaned down, as in the fairy tales of yore, and touched his dry, trembling lips to her still, perfect ones. Instantly, she opened her eyes, and it was as if they had been waiting for each other for all of eternity. She allowed herself to be swept up even further in the kiss, and he was soon with her, under the covers.

They made love, passionately, in the semi-darkness (where all dreams are; the well-lit ones are simply optical illusions in mid-slumber), and after several exhausting but very satisfying hours, their legs became entwined as they enjoyed the smooth sleep of afterglow.

In the morning she awoke, and the memory of the past night had left a smile on her face. But, she mused, he was still not quite perfect (italics hers), and once the morning niceties (a warm shower, a generous breakfast) were done, she set out for the newsstand, where she thought the latest monthlies from Paris might just give her the ideas she needed to create a new dream lover, one she would want to keep for good...

Copyright © 1996 Brian Tung

When We Flew

[Another Facebook post cannibalized for National Poetry Month.  At the time I wrote this, Kobe had not yet suffered his season-ending Achilles injury.]

I was watching yet another YouTube clip of Kobe wowing us with his athleticism and wizardry, and I started thinking about how many of the highlights were in another century. Hard as it may seem to believe at the moment, there will come a day when Kobe will no longer be able to dunk. It might not come this decade—hell, if MJ is any indication, it might not come the next, either—but it will come.

Anyway, I started getting a bit depressed about that, and so as if to bring myself out of that funk, I started scribbling some lines. And I found that it actually sort of helped, a little. I hasten to emphasize that all this has nothing at all to do with the fact that a birthday is coming up, or anything like that. That is so a coincidence.

It may read as though it's about other things, and it can be. But I really did write it with basketball in mind.

when we flew

When we flew,
we made legends.
We startled and we stunned,
and foes grasped at us in vain.
Our wings would never tire,
and our lungs never fail.
The world lived a thousand times
and never knew how close it had come,
and all because we flew
     when we flew.

When we flew,
time stood to watch,
then travelled back to watch again,
hardly daring to believe.
Space cleared space for us,
and light held us in her gaze.
The stars shone their mute fanfare
shattering their crystal spheres,
and all because we flew
     when we flew.

Now we stand,
make way while children soar.
We wear our pride like envy,
and dress our unease in longing.
We envision battles we will never fight,
and so we shall never lose.
A thousand times we'll close our eyes and ears
and sip champagne from glass slippers,
and all because we flew
     when we flew.

Copyright © 2012 Brian Tung

The Wolfpack and the Lone Wolves

So a friend of mine posted a link to this story, and because it involves game theory (even though it wasn't actually a game theory course) and I do, in fact, work like that, I immediately started thinking about a way to analyze it.  Actually, I think thirty students is way too many to get some of the more interesting interactions going; the wolfpack is almost certainly the way to go, especially if you're not one of the brighter bulbs.  Thirty is probably too many to deal with analytically anyway.  So let's start with three.

Suppose the three students A, B, and C have (possibly) different aptitudes, represented by a, b, and c, respectively.  These three numbers represent the probability with which each of the students answers questions correctly.  (We'll assume that questions have two answers, one right and one wrong.)  Without loss of generality, let's say that a ≥ b ≥ c.  Under which conditions will two or more of these students collude?  Without explicitly prescribing a curve, let us say that the aim of any of the students is to improve their own grade; specifically, there is no benefit to philanthropy.

We can fairly quickly conclude that two students will not collude.  Consider A and B, and suppose first that a > b, and that A and B know that (that A is a better answerer than B).  A and B compare answers.  If they coincide, then of course they both answer that way, but if they differ, they'll choose A's answer (since it's more likely to be correct than B's).  But if that's the case, then they'll both answer correctly only if A already had the right answer.  That is to say, both A and B will answer correctly with probability a.  Well, there's no reason for A to collude with B, since it helps B without helping A.

The situation is not helped even if a = b, since the only difference is that some other means must be used for breaking the tie.  No matter how the tie is broken, the answer that is chosen cannot have a greater probability of being correct than a = b, so there is no benefit to collusion for either A or B.

A similar line of reasoning applies to any other pair of students.  Well, then how about all three students colluding?  That will only happen if all three students are benefited, and A, with the highest aptitude, is the standard here.  Let's consider how A's answer would be affected by the collusion.  The first way is that A's initially correct answer would be made incorrect by collusion.  That happens if A would have answered correctly, but B and C would not.  That happens with probability a (1 - b) (1 - c).

The second way to affect A's answer is to change an initially incorrect answer into a correct one.  That happens with probability (1 - a) b c.  So, on balance, A has an incentive to collude (and therefore all students do) if

(1 - a) b c > a (1 - b) (1 - c)

For instance, if the three students respectively have 90, 80, and 70 percent probabilities of answering questions correctly, then we have

(0.1) (0.8) (0.7) = 0.056 > 0.054 = (0.9) (0.2) (0.3)

and it makes sense for all three to collude, by this metric.

Why by this metric?  What other metric could there be?  Suppose we now introduce an explicit curve: The students receive, as their final grade, not their actual raw score, but a ranking-scaled score.  The top raw score earns three points, the second best raw score earns two points, and the lowest raw score earns one point.  Two students tying at the top both earn 2.5 points, while two students tying at the bottom earn 1.5 points, and finally if all three students tie, they all earn two points.

Under these conditions, the three students will not all collude.  A, as the best student, is the most likely of the three to earn three points, and the more questions there are, the more certain that is.  If A, B, and C all collude, they will all three earn two points (since their answers will be identical).  So chuck out three-way collusion.

But two-way collusion is now even less likely than before.  As we observed, it only improves the accuracy of the inferior student.  Before, that at least did not hurt the superior student, but now it improves the inferior student's scaled score at the expense of the superior student's scaled score.  So two-way collusion is out, too.

Shall we move on to four students?  I'll save that for a later post.

i saw in yesterday your pretty when

I almost called this "in crude homage to edward estlin," but I thought maybe that would be too predictable.

Most people know about E.E. Cummings's free verse.  I first came into contact with his name, if not his poetry, from a poster in my seventh-grade English classroom.  (Does anyone remember Mr. Clancy from Redwood Junior High?  No?)  I don't think I actually read any of his poems until rather much later.  I did hear an exquisite (and in context, wholly inappropriate) love poem of his in Woody Allen's Hannah and Her Sisters, entitled "somewhere i have never travelled,gladly beyond."

I may as well say that although his deconstructive approach to grammar is refreshing, I find some of his poems orthographically grotesque.  Not for the reasons most frequently cited; I have no problem with his lack of capitalization (I do that myself in chats), or his exuberantly nested parentheticals, or anything pedestrian like that.  No, what bothers me are the superlatively trivial things, like not having a space after commas (see above, you have no idea how that killed me to accurately reproduce his title), or before parentheses, and that sort of thing.

Anyway, because of the renown of his free verse, not many people know that he wrote sonnets, too, and intensely romantic ones at that.  Sonnet XCII of his 95 Poems is one of his better known ones; it goes

i carry your heart with me(i carry it in

my heart)i am never without it(anywhere

i go you go,my dear;and whatever is done

by only me is your doing,my darling)

                                                                    i fear

no fate(for you are my fate,my sweet)i want

no world(for beautiful you are my world,my true)

and it’s you are whatever a moon has always meant

and whatever a sun will always sing is you

here is the deepest secret nobody knows

(here is the root of the root and the bud of the bud

and the sky of the sky of a tree called life;which grows

higher than soul can hope or mind can hide)

and this is the wonder that’s keeping the stars apart

i carry your heart(i carry it in my heart)

(It's a good thing that all I had to do was cut and paste; I don't know that I could have elided all those spaces otherwise.)  Anyway, here's my tyro's try at the same kind of thing, and at least it's honest, it's a thing I feel (and doggone it, I shall put spaces where I will):

i saw in yesterday your pretty when

i saw in yesterday your pretty when
and past a rise your beautifully where
(i do lose during you my now and then,
and inside you(r inside) my here and there).
since draw me to your captivating why
(a finger may mislead, i have no who
that cries the how you tear), i heard them sigh
your fragile yes or maybe noes to do.
with you i have no ask or answer (no
inquire or wonder, neither no believe,
no yet or still, no if (or so, or so)
for(giving life, where is no is to grieve))
but breath demanding breath, each every day
in death for(little death) you to replay.

Copyright © 2013 Brian Tung

Daybreak (a Chinese poem)

Another offering for National Poetry Month, but something a bit more unusual this time.

Every now and then, I'll attempt a Chinese poem.  Because I'm not as fluent as I'd like to be, this effort is invariably a little stilted, but (I hope, at least!) progressively less stilted each time.  Before I say any more, here first is my latest attempt in the original Chinese:

朝陽

夜裡星星亮，
朝陽處處光。
青年游外地，
老是想家鄉。

Now, those of you who speak Chinese will probably recognize this as somewhat stilted (which is true), while those of you who don't have no idea what I just said.  I'll explain in a moment, but before I do so, allow me to put on my professor hat and insert a few thoughts on Chinese poetry.

I make no secret of the fact that I find Chinese writing to be the most beautiful.  By that I don't mean that I find Chinese prose better than prose in other languages; I mean the actual written characters.  But because I actually do read Chinese (about 60 to 80 percent as well as I'd like to, but that's a story for another time), I instinctively see the meaning behind most of the characters before I see their form.  I often wonder what it's like to see those characters from the perspective of someone who has no idea what they say.

At any rate, one of the appealing features of Chinese writing is that the characters (which are almost universally monosyllabic) are distinct and individual pieces of art, and a Chinese poem puts that all together in a composite that's a piece of art (when properly conceived) at multiple levels.

Because the monosyllabic characters are all distinct, one can easily tell from the above that this poem consists of four lines of five syllables each.  That may remind some of you of the poem's more famous Japanese relative, the haiku, which is three lines of five, seven, and again five syllables.  In fact, I would say that—in Western minds at least—that is the defining characteristic of the haiku, is that it contains seventeen syllables in that arrangement.

Writing these poems gives me some insight, though, why that conception isn't accurate, even with respect to Asian poetry in general.  (I think it's a remarkably trivial characterization, not the least because it's totally underspecified.  See the postscript, for instance.)

In the first place, there's a difference between Chinese syllables and English syllables.  The majority of Chinese words are polysyllabic—that is, they consist of compounds of two or more characters—but nevertheless, the characters retain a distinct identity that is different from that of English syllables.  The characters are less subordinated to the line, so to speak.  That is more true of older writing than of modern writing, and also more true of poetry than of prose.

From a more technical perspective, Chinese poetry has its constraints that roughly map onto English meter and rhyme.  For instance, the above poem belongs to a form called 五言絕句, which means (broadly translated) five-character quatrain, which it clearly is.  This form prescribes a simple rhyme scheme: the end of the second line must rhyme with the end of the fourth line.  And they do: the characters in question are spelled, in hanyu pinyin, guāng and xiāng, and even if you don't know a darned thing about Chinese spelling, I think you can tell that the two characters rhyme.  (The macrons over the a's indicate that the tones match, too, which they must do.)

In addition, the tones of the characters must follow certain arrangement rules.  Chinese characters generally have one of four different tones, of which the first two might be called "level" tones, and the last two "deflected" tones.  [EDIT: I should add here that originally, there was only one level tone and three deflected ones.  The one level tone evolved, in Mandarin, into the first two tones, while the second and third tones evolved into the last two Mandarin tones.  The fourth original tone, the so-called entering tone, disappeared from Mandarin, and characters with that tone were haphazardly distributed amongst the surviving tones.]

The tones in the first couplet must complement each other, as must the tones in the second couplet.  That is to say, for every level-tone character in the first line, the corresponding character in the second line must have a deflected tone, and vice versa.  The same is true of the third and fourth lines.  For instance, the above poem has the following pattern of tones (if we denote level tones with = and deflected tones with ×):

××==×
==××=
===××
×××==

What's more, the patterns are traditionally restricted.  One does not generally see ===== or ×××××, or =×=×=, or anything like that.  Some variation is permitted (as is true of English poems, too), but is fairly carefully circumscribed.

In addition to all this is the usual transcendant pressure to make the expression of the form "beautiful" in some ill-defined (and probably undefinable) way, so that it isn't just a bunch of syllables, nor a bunch of syllables conforming to some rules, nor even a bunch of sensible syllables conforming to some rules.

I don't know Japanese at all, really, so I have no idea if some of these considerations apply (or if there are others in their place), but I certainly do not expect that haiku are simply seventeen syllables in a particular arrangement.  I have heard, for instance, that some reference to the seasons is expected, and that the syllables are not really syllables, but mora (the Japanese unit of speech timing), and so forth.

Anyway, enough of this palavering.  Here's a rough English translation of the poem:

daybreak

The stars gleam in the nighttime,
but the dawning sun drowns them all out.
We venture into the world in our youth,
but thinking always of our hometown.

No, it's not deep, I never said it was!  I'm working on it!

P.S.  Because I'm unable to let a post go without some nerdery involved: Suppose that one uses a vocabulary of English words that are (with equal probability) one, two, or three syllables long.  What is the probability that an arbitrary sequence of words totalling seventeen syllables can be broken into lines of five, seven, and then five syllables without breaking a word?

The Passion of the Play

Another offering for National Poetry Month.

This is for all those who feel that sports is incapable of being an art, or poetry, or beauty.  (I don't think any of those read my blog, but I suppose you never know.)

the passion of the play

You throng who find in contests but
an infinite procession of
bats, balls, and running, jumping—what
you miss!  (Look at the sky above:
Do you see only endless dots?
Or in the rolls of history,
but names and dates—bereft of thoughts
and love, and pride—exclusively?
A narrative from breath to breath
we savor in our champion's flight:
War without anger, without death;
Force without peril, without spite.
Drink you of whiskey or of wine,
imbibe you spirited design!

Copyright © 2013 Brian Tung

The Slowness of the Post

Once again, it's National Poetry Month here in the States.  (Do I have any international readers?  Actually, do I have any readers?  Sometimes it's hard to tell, hint hint.)

I can't just be posting old ones, though, so this one is kind of new.  I started this and had the opening quatrain and the ending couplet a couple of years ago, but then gave it up.  This is my rather indifferent attempt, I'm afraid, at filling up the inside.  Don't worry, I'm not giving up my day job; I like that one a bit too much.

[EDIT: And I just noticed that this poem has extra bonus enjambment.  So, umm, yeah.]

the slowness of the post

When lovers in years past took quill in hand
to add to their epistolary chain
the latest, best-wrought link, they might complain
about the slowness of the post.  They planned
their thoughts for days, while trains traversed the land
with bundled hearts and holes, delayed by rain,
or frailty, or the smugness of the sane.
(But, yes, this did make love more tragic.)  And
now, though we write in liquid crystals, though
we fancy we eliminate the tragic,
anticipation, overnight, is no
less puzzling, no less vexing—no less magic.
    Look to the sky—yes, look, her answer, soon—
    look for it ere the waning of the Moon!

Copyright © 2013 Brian Tung

A Post-Easter Puzzler

Recently, a good friend gifted me a bag of Easter SweeTarts, with ducks and bunnies in place of the usual round candies.  They come in five flavors, which are officially blue raspberry (blue), cherry (pink), grape (purple), orange (orange) and green apple (green).  (This according to Wikipedia, at least.)

I don't like the blue ones, so because I'm that way, I culled those out and they're still sitting in front of me in a bowl.  The rest I ate at my leisure—though rather less leisurely than is quite becoming, I'm afraid.

At some point, near the end of the bag, I wondered what the probability was, if I pulled out two candies at random, that they'd have the same flavor.  I looked at the candies that were in there, and it was a simple matter to figure the answer out.  It was—ahh, but then I'd be giving the puzzle away. 

I then turned to look away and puckishly reached into the bag and pulled out a pair of green apples.  (Those are my second favorite, after the artificial grape ones, which, as you'll know if you eat them, taste nothing at all like actual grapes.)  I wondered if that affected the probability at all—figuring that if anything, it would have reduced the odds—but after looking in and doing some quick figuring, I found that the odds were exactly the same as before.

"Hunh!" I thought to myself in surprise, and (if you know me at all, you know what happened next) I wondered what the odds were of that.  As it so happens, that's not a question you can answer rigorously at all, without knowing the priors.  But perhaps you can rigorously answer

Q1: What were the odds of drawing a matching pair of candies?

I reached in again, and this time pulled out a cherry and a grape; I did it again, and pulled out a matching pair of grapes.  So this time, I thought, for sure there must be a change in the odds of drawing a match, but when I looked in again, the odds were once more exactly the same as the first time.  What's more, I reached in again, pulled out a pair of green apples, looked in one last time, and the odds were again exactly the same as before!

Q2: Knowing there were no blue raspberry candies at all, how many of each of the other flavors were there, before I pulled out the first pair of green apples?

In Crude Homage to Edna St Vincent Millay

[From my Facebook page, originally written in February 2010, and here lightly edited.  I've been thinking about posting poetry here a bit, especially as it's National Poetry Month and all.]

Sonnets are convenient lunchtime reading material: short, yet dense with rhythm and sense (when reasonably well written). I've been working my way haphazardly through a collection of sonnets by Edna St Vincent Millay, one of the great romantic poets—at least, so say those who would know. Not to put too fine a point on it, I like them. What's more, I've been informed that it is a prominent chick-lit marker for the protagonist taking herself (over) seriously when she reads or even quotes poetry by Millay.

Well, I am nothing if not self-aggrandizing (often in the guise of self-deprecation), so despite my obvious gender challenge—being a guy—I have taken it upon myself to attempt a quasi-imitation of Millay. ("Aping" might be more apt a word.) I have used, as she does, the sonnet form (of a fittingly quasi-Petrarchan variety), and I have also taken as my subject unrequited affection, a common enough Millay theme. I have not, however, tried generally to affect the effortless facility with which she, Yoda-like, twists normal English word order like a pretzel. (I believe that the subject is permitted to precede the predicate at most once per stanza.)

By the way, Millay's name being two and a third dactyls lends itself conveniently to the limerick form. So as a kind of appetizer, and by way of introduction:

To Ms Edna St Vincent Millay,
I now offer this humble assay.
    For her sonnets are kings
    Of romantical things
And just what they're about none can say.

And perhaps you'll find that you like the appetizer better than the main course anyway.

in crude homage to edna st vincent millay

Your lips not once did tender mine, and yet
I loved you—no, and never once your hand
grasped mine in supplicating fever, and
I loved you still—nor even did you let
your eyebrows knit, or mouth to trembling set,
and still I loved you. (Once, perhaps, unplanned,
to quell persistent pity's keen demand,
you touched my head, as one would with a pet.)
Thus singularly blessed I count those days
where in a wondrous haze I hoped (or guessed)
that glances cast in jest were courting plays
to clasp in rapt amazement to my breast.
    And so I say—in seeking Love's mad thrall—
    you loved me best who loved me not at all.

Copyright © 2010 Brian Tung

EDIT: This sonnet can be considered a kind of lame reply to this one by Millay.

Mad as March

Note: This post has been updated to correct some of the probability figures, and to mention UMBC's defeat of Virginia in the 2018 tournament.

 

Hey, it's March, it's mad, it's March Madness!

Which means that there's math, too.

I was inspired to write math this time (as opposed to all those other times) by a short video in which some mathematics guy explained why filling out a perfect bracket (ignoring the "First Four" and focusing only on the 64 teams in the "real" tournament) is so hard.  According to him, it's because there are 63 games, each one eliminating one of the 64 teams, each of which has to be prognosticated correctly in a perfect bracket.  The number of possible brackets is therefore 2 to the 63rd power, or about 9 times 10 to the 18th power.  And so the odds of filling out a perfect bracket is 1 in that enormous number.  Even if everyone in the whole world filled out a bracket, the odds are still a billion to one against anyone getting it all right.

As viewers too numerous to list pointed out (correctly), this line of reasoning is entirely bogus because it assumes that each of the 63-game sequences is equally likely.  Of course they aren't.  Higher seeds are more likely to win their games than lower seeds.  In particular, in the 28 years they've had 64 teams in the tournament, no 16 seed has ever beaten a 1 seed.  That doesn't mean it's impossible, or that it'll never happen, only that it's very unlikely on a game to game basis.  Eventually, though, it's inevitable, provided the tournament goes on year after year. (ETA 2024-03-29: Sure enough, it's happened twice in the last several years. In 2018, the 16th seed University of Maryland Baltimore County Retrievers beat the top seed Virginia Cavaliers by twenty, 74–54, and in 2023, the 16th seed Fairleigh Dickinson Knights beat the top seed Purdue Boilermakers by the more sedate score of 63–58. Both Cinderellas went on to lose their second-round matchups, though.)

The upshot is that certain brackets are more likely to be correct than others, and I've even heard tell that people have filled out perfect brackets in the past.  So I wondered to myself: What are the odds of someone filling out a perfect bracket?

To estimate that (because this really isn't something you can determine empirically), I had to construct a model for simulating tournaments.  This has to be done because although there are plenty of statistics for how often a 5 seed beats a 12 seed (because that pairing always meets four times in the first round, once for each of the four regions), there aren't going to be statistics for how often a 5 seed beats a 14 seed, because that could only happen in the regional finals, after both teams have defeated three teams (mostly teams better than they are), which is highly unlikely.  In fact, I'm not sure that it's ever happened.  I needed a model that would be reasonably simple to calibrate, quick to evaluate, and was generally applicable to any pair of seeds.

The model I decided upon, fairly quickly, works as follows.  Each team has a certain "strength," which depends only on its seeding.  Then, if teams A and B meet, one with strength SA and the other one strength SB, the probabilities of each of them winning are given by

P(A wins) = SA / (SA+SB)
P(B wins) = SB / (SA+SB)

Fairly straightforward. (ETA 2024-01-21: This turns out to be the Bradley-Terry model. I'm sure it's been independently reinvented many times, since it's such a natural idea.) I calibrated it by finding statistics on how often teams of different seeds made it to various stages of the tournament.  I was a bit surprised, actually, by some of the statistics. I had imagined that the chances of winning the first-round game would decrease very little from the 1 seed down to about the 4 seed or so, and then accelerate quickly down to about the 13 seed, and then decrease very slowly again.  (I was aware that there were some seeds that historically have won more often than you might expect, such as the 12 seed, but I assumed those were statistical anomalies that one could reasonably expect to show up in only thirty years of history.  In particular, I did not want to assume that 12 seeds, for instance, were magically better than 11 seeds, or even 5 seeds.  I assumed seeds properly reflected relative talent.)

But no such pattern appeared.  Instead, the probability of winning the first round seems to decrease fairly steadily from the 1 seed down to the 16 seed.  The 12 seed teams do seem to win slightly more than you might expect, but they win no more often than do 11 seeds.  So here, at least, the 12 seed bump wasn't great.  (EDIT: Ha!  Both 12 seeds playing on the first day of the 2013 tournament won: the Oregon Ducks, and my California Golden Bears.  Further EDIT: And now 12th-seeded Ole Miss.  And 13th-seeded La Salle, for that matter.)

While I was trawling for these statistics, by the way, I also came upon the assertion that the way teams were seeded (and in particular, not re-seeded after each round) placed a penalty on the middle seeds, so that the 12 and 13 seeds, it was claimed, were in some cases likely to advance further than the 8 and 9 seeds, for instance.  I thought it might be interesting to see if that came out of the model.

Anyway, as a result of these statistics, I came up with the following strengths for the 16 seeds:

1, 1/2, 1/3, 1/4, 1/5, 1/6, 1/7, 1/8, 1/9, 1/10, 1/11, 1/13, 1/17, 1/25, 1/41, 1/73

You may notice that these strengths imply that a 16 seed will win the first round 1/74 of the time.  (But they never win, I can hear you saying.  Nonsense.  You're only saying that because no one ever has. ETA: It happened! In 2018, the 16 seed University of Maryland, Baltimore County defeated the 1 seed Virginia. As of this writing, before the 2023 tournament, I think that makes the 16 seed one for 148, or exactly half as often as predicted by my wholly ex recto model.)  As you can see, the top 11 seeds have strengths that decrease harmonically—that is, as the reciprocal of the seed.  After that...well, maybe if you're dorky enough, you'll see what the pattern is.

To be sure, I don't really know how accurate this model is, largely because (as I mentioned previously) statistics for many of the match-ups just don't exist, or at least don't exist in sufficient quantity.  But since I'm taking the results with a grain of salt (I only need rough order-of-magnitude estimates), it only has to be moderately accurate for it to do what I want.

Anyway, my simulation engine runs through each of the 32,768 possible regional brackets (each of the regions is identically seeded) and determines how likely each bracket is, and how far each seed got in that bracket.

The results were sort of interesting.  In the first round, there are no notable oddities, which makes sense because the better teams always play against worse teams, so the higher a team is seeded, the more likely it is to win the first round.

1 seed wins First Round with probability 0.986486
2 seed wins First Round with probability 0.953488
3 seed wins First Round with probability 0.892857
4 seed wins First Round with probability 0.809524
5 seed wins First Round with probability 0.722222
6 seed wins First Round with probability 0.647059
7 seed wins First Round with probability 0.588235
8 seed wins First Round with probability 0.529412
9 seed wins First Round with probability 0.470588
10 seed wins First Round with probability 0.411765
11 seed wins First Round with probability 0.352941
12 seed wins First Round with probability 0.277778
13 seed wins First Round with probability 0.190476
14 seed wins First Round with probability 0.107143
15 seed wins First Round with probability 0.046512
16 seed wins First Round with probability 0.013514

(Remember to take all those digits with a sizable grain of salt.)  The second round is where it gets interesting.  Consider a moderately lower seed, like the 12 seed.  If it happens to win its first round, its second round game will be against either the 4 seed or the 13 seed.  It's likely to be against the 4 seed, but not overwhelmingly so; it will be the 13 seed about 19 percent of the time.  In that latter case, the 12 seed will actually be a slight (57 percent) favorite in the second round.  But even if it meets up against the 4 seed, it will be an underdog, but not a prohibitive one.  In such match-ups, the 12 seed beats the 4 seed about 24 percent of the time.

Compare that to one of the middle seeds—say, the 8 seed.  If it reaches the second round, it has to play against either the 1 seed or the 16 seed.  Not only is the 1 seed overwhelmingly likely to win its first round match-up, but it is also a much stronger opponent for the 8 seed than the 4 seed was for the 12 seed.  As I mentioned above, this happens because the teams are not re-seeded after each round, with the best of the surviving teams playing the worst of the surviving teams, the second best playing the second worst, and so on.  The moral of this story is that as far as the Sweet Sixteen is concerned, the pundits are right: The middle seeds are (slightly) cursed!

1 seed reaches Sweet Sixteen with probability 0.882035
2 seed reaches Sweet Sixteen with probability 0.763414
3 seed reaches Sweet Sixteen with probability 0.632753
4 seed reaches Sweet Sixteen with probability 0.496767
5 seed reaches Sweet Sixteen with probability 0.366148
6 seed reaches Sweet Sixteen with probability 0.248486
7 seed reaches Sweet Sixteen with probability 0.148009
8 seed reaches Sweet Sixteen with probability 0.064476
9 seed reaches Sweet Sixteen with probability 0.052084
10 seed reaches Sweet Sixteen with probability 0.080832
11 seed reaches Sweet Sixteen with probability 0.093788
12 seed reaches Sweet Sixteen with probability 0.082892
13 seed reaches Sweet Sixteen with probability 0.054193
14 seed reaches Sweet Sixteen with probability 0.024973
15 seed reaches Sweet Sixteen with probability 0.007745
16 seed reaches Sweet Sixteen with probability 0.001405

Now that I think about it, I think it's this bump for the 10 through 13 seeds that accounts for their "upset" reputation, more than their success in the first round.

The trend continues, though with decreased intensity, in the third round, in order to reach the Elite Eight (although notice that there's a bump at both the 6 seed and the 10/11 seed)...

1 seed reaches Elite Eight with probability 0.732698
2 seed reaches Elite Eight with probability 0.510341
3 seed reaches Elite Eight with probability 0.302688
4 seed reaches Elite Eight with probability 0.127560
5 seed reaches Elite Eight with probability 0.081095
6 seed reaches Elite Eight with probability 0.081461
7 seed reaches Elite Eight with probability 0.056441
8 seed reaches Elite Eight with probability 0.025441
9 seed reaches Elite Eight with probability 0.019169
10 seed reaches Elite Eight with probability 0.024748
11 seed reaches Elite Eight with probability 0.020596
12 seed reaches Elite Eight with probability 0.009123
13 seed reaches Elite Eight with probability 0.004812
14 seed reaches Elite Eight with probability 0.002918
15 seed reaches Elite Eight with probability 0.000807
16 seed reaches Elite Eight with probability 0.000101

...but interestingly, it's essentially gone by the time one reaches the Final Four.

1 seed reaches Final Four with probability 0.535913
2 seed reaches Final Four with probability 0.222277
3 seed reaches Final Four with probability 0.106313
4 seed reaches Final Four with probability 0.053660
5 seed reaches Final Four with probability 0.030044
6 seed reaches Final Four with probability 0.018613
7 seed reaches Final Four with probability 0.011601
8 seed reaches Final Four with probability 0.006982
9 seed reaches Final Four with probability 0.004848
10 seed reaches Final Four with probability 0.003929
11 seed reaches Final Four with probability 0.003042
12 seed reaches Final Four with probability 0.001761
13 seed reaches Final Four with probability 0.000753
14 seed reaches Final Four with probability 0.000221
15 seed reaches Final Four with probability 0.000039
16 seed reaches Final Four with probability 0.000004

There is a bit of an inflection in the curve at about the 10 seed, but it's still monotonically decreasing across all seeds.

Now, one might think that this is just an artifact of the strengths I chose, somewhat arbitrarily, and that either the trend itself, or its vanishing by the Final Four, might not arise with a different set of strengths.  For what it's worth, I thought that myself, and tried running the simulations with different sets of strengths.

As it turns out, with any reasonable set of strengths that I chose, the trend of the middle seeds being somewhat worse off at the Sweet Sixteen than the moderately lower seeds—that trend might arise or not, but if it did, it always disappeared by the Final Four.  I didn't find any set of strengths which retained the trend all the way through to the Final Four.  Heuristically, I think this is because by the time you get to the regional finals, you have to play the best teams in the entire bracket—you can't avoid anyone for sure.  So if your goal is to reach the Final Four, then have no fear: I don't think the lack of re-seeding significantly hurts you if you're in the middle seeds.  Your answer may be different, of course, if your goal is simply to make it to the Sweet Sixteen.

Oh yes, the question that first stimulated this exploration: What are the odds of filling out a perfect bracket?  Well, given the strengths as I initially had them, the most likely bracket is the one where all the favorites win every game.  For each region, this happens about one time in 123; since there are four regions in the entire bracket, the odds on the ultimate "chalk" bracket are that raised to the fourth power, or about one time in 225 million. That leaves the Final Four. Since any seeds can meet there, we'll simplify things and just assume that all three games can go any way, leading to an eight-fold increase in the number of overall tournament brackets, or 1.8 billion.

Some people, not accustomed to thinking through probability, will point out that no bracket has ever turned out perfectly chalk (which is true) and suggest that a slightly off-chalk bracket is individually more likely (which isn't).  One must not confuse "most likely" with "likely."  The reason that each year the tournament turns out slightly off-chalk is that there are enormously more off-chalk brackets than chalk ones.  (Strictly speaking, of course, there is only one perfectly chalk bracket.)  The fact that these off-chalk brackets are slightly less likely than the pure chalk bracket is more than compensated for by their superior numbers.

Anyway, there are a lot of brackets filled out each year, so given that the odds on the chalkier ones are probably not too much worse than 1 in 1.8 billion, it wouldn't be surprising if somewhere along the way, someone did end up filling out a perfect bracket. As far as we know, however, it hasn't happened.

Note: By the way, if you've only a passing familiarity with sports, you may wonder what I mean by "chalk."  Chalk is a sports betting term that refers to favorites winning; the more favorites win, the chalkier the outcome.  I've heard that it came from betting lines on horse races, which were written up in chalk, but I've no good idea if that's actually so.  Anyone?

EDIT: Here's a good write-up on how the term came to be.

A Harry Potter Puzzler

I recently had occasion to put together a bit of a puzzle for a fellow math fiend on the occasion of his birthday.  If you enjoy Harry Potter and recreational math—I know that's a limited bunch, but it occurred to me this blog readership might just select a little for that—you may well like this small offering:

Gryffindor and Slytherin played a Quidditch match.

1. Alicia Spinnet scored the first goal of the match, giving Gryffindor its one and only lead of the match until the moment that Harry caught the Snitch, winning the match for Gryffindor. The match was, however, tied three times (other than at 0-0).
2. Gryffindor never scored two goals in succession; Slytherin always scored at least one goal in between. Furthermore, each pair of Gryffindor goals was separated by a different number of Slytherin goals.
3. Ginny Weasley and Katie Bell each scored a hat trick (three goals) for Gryffindor.
4. Each Gryffindor score was assisted by the Chaser who scored the previous Gryffindor goal. Each Slytherin score was also assisted by the Chaser who scored the previous Slytherin goal.
5. Katie Bell's second goal came one hour into the match. Slytherin scored twice as many goals after that point than they did before it. Interestingly, Graham Montague scored all of his goals before that point, Cassius Warrington scored all of his after that point, and Adrian Pucey scored more than the other two combined.

Who scored the last goal of the match, and what was the final score after Harry ended it?

(Muggles—non-magical folk—may find it helpful to know that in Quidditch, goals are worth 10 points apiece.  Play continues until a player catches the Golden Snitch, which is worth 150 points and ends the match.  There are no other ways to score points.  The team with more points at the end of the match wins.  Assists are passes from one player to a different player leading directly to that second player scoring a goal.  Finally, each team has three and only three Chasers, who score all the goals; the other players are two Beaters, a Keeper, and a Seeker.)