New Mexico Occasionally people ask what I think about when I climb. On longer hikes, by yourself, there's a lot of time to think, if you choose to use your time that way. Even when others come along most of your time is your own.

I won't answer that question here. I'll just provide an answer.

 Christine and I followed a trail that looked roughly like the one at right up Όλυμπος. (Since I left the Όλυμπος map with her, this is actually from one of my New Mexico maps, but the point's the same.) Ceteris paribus, the points marked in red (and the approaches to them) will have roughly the same scenic views as you move along the trail.Look at the topo map until you believe.This switch-backing, confusing to the new hiker, reduces trail degradation and energy expenditure, while presenting a unique problem…

In the context of Όλυμπος, it meant that we repeatedly passed a view which looked like this.

As a photographer-hiker there's a problem here. Do you stop at each bend to take another picture? (Until your hiking partner is driven nuts.) Do you take a few representative shots? Do you satisfy yourself with one picture?

And then there's another problem which bothers me. As I explain it to other photographers, I think the mark of a novice photographer is taking a single photograph and thinking it's right. Your journeyman photographer knows that photograph isn't right and therefore takes a lot of photographs knowing one of them will probably hit it. The master photographer takes a single photograph, but this time, it is right.

But, how does the master photographer know?

Perhaps through his knowledge of the Sultan's Dowry Problem.

As Christine said at this point, "Δηλαδή;"1

I'll explain it to you as I explained it to her…

In the Sultan's Dowry Problem you meet the Sultan and somehow, after a night of carousing with him, find yourself presented with an "interesting" deal. The Sultan will let you marry one (and only one) of his one hundred very attractive sons.

The Sultan will let you check out his sons one by one. If you reject a son you will never, ever see him again. If you decide to marry a son then the Sultan performs the ceremony on the spot. Choosing not to marry anyone, divorcing later, or cheating on the son will probably result in the Sultan killing you.

What do you do?

First, let's lay out the rules more clearly.

 The Sultan's Problem The Photographer-Hiker's Problem A single son may be chosen. A single photograph may be taken. There are $n$ sons. There are $n$ scenic views. We know $n$, from the Sultan. We know $n$, from our map. The sons can be ranked from hottest to least hot with no ties. The views can be ranked from most to least scenic with no ties. The sons are presented sequentially in a random order. The views are presented sequentially in a random order.This can be considered true the first time we hike a trail. All orders are equally likely. All orders are equally likely. Each son will be accepted or rejected. Each view will be accepted or rejected. This decision can only be based on the relative ranks of the sons seen so far.There is no chance to make-out. This decision can only be based on the relative ranks of the views seen so far. Rejected sons are lost… forever. Rejected views are lost… forever.

So there are some assumptions going on. Knowing $n$ is an assumption, but a larger assumption is that we don't know anything about the distribution of rankings beforehand. While the Sultan can randomly order his sons, a trail can't randomly order its views. But, in the pictures above, you'll notice that elevation doesn't necessarily correspond to photo quality, so let's let these assumptions go… at least for now.

Our strategy will be to always meet and reject the first $r$ sons/views and then choose the next best son/view we meet. There are ways of showing that this is an optimal strategy, but we won't go into that here.

Using this strategy, what the odds of picking the best son/view?

Clearly, if we use this strategy and the best son/view (let's call it $B$) is one of the first $r$ we meet, then we "lose". If $B$ is not one of the first $r$ than whether we choose it or not will depend on where it lies.

If $B$ is the $r+1$ position than we win. This will happen with probability $\frac{1}{n}$.

Now, if $B$ is in the $r+2$ position, than we will win if the best candidate we've seen yet is not in the $r+1$ position; that is, if the best candidate we've seen out of the first $r+1$ was one of the first $r$. This happens with probability $\frac{r}{r+1}$. Of course, in this scenario we only win if $B$ is actually in the $r+2$ position, so the total probability of winning here is $\frac{1}{n} \frac{r}{r+1}$.

Similar ideas will be true for the rest of the positions and we have the terms:

$\frac{1}{n} \frac{r}{r+1},\frac{1}{n} \frac{r}{r+2},\frac{1}{n} \frac{r}{r+3},\frac{1}{n} \frac{r}{r+4},\frac{1}{n} \frac{r}{n-1}$

Since all these possibilities for the position of $B$ are mutually exclusive, they may be summed and we have the following:

$\frac{1}{n}(1 + \frac{r}{r+1} + \frac{r}{r+2} + \frac{r}{r+3} + … + \frac{r}{n-1})$

or

$\frac{r}{n} \sum{\frac{1}{j}}$, for r<=j<n

We may approximate this as an integral from $r$ to $n$ and get:

$\frac{r}{n} \sum{\frac{1}{j}} = \frac{r}{n} \int_r^j{\frac{1}{j}}$

$=\frac{r}{n} (\ln{n} - \ln{r})$

Now, for what value of $r$ is this probability maximized? Let's take a derivative with respect to $r$.

$\frac{d}{dr} (\frac{r}{n} (\ln{n} - \ln{r})) = \frac{d}{dr} (\frac{r}{n} \ln{n} - \frac{r}{n} \ln{r}) = \frac{1}{n} \ln{n} - \frac{1}{n} \ln{r} - \frac{1}{n}$

Setting this equal to zero gives us the maximum…

$\frac{1}{n} \ln{n} - \frac{1}{n} \ln{r} - \frac{1}{n} = 0$

$\ln{n} - \ln{r} - 1 = 0$

$\ln{r} = \ln{n} - 1$

$r = e^{\ln{n} - 1} = \frac{n}{e}$

So, the best son or view to choose is the $n/e$ view where e is nautral log base. And $1/e$ is the probability that this strategy will work. Using this strategy you'll end up with the hottest son or the best photograph (given the constraints) a surprising 36.7% of the time! Incidentally, if you have one hundred sons or one hundred scenic views, than you should reject the first 37 of them and then choose the next best one (given the constraints).

So now Christine knows how to choose a hot guy, the master photographer knows which picture to take, and you know at least one thing I've thought about.

1 Her favourite Greek word, translating to "namely" or "and that is".

Check if this is a private message just for Richard: