\chapter{KNOWING WHEN TO STOP}

\label{chapter_stopping}


  \begin{figure}[h]
  \begin{centering}
    \includegraphics[width=0.50\textwidth]{chap_stopping/optimal_love.png}
    \caption{To find Ms Right in 100 candidates, try 37 dates, then get serious!}
  \end{centering}
  \end{figure}

  
\section{Introduction}

A mysterious stranger has arrived in town with a deck of cards, and a wagonload
of gold.  He announces that he has decided to give away his fortune, by letting
each person in the town play a game.  He has a deck of ten blank cards.  On the
face of each card, he writes a number representing an amount in gold coins,
and then turns the cards face down.  Now he turns over the first card.
``Is this the card you want?'' he asks, and the player can either accept it,
winning the corresponding amount, or reject it.  If the player rejects that card,
the next one is turned over, and so on, until the player accepts a card, or
reaches the last card which is then, by default, the player's winnings.

A greedy player will naturally wish to be lucky enough to choose the very highest
card.  If the player decides in advance to choose a card at random, the seventh card, 
perhaps, then this strategy would have a 1/10 chance of correctly selecting the 
highest card.  But somehow, that doesn't seem the best strategy.  After all, that's 
the same as always picking the first card.  But it's hard to resist the feeling 
that you really ought to turn over some cards before making a choice.  Except that 
the price of seeing the next card is giving up the one you have.

The game would be easy if it was known in advance what numbers appeared on the
cards, so we will suppose the range is not known.  Even if we don't know the range, 
particular values such as ``1'' or ``2'' would almost certainly not be the maximum;
so to make sure the puzzle is hard, we will suppose that the card values are chosen 
in such a way that every card could be the maximum.  Here is a sequence of numbers
chosen in such a way.  
\begin{verbatim}
512   256   896   320   928    80   680   116   118   571
\end{verbatim}
Given 10 cards, we start with $2^9$, and then randomly 
add or subtract $2^8$ to get the next card, then randomly add or subtract $2^8$ and
$2^7$ to get the next card, and so on.  This guarantees that every card is equally
likely to be the maximum, and that the location of the maximum can never be determined
from the observed values of the preceding cards.

This is an example of what is called an {\it{optimal stopping problem}}.  Martin Gardner
described this problem as ``The Game of Googol''.  A variation, called ``The secretary
problem'', involves an employer seeking a secretary, who has scheduled interviews with 50 applicants,
and will either say ``Next!'' or ``You're hired, send the rest home!'' at the end
of each interview.  The problem has also been posed as a person wanting to get married;
a dating service has provided the names of 100 candidates, and the person, while
wishing to marry the best of the candidates, must date each in turn and either
accept that person, or permanently reject them and request the next candidate.
Here, the assumption is made, of course, that the candidate is willing to accept
the marriage proposal, and is not also simultaneously dating a number of people
looking for the best!

\section{An Optimal Strategy}

Surprisingly, a strategy can be devised which, on average, will select the highest
card, the best secretary, or the ideal mate about 37\% of the time.  Moreover,
this is true pretty much independent of $n$, the number of choices available. 
The strategy is in two parts:
\begin{packed_itemize}
  \item{examine, but reject, the first $k-1$ items;}
  \item{examine items $k$ through $n$, accepting the very first one whose value
  is greater than the first $k-1$.}
\end{packed_itemize}

For a given value of $n$, we can work out the probability that a given $k$ will
product the optimal value, and in fact, we can write a MATLAB function to do
this for us: 
\begin{lstlisting}
function p = high_card_exact ( n, k )
%% high_card_exact.m  
  p = ( 1 + ( k - 1 ) * sum ( 1 ./ ( k:n-1) ) ) / n;
\end{lstlisting}

For our mysterious stranger's game using a 10 card deck, the results are:
\vskip 0.1in
\begin{tabular}{|l|r|r|r|r|r|r|r|r|r|r|}
\hline
k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\hline
p(k) & 0.100 & 0.283 & 0.366 & 0.399 & 0.398 & 0.373 & 0.327 & 0.265 & 0.189 & 0.100 \\
\hline
\end{tabular}

The optimal value of $k$ for this problem is clearly 4.  But, except for very small
values of $n$, the optimal value can be well approximated by $k^* \approx \frac{n}{e}$,
which here would give us $k^* = 3.6788$, and in general, the chances that this strategy
will succeed are $p(k^*) = 1/3 = 0.3679$.

  \begin{figure}[h]
  \begin{centering}
    \includegraphics[width=0.75\textwidth]{chap_stopping/high_card_exact.png}
    \caption{The exact probability of winning high card with a deck of 100}
  \end{centering}
  \end{figure}

