Optimal stopping

From Wikipedia, the free encyclopedia

The theory of optimal stopping is concerned with the problem of choosing a time to take a particular action, in order to maximise an expected reward or minimise an expected cost. Optimal stopping problems can be found in areas of statistics, economics, and mathematical finance (related to the pricing of American options). A key example of an optimal stopping problem is the secretary problem. Optimal stopping problems can often be written in the form of a Bellman equation, and are therefore often solved using dynamic programming.

[edit] Definition

Stopping rule problems are associated with two objects:

  1. A sequence of random variables X1,X2,..., whose joint distribution is something assumed to be known
  2. A sequence of 'reward' functions (y_i)_{i\ge 1} which depend on the observed values of the random variables in 1.:
    yi = yi(x1,..,xi)

Given those objects, the problem is as follows:

  • You are observing the sequence of random variables, and at each step i, you can choose to either stop observing or continue
  • If you stop observing, you will receive reward yi
  • You want to choose a stopping rule to maximise your expected reward (or equivalently, minimise your expected loss)

[edit] Examples

Coin tossing ((yi) converges)

You have a fair coin and are repeatedly tossing it. Each time, before it is tossed, you can choose to stop tossing it and get paid (in dollars, say) the average number of heads observed.

You wish to maximise the amount you get paid by choosing a stopping rule. If Xi (for i ≥ 1) forms a sequence of independent, identically distributed random variables with distribution

Binomial\left(1,\frac{1}{2}\right),

and if

y_i = E((\sum_{k=1}^{i} X_k)/i),

then the sequences (X_i)_{i\geq 1}, and (y_i)_{i\geq 1} are the objects associated with this problem.

House selling ((yi) does not necessarily converge)
You have a house and wish to sell it. Each day you are offered Xn for your house, and pay k to continue advertising it. If you sell your house on day n, you will earn yn, where yn = (Xn − nk).
You wish to maximise the amount you earn by choosing a stopping rule.
In this example, the sequence (X_i) is the sequence of offers for your house, and the sequence of reward functions is how much you will earn.

Secretary problem ((Xi) is a finite sequence)

Main article: Secretary problem

You are observing a sequence of objects which can be ranked from best to worst. You wish to choose a stopping rule which maximises your chance of picking the best object.
Here, if R1,...,Rn (n is some large number, perhaps) are the ranks of the objects, and yi is the chance you pick the best object if you stop intentionally rejecting objects at step i, then (Ri) and (yi) are the sequences associated with this problem. This problem was solved in the early 1960 by several people. An elegant solution to the secretary problem and several modifications of this problem is provided by the more recent odds-algorithm of optimal stopping due to Thomas Bruss. See Odds-Algorithmus.

Search theory

Main article: Search theory

Economists have studied a number of optimal stopping problems similar to the 'secretary problem', and typically call this type of analysis 'search theory'. Search theory has especially focused on a worker's search for a high-wage job, or a consumer's search for a low-priced good.

[edit] References

 Please expand this article using the suggested source(s) below.
More information might be found in a section of the talk page.
  • Optimal Stopping and Applications, retrieved on 21/06/2007
  • Thomas S. Ferguson. "Who solved the secretary problem?" Statistical Science, Vol. 4.,282-296, (1989)
  • F. Thomas Bruss. "Sum the odds to one and stop." Annals of Probability, Vol. 28, 1384-1391,(2000)
  • F. Thomas Bruss. "The art of a right decision: Why decision makers want to know the odds-algorithm." Newsletter of the European Mathematical Society, Issue 62, 14-20, (2006)