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).