\section{A Sequential Simulation}

Let us assume that we know about the high card game, and wish to analyze it 
computationally.  We choose a deck size $n$, and then want to see how the
value of the skipping strategy for various skip values $k$.

When a human is playing the game, it's important to try to disguise the
range of values.  However, we'll assume the computer makes no conclusions from
the actual values displayed, so our deck of $n$ cards can simply be modeled as
a random permutation of the integers 1 through $n$. 

So our procedure will be, for each skip value $k$ from 1 to $n$, to simulate
$t$ realizations of the game using the given skip strategy.  If $h$ is the number
of times we picked the high card (which here will simply be the one labeled $n$),
then we estimate the probability of winning with skip $k$ as
\begin{displaymath}
  p(k) \approx \frac{h}{t}
\end{displaymath}

Given values of $n$ and $k$, a function to estimate $p$ could be:
\begin{lstlisting}
function p = high_card_estimated ( n, k, t )
%% high_card_estimated.m
  h = 0;
  for j = 1 : t
    cards = randperm ( n );
    margin = max ( cards(1:k-1) );
    for i = k : n
      if ( margin < cards(i) )
        if ( cards(i) == n )
          h = h + 1;
        end
        break;
      end
    end
  end
  p = h / t;
\end{lstlisting}

Of course, while the function is the key to the calculation, it only computes the estimated
probability for a particular value of $k$.  To judge what the optimal value of $k$ is, or to 
make a plot of the estimated probabilities, we would need to call {\it{prob\_estimat(n,k,t)}}
for each value of $k$ from 1 to $n$.

\section{A Parallel Simulation Using parfor}

If we wish to compute a table $p(1:n)$ of the probability estimates for each skipping
value, then we only need to add a simple loop to generate each $k$ and call the function.
Computing this data in parallel is therefore also quite easy, since the details are
hidden in the function; moreover, the fact that the function depends only on the fixed
numbers $n$ and $t$ and the loop index $k$ means it is almost certain that the computation is
suitable for parallel treatment.

Since the loop is so short, we'll include the calls that summon and dismiss the workers,
and suggest how the result vector can be displayed:
\begin{lstlisting}
%% high_card_estimated_call.m
  n = 100;
  t = 1000;
  matlabpool open local 4

  parfor k = 1 : n
    p(k) = high_card_estimated ( n, k, t );
  end
  
  matlabpool close

  plot ( 1:n, p, 'b-' );
  title ( 'Estimated winning probabilities for 100 card deck.' )
\end{lstlisting}

An plot of the results for the 100 card deck, estimated by 1,000 trials for each
skip value $k$, captures the general shape of the curve computed from the exact
formula, although it remains surprisingly irregular in detail.

  \begin{figure}[h]
  \begin{centering}
    \includegraphics[width=0.75\textwidth]{chap_stopping/high_card_estimated.png}
    \caption{The estimated probabilities, with a deck of 100, and 1,000 trials.}
  \end{centering}
  \end{figure}
  
As far as parallelism goes, however, there are several points to consider.  

A new feature of this example is that the {\it{parfor}} loop stores data into an array whose results
will be needed after the loop is completed.  This array is accessed by the loop parameter
in the simplest way.  Loops controlled by parfor impose some strict requirements on the
ways in which arrays can be used on the left or right hand sides of the statements they
control.  Luckily, using the loop index to access a vector is always legal!

A second thing to consider is that we parallelized on the skipping number $k$.  In fact,
there really are two loops surrounding the calculation; the other loop involves the
number of trials.  The fact that we buried the calculation inside a function obscures
this detail, which might have led us to consider reordering the loops, especially if $n$
was small relative to the number of processors, or if we actually only wanted to check
a few values of $k$, not the entire range possible.

Finally, note that the function {\it{prob\_estimat()}} invokes the random number generator.
In a sequential calculation, we should be comfortable with the idea that there is a single
generator with an internal state, and that each call to this generator both produces a
random value and advances the state.  What happens in a parallel calculation?  Does each
worker invoke a separate random number generator?  Does each random number generator
begin in the same state?  For some applications, this would cause unacceptable correlations
instead of the desired random behavior.  At the moment, we will only raise these issues,
to encourage you to see that moving from a sequential to a parallel system means that
sometimes you are probably only assuming that things work the way they should!


