Shot Selection and the Secretary Problem

One of my favorite problems in all of recreational mathematics is the so-called secretary problem.  In this problem, you are interviewing a hundred candidates for a secretarial position.  For the purposes of discussion, we'll assume that the various candidates have a precise suitability rating, and of course, you want to maximize this rating for your hire.  Ideally, then, you'd interview all hundred candidates first, get their ratings, and then hire the best one.

Unfortunately, that's not the way things work in this problem.  You only get the candidates one at a time, and you have to decide then and there whether or not to hire them or not.  Once you've rejected a candidate, they're lost to you forever.  One could, theoretically, lose the best candidate on the very first interview.

The question then is, what is your best strategy, and what is your probability of making the best possible hire using that strategy?

(By the way, if you think this problem is formulated in a politically incorrect way, I first encountered it in a form called the sultan's dowry, in which a suitor for the sultan's daughters had to select the one with the largest dowry.  If he picked the right one, he got to marry her, but if he didn't—well, let's just say an unsuccessful suitor and his head are soon parted.  But it wasn't entirely unproductive; I eventually formulated a variation called the iterated sultan's dowry, in which a second suitor, seeing the first suitor's unsuccessful head roll down the hill, gets to use the information in choosing a prospective mate, and then the third, the fourth, etc.  This variation has an interesting solution which is unfortunately too large to fit into this parenthetical comment.)

It can be shown, fairly easily, that the best strategy must be of the form "Skip the first n candidates, recording their suitability ratings.  Then choose the next candidate whose rating exceeds theirs."  The reason is that as you plow through the candidates, the probability that the best one is yet to come never increases, whereas the probability that you've already encountered the best one never decreases.  So the question reduces to figuring out what the right choice for n is.

Ultimately, following a strategy like this, you could end up choosing no candidate at all if the best candidate is already in the first n, since you've already skipped all of those.  But if you do pick a candidate, it will be number k > n.

For that one to be the best overall, the best must be in the last 100-n.  Furthermore, the second best of the first k (that is, the best before the ultimate choice) must belong in the first n.  Now, let's work out the probability that both of these happen.  In order to do this, we have to break down the possibilities into all the different cases.

The first case is that the best candidate is the very next one—candidate number n+1—which happens with probability 1/100.  You'll choose that one provided that there's no other candidate between the first n and number n+1 that is better than the first n.  Since there are no candidates in between, that probability is 1.  So the incremental probability for this case is 1/100 times 1, or just 1/100.

The second case is that the best candidate is the one after that—candidate number n+2—which again happens with probability 1/100.  You'll choose that one provided that there's no candidate between the first n and number n+2 that is better than the first one.  That will be true provided the best of the first n+1 happens within the first n, so the incremental probability for this case is 1/100 times n/(n+1).

Following the same line of reasoning, the third case—that the best candidate is number n+3—provides an incremental probability of 1/100 times n/(n+2), the fourth case provides an incremental probability of 1/100 times n/(n+3), etc., until the last case—that the best candidate is number 100—provides an incremental probability of 1/100 times n/99.

Putting all these cases together, this strategy "wins" with probability 

n/100 × [1/n + 1/(n+1) + 1/(n+2) + · · · + 1/99]

It can be shown, using relatively straightforward calculus, that this expression reaches a maximum when n = 37, and yields a probability of success of about 0.37.

That's not a coincidence, incidentally.  For large candidate pools (and a hundred candidates qualify as a large pool), of size N, the best strategy is to skip the first n = N/e, where e = 2.71828+ is the base of the natural logarithm, and to take the earliest best candidate thereafter.  The approximate probability of success (that is, choosing the very best candidate of them all) is very close to 1/e = 0.36787+.

For a lot of people (including myself), that's rather stunning.  It implies that even if you have a million candidates, you have a strategy that picks the very best one of them with better than a one-in-three chance.

The reason I'm putting basketball in the mix is that there's a fairly straightforward application to a vital aspect of scoring: shot selection.

Consider: A possession in basketball lasts for anywhere from 0 to 24 seconds (neglecting offensive rebounds).  You can't always guarantee that you'll make the shot; the next best thing (at least before the endgame) is to select the very best shot—that is, the shot that has the best probability of going in (neglecting fouls and three-point shots).

 

In other words, ahem, optimal shot selection.

But you don't always know when that best shot is going to come, especially when you're working out of a halfcourt set.  Is it the very first one?  Is it the next best one?  Maybe the best one will come at least twenty seconds into the possession.  You just don't know.  But maybe, now, you have a rule of thumb for selecting that best shot.  You skip the ones that come in the first 24/e = 9 seconds (approximately), and take the next best one that comes thereafter.

Obviously, this rule makes lots of assumptions, such as (a) the defense is equally tenacious across the entire possession, (b) the offense is equally productive of shot opportunities across the entire possession, (c) the best shot opportunity is equally likely to come at any time during the entire possession, etc.  But to the limited extent that these assumptions are approximately valid, it's not a bad rule of thumb.  It suggests that the Phoenix Suns of the early-to-mid-2000s were a bit hasty.

But not by much.  Just a second or two.

Constructions with Compass, Straightedge, and Flatiron

There may not be many of you out there who remember high-school geometry fondly, but those of you who do probably share my appreciation for compass-and-straightedge constructions.  I (re-)started thinking about this today, when someone mentioned, jocularly, preparing for travel at Warp Cube Root of Two, and it occurred to me that this was one of the three classical things that one cannot do with compass and straightedge.

Those strangely intermediate folks who are at once unfamiliar with compass-and-straightedge constructions and yet not intimidated by their spectre may find the Wikipedia page a reasonable starting place.  But what I'm proposing today is something different, which I'm a bit startled hasn't been discussed more prominently: three-dimensional constructions.  I've had this in my virtual back pocket for a while; this seems as good an opportunity as any to pull it out for a looksee, and figure out if anyone else has encountered anything like this.

The idea here is to extend to three dimensions what ordinary compass-and-straightedge constructions do in two dimensions.  The first thing is to define the tools and rules for their use.  For instance, in two dimensions, the tools are a compass and straightedge (like a ruler, but with only one edge and no markings), and with them, one may:

1. Draw a line between any two distinct points.
2. Draw a circle with one point as the center, and any other point on its circumference.
3. Draw an arbitrary point on a line or a circle, or off it.
4. Draw the point at the intersection of two lines (if they intersect).
5. Draw the point (or two) at the intersection of two circles (if they intersect).
6. Draw the point (or two) at the intersection of a line and a circle (if they intersect).

That's it; that's all you're allowed to do.  With these restrictions, the Greeks discovered that it is possible to construct an astonishing variety of geometrical objects, but they were unable to construct three famous examples.  They were unable to construct the square root of pi (also known as squaring the circle); they were unable to trisect arbitrary angles (that is, construct an angle with one-third the extent of a given angle); and they were unable to construct the cube root of two (also known as doubling the cube).

It turns out that these are impossible, and can be proved to be so, using some notions from field theory.  That has not, of course, stopped people from submitting reams upon reams of alleged constructions of one of these three objects, all of which (you may be assured) are somewhere bogus.

But enough of that for now.  In three dimensions, the canvas is not a flat plane, as it is in two dimensions, but all of space.  And we introduce a new tool, which I will call a flatiron, which permits you to draw planes.  The flatiron rules are as follows; in addition to the above, one may:

1. Draw the unique plane containing any three non-collinear points.
2. Draw a sphere with one point as the center, and any other point on its surface.
3. Draw an arbitrary point on a plane or a sphere, or off it.
4. Draw the line at the intersection of two planes (if they intersect).
5. Draw the circle (or point) at the intersection of two spheres (if they intersect).
6. Draw the circle (or point) at the intersection of a plane and a sphere (if they intersect).
7. Draw the point (or two) at the intersection of a line or circle with a plane or sphere (if they intersect).

As an example of what one might do in a three-dimensional construction, consider the following fairly simple task: Given points P and Q, construct a regular tetrahedron with PQ as edge.  We proceed as follows:

1. Draw spheres of radius PQ around both P and Q.
2. Draw the circle C at the intersection of spheres P and Q.
3. Draw R, an arbitrary point on circle C.
4. Draw a sphere of radius PR around R.
5. Draw S, one of the two points of intersection between circle C and sphere R.  PQRS is then a regular tetrahedron.

It should be straightforward to see that one may construct a regular cube as well.  Does this mean that one can construct the cube root of two in three dimensions?  I suspect not, although I cannot yet prove this.

So, a couple of questions, one easy, and one not so easy:

1. Suppose that indeed, the cube root of two is not constructible in three dimensions.  What about the fourth root of two?  In which dimensions might that be constructible?
2. Is it possible to construct all five of the regular polyhedra?  In addition to the tetrahedron and cube, these include the regular octahedron (eight faces), dodecahedron (twelve faces), and icosahedron (twenty faces).

 

It's True

This man has no gut.

Could You Be a Crackpot?

Of course not!  That's why I invented the following barometer for identifying crackpots, so you'll see how much you're not a crackpot.  This won't take long.  Just read the following essay, then answer the question afterward.

You have always, from an early age, been fascinated by the workings of the universe.  For longer than you can remember, the suspicion that something is amiss in the prevailing scientific theory has gnawed at you, but only recently, in your maturity, have you recognized how to rectify its flaws.

This is no patchwork repair—it is a fundamental revision in how to perceive the universe.  You have discovered this shift by virtue of your stark insight, uncluttered by years of outdated academic instruction.  You have been labelled a crackpot, but this has always been the mark of the true genius.  Witness Galileo: He had to withstand the prejudices and superstitions of his time, even amongst his colleagues, in his pursuit of the truth!  And you, like Galileo, are no crackpot.

Your breakthrough must be distributed personally, as part of a grass-roots campaign, in order to avoid the censorship that is part and parcel of the mainstream scientific press.  But you have no doubt that you will succeed; you are brave enough to face the naysayers who have shouted down other talented scientists who lacked your resolve.  Witness Einstein: His original mindset differed from the battered viewpoint that jealous criticism reduced him to!  You can quote effectively from his writings to support this.

The prevailing scientific theory requires—in fact, relies crucially on—a body of mathematics that was clearly invented ad hoc: for the purpose of showing exactly that for which it was invented.  This circular line of reasoning is a basic but crushing flaw.  Your alternative, for those who have the vision to properly appreciate it, is conversely a work of great elegance and beauty, which resonates with rather than challenges your acute intuition.

When at last it is properly recognized, your breakthrough will enable great boons for humanity.  You will be offered vast rewards for your work, but you will turn most of them down, asking only to continue your scientific investigations without the further distraction of interacting with the scientific community.  Those who doubted you will permit this reluctantly, out of respect for your talent, but all the while will admire your work from afar.

OK, now that you've read that (haven't you?!), here is your one question:

On a scale of 0 to 10—0 indicating complete disagreement and 10 indicating complete agreement—how well does the foregoing essay represent your viewpoint?

Scoring:

10: You are a crackpot.
0-9: You are not a crackpot.  True crackpots are in for a pound if they're in for a penny.

The Myth of Common Sense

How many times have you heard someone say, "It's just common sense"?  I just heard it myself (well, read it in an e-mail) two days ago, and it was in relation to something that I might argue wasn't really common sense at all—at least, not beforehand.  With the benefit of hindsight, it became common sense.  (If you're inordinately curious, it had to do with how hot a playground surface could get on a cool day.  Pretty hot, as it turns out.)

Right now, as I write this in late June 2011, if you google "it's just common sense," you get the following things that are supposed to be common sense:

• Domestic drilling for oil
• Creation science (I think—the post wasn't entirely coherent)
• The necessity of broad-ranging budget cuts
• Wearing a bicycle helmet reduces the risk of injury
• The use of backscatter scanners (so-called "naked X-rays")
• Avoiding texting while driving
• Essentially any Republican viewpoint on fiscal policy
• Showing discretion on social networks
• Allowing schoolteachers to bring guns to class (!)
• Using alternative medicine

Those are just the first ten hits that made an assertion that something or some position was "common sense."  I ignored any example that used the term in an ironic sense (most notably, "Repeal child labor laws?  It's just common sense!"), or were talking directly about common sense.

Now, one thing I expected was that there would be a split between things that were asserted to be common sense in a descriptive way (that is, people do commonly agree on them, or would if they were asked), and those that were asserted to be common sense in a prescriptive way (that is, people should agree on them).  And indeed there is, but the split was fairly unbalanced: I'd say that out of the ten hits I listed above, just three—the bicycle helmet one, texting while driving, and discretion on social networks—were even close to the descriptive sense, and the bicycle helmet one only alluded to common sense to set up the contrasting finding that apparently, it doesn't reduce the risk of injury.  (Very interesting, by the way.  But a post for another time.)

The remainder were all prescriptive; in general, they even conceded that a large segment of the population—be it liberals, non-religious people, gun-control advocates—were opposed to their viewpoint, but they then went on to say that these people were mistaken, and they were mistaken because they went against common sense.  In most cases, they don't really explain why their viewpoints were common sense; it was enough to say simply that they were.

And that demonstrates the appeal of saying that something is common sense: It removes the burden of proof from the person making the assertion, and places it on anyone who disagrees with it.  Essentially, it abdicates any responsibility for backing up your position.  More than that, it demeans anyone who disagrees, as they obviously lack common sense (whatever that might be).

Granted, it's always been a bit hazy exactly who has the burden in any particular case.  The negation of an assertion is, of course, another assertion, so who really has the burden of proof?  A convenient rule of thumb is that anyone who goes against the conventional wisdom position (the descriptive common sense, basically) assumes that burden, but there are, I'm sure, plenty of exceptions to that.  But I argue that in any borderline case, where there's some dispute as to who has the burden of proof, both sides should assume that burden.

So when someone writes that something is "just common sense," it almost always turns out (and I'm being as generous as I can here) that they don't exactly know why they hold their position.  Or won't say.  Or it's just too much trouble to actually work out and explain what their position is.  To which I'd say, "Well, then, why are you wasting your time explaining your common-sense position?"

To its credit, the bicycle helmet post actually points this out.  From Doug's Darkworld:

"It’s just common sense" is probably one of the most seductive and deadly false arguments out there. When someone says "it’s just common sense" what they are really saying is "reality conforms to my idea of what makes sense."

I would say there's other cases, but that is a big reason that people say something is common sense.  It puts me in mind of a point made by Michael Shermer.  Shermer's a skeptic of possibly the most compelling kind: a recovering occultist (an anti-skeptic, if you will).  He wrote a book in 1997 entitled Why People Believe Weird Things; he updated it five years later, most significantly including a new chapter entitled "Why Smart People Believe Weird Things."  In it, he argues the following thesis: Smart people believe weird things because they are skilled at defending beliefs they arrived at for non-smart reasons.

I can't emphasize strongly enough what a transforming revelation that was for me.  For much of my life, I'd encounter people holding what (to me, at least) appeared to be some kooky position or another, and my reaction was nearly always something along the lines of "How can you possibly believe that?"  And that was a rhetorical question; I wasn't really interested in how they came to believe that, I just wanted to point out that it was a nonsensical position.  As you might expect, I eventually came to realize that most people didn't particularly take kindly to that sort of question, so I stopped saying it.  But I still thought it.

Shermer's thesis, however, made me start asking that question again, but internally, and this time at face value: Why do they hold that position?  It's very often not for the reason they espouse.  (For instance, most of the common sense cases, I pointed out, are not in fact commonly held.)  Maybe it's because of their own personal experience; people tend to overvalue personal experience.  Maybe it's because of their religious or cultural upbringing.  Or maybe it's a position that has to be taken in order to avoid cognitive dissonance with something that they've done.  It's an interesting intellectual exercise, and sometimes I can work it out without coming straight out and asking them, "Well, why do you think it's common sense?"

But the other lesson is important, too: When someone says something is common sense, and that you should act in such-and-such a way because of it, it's vital not to adopt that common-sense attitude, if you don't already agree with it.  It can be surprisingly compelling, if you're not careful (after all, who wants to be demeaned?), and you may sooner rather than later find yourself espousing the same position, seeing as it's "just common sense."

When Does It Start?

So I'm driving to work the other day, and I'm stuck behind this car whose driver has decided that today, freeways shall be traversed at the speed of 42 mph.  (In reality, I suspect this decision applies to most days, but I'm trying to be conservative here.)  And it's almost impossible to pass him, because the stream of cars passing both of us is too dense and too much faster than we are to enter safely.

Eventually, I manage, and at a relatively safe moment, I cast a quick sidelong glance at him and affirm that he's northward of 80 years old.  Now, there's a lot of talk that drivers that old should be looked at fairly hard and often to establish that they're able to drive safely, but I'm actually not thinking about that.  What I'm thinking about is, at what point did he become a 42 mph kind of driver on the freeway?  Was he always like that, or did he start out as what most of us would consider an ordinary kind of driver, and over time got slower and slower?  I mean, maybe there are places where 42 mph is considered sort of daring, and that's where he grew up.

At this point in the discussion, someone invariably pipes up and mentions that such drivers are in fact safer than those driving at some higher speed, say, 80 mph, on the assumption that 80 mph is just inherently less safe.  There's something to be said for that point of view, in that there's less time to avoid impacts if you're driving at a higher speed, and any impacts you do end up in are more dangerous.  But that's only part of the picture.

The reality of the situation is that although (in Los Angeles) the freeway traffic occupies a continuum of speeds, most of the traffic—perhaps 90 to 95 percent—falls between 60 and 80 mph.  And your risk of impact depends primarily on how often you encounter cars travelling at that range of speed.  A long time ago, in grad school, I spent a little time figuring out how often you encounter cars on the road: either passing slower cars, or being passed by faster ones.  And what I found was that the details of the speed distribution of cars matters very little.  There are only four parameters of interest: the density of cars on the road, the percentage of cars you're faster than, the average speed of those cars that you're faster than, and the average speed of those cars that are faster than you.

That means that you could pretty much figure out the rate at which both my 42 mph driving friend and the hypothetical 80 mph driver would encounter cars by simply assuming everybody else was driving 70 mph.  Our superannuated man behind the wheel would encounter cars nearly three times more often than the 80 mph driver, and encounter them at nearly three times the relative rate of speed.  To be sure, the combined energy of an actual collision would be greater for 70 mph and 80 mph than it would be for 42 mph and 70 mph, but the increased frequency of encounters and the much shorter period of time drivers would have to avoid them would, I think, more than compensate for that.

All in all, I think if you want to drive slower to be safer, you're better off driving 60 mph, or whatever the lower end of speeds is for your road of choice.

A Different Kind of Search

Because I have a bad habit of imagining all sorts of bizarre, improbable scenarios, I dreamt up this one: Suppose I woke up in a strange town, with no idea of who I was or where I came from, or indeed of any of my past. How do I find out?

Of course, I might go to the police or something like that, but perhaps they'd be no more helpful than myself. So I imagined I might start a blog, mostly unlike this one, where hopefully someone would recognize me. I'd start out by saying I'm most likely a missing person. Over time, as I remembered more about my past, hopefully, I'd start putting that down in the blog. Ordinary blog stuff I'd post much as anyone would, but all the identifying information I'd collect in a single post, accumulating edits, so it'd be more easily indexed by Google.

But what kind of stuff would be useful identifying information?

It occurred to me that the usual "obvious" stuff isn't necessarily all that useful in a case like this. My height and weight are not really specific enough to be a useful filter if someone else were looking for me. There are about 100,000 active missing persons in the U.S. (as of the end of 2009, according to the FBI); there must be hundreds that are my height and weight, or thereabouts. A picture would be more distinguishing, but it's hard to search for a picture of someone if all that's known is that they're missing.

So I think I'd try to post stuff that's more distinctively me. Maybe I'd somehow realize that I like to play jazz piano, or enjoy recreational mathematics, or have a rather deep interest in sports and statistics. Maybe I'd recollect some piece of poetry I'd memorized (or even composed). Along with any other more personal tidbits, I'd put them all in my Google flypaper for my old identity.

OK, obviously, I'm surpassingly unlikely to ever need to do anything like this (and it's unclear whether or not this planning would be something I'd remember if I ever did), but then it also occurred to me: Why don't we post this kind of information when we're looking for someone?

When a missing person poster is put up in my neighborhood, it always gives out some basic statistics for them, but the information is mostly generic: a photo, name, date of birth, height, weight, date missing, etc. If a person is amnesiac or doesn't wish to be found, that information is nearly useless—even the photo, since the person may have changed appearance quite dramatically.

What about favorite activities? What about peculiar habits or reflexes? What about a recording of the person's voice? Even people who have forgotten who they are, or wish others would, would not easily change such essential characteristics of themselves. And with the Web as adjunct for missing persons posters, putting up a voice recording is simplicity itself. I'm not suggesting that anything be put up that the family not be comfortable with, but lots of this stuff would violate privacy but little, and would (it seems to me) provide substantial aid in finding the missing person. I'm sure it's done to some limited extent—some posters do list some minor personal details—but a casual survey of local posters shows precious little of it. Can anyone explain why this isn't done more, if only on a voluntary basis? I know if a family member went missing, I'd want the poster to have as much trivial (i.e., non-security) detail as possible on it.