World Library  
Flag as Inappropriate
Email this Article

Optimal stopping

Article Id: WHEBN0007189886
Reproduction Date:

Title: Optimal stopping  
Author: World Heritage Encyclopedia
Language: English
Subject: Robbins' problem, Search theory, Mathematical finance, Odds algorithm, Mihail Zervos
Collection: Decision Theory, Dynamic Programming, Mathematical Finance, Mathematical Optimization, Sequential Methods
Publisher: World Heritage Encyclopedia

Optimal stopping

In mathematics, 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.


  • Definition 1
    • Discrete time case 1.1
    • Continuous time case 1.2
  • Solution methods 2
  • A jump diffusion result 3
  • Examples 4
    • Coin tossing 4.1
    • House selling 4.2
    • Secretary problem 4.3
    • Search theory 4.4
    • Option trading 4.5
  • See also 5
  • References 6
  • External links 7


Discrete time case

Stopping rule problems are associated with two objects:

  1. A sequence of random variables X_1, X_2, \ldots, 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.:
    y_i=y_i (x_1, \ldots ,x_i)

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 at step i, you will receive reward y_i
  • You want to choose a stopping rule to maximise your expected reward (or equivalently, minimise your expected loss)

Continuous time case

Consider a gain processes G=(G_t)_{t\ge 0} defined on a filtered probability space (\Omega,\mathcal{F},(\mathcal{F}_t)_{t\ge 0},\mathbb{P}) and assume that G is adapted to the filtration. The optimal stopping problem is to find the stopping time \tau^* which maximizes the expected gain

V_t^T = \mathbb{E} G_{\tau^*} = \sup_{t\le \tau \le T} \mathbb{E} G_\tau

where V_t^T is called the value function. Here T can take value \infty.

A more specific formulation is as follows. We consider an adapted strong Markov process X = (X_t)_{t\ge 0} defined on a filtered probability space (\Omega,\mathcal{F},(\mathcal{F}_t)_{t\ge 0},\mathbb{P}_x) where \mathbb{P}_x denotes the probability measure where the stochastic process starts at x. Given continuous functions M,L, and K, the optimal stopping problem is

V(x) = \sup_{0\le \tau \le T} \mathbb{E}_x \left( M(X_\tau) + \int_0^\tau L(X_t) dt + \sup_{0\le t\le\tau} K(X_t) \right).

This is sometimes called the MLS (which stand for Mayer, Lagrange, and supremum, respectively) formulation.[1]

Solution methods

There are generally two approaches of solving optimal stopping problems.[1] When the underlying process (or the gain process) is described by its unconditional finite-dimensional distributions, the appropriate solution technique is the martingale approach, so called because it uses martingale theory, the most important concept being the Snell envelope. In the discrete time case, if the planning horizon T is finite, the problem can also be easily solved by dynamic programming.

When the underlying process is determined by a family of (conditional) transition functions leading to a Markovian family of transition probabilities, very powerful analytical tools provided by the theory of Markov processes can often be utilized and this approach is referred to as the Markovian method. The solution is usually obtained by solving the associated free-boundary problems (Stefan problems).

A jump diffusion result

Let Y_t be a Lévy diffusion in \mathbb{R}^k given by the SDE

dY_t = b(Y_t) dt + \sigma (Y_t) dB_t + \int_{\mathbb{R}^k} \gamma (Y_{t-},z)\bar{N}(dt,dz),\quad Y_0 = y

where B is an m-dimensional Brownian motion, \bar{N} is an l -dimensional compensated Poisson random measure, b:\mathbb{R}^k \to \mathbb{R}^k , \sigma:\mathbb{R}^k \to \mathbb{R}^{k\times m} , and \gamma:\mathbb{R}^k \times \mathbb{R}^k \to \mathbb{R}^{k\times l} are given functions such that a unique solution (Y_t) exists. Let \mathcal{S}\subset \mathbb{R}^k be an open set (the solvency region) and

\tau_\mathcal{S} = \inf\{ t>0: Y_t \notin \mathcal{S} \}

be the bankruptcy time. The optimal stopping problem is:

V(y) = \sup_{\tau \le \tau_\mathcal{S}} J^\tau (y) = \sup_{\tau \le \tau_\mathcal{S}} \mathbb{E}_y \left[ M(Y_\tau) + \int_0^\tau L(Y_t) dt \right].

It turns out that under some regularity conditions,[2] the following verification theorem holds:

If a function \phi:\bar{\mathcal{S}}\to \mathbb{R} satisfies

  • \phi \in C(\bar{\mathcal{S}}) \cap C^1(\mathcal{S}) \cap C^2(\mathcal{S}\setminus \partial D) where the continuation region is D = \{y\in\mathcal{S}: \phi(y) > M(y) \} ,
  • \phi \ge M on \mathcal{S} , and
  • \mathcal{A}\phi + L \le 0 on \mathcal{S} \setminus \partial D , where \mathcal{A} is the infinitesimal generator of (Y_t)

then \phi(y) \ge V(y) for all y\in \bar{\mathcal{S}} . Moreover, if

  • \mathcal{A}\phi + L = 0 on D

Then \phi(y) = V(y) for all y\in \bar{\mathcal{S}} and \tau^* = \inf\{ t>0: Y_t\notin D\} is an optimal stopping time.

These conditions can also be written is a more compact form (the integro-variational inequality):

  • \max\left\{ \mathcal{A}\phi + L, M-\phi \right\} = 0 on \mathcal{S} \setminus \partial D.


Coin tossing

(Example where \mathbb{E}(y_i) 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 Bernoulli distribution


and if

y_i = \frac 1 i \sum_{k=1}^{i} X_k

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

House selling

(Example where \mathbb{E}(y_i) does not necessarily converge)

You have a house and wish to sell it. Each day you are offered X_n for your house, and pay k to continue advertising it. If you sell your house on day n, you will earn y_n, where y_n = (X_n - 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

(Example where (X_i) is a finite sequence)

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 R_1, \ldots, R_n (n is some large number, perhaps) are the ranks of the objects, and y_i is the chance you pick the best object if you stop intentionally rejecting objects at step i, then (R_i) and (y_i) are the sequences associated with this problem. This problem was solved in the early 1960s 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 (Bruss algorithm).

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.

Option trading

In the trading of options on financial markets, the holder of an American option is allowed to exercise the right to buy (or sell) the underlying asset at a predetermined price at any time before or at the expiry date. Therefore, the valuation of American options is essentially an optimal stopping problem. Consider a classical Black-Scholes set-up and let r be the risk-free interest rate and \delta and \sigma be the dividend rate and volatility of the stock. The stock price S follows geometric Brownian motion

S_t = S_0 \exp\left\{ \left(r - \delta - \frac{\sigma^2}{2}\right) t + \sigma B_t \right\}

under the risk-neutral measure. When the option is perpetual, the optimal stopping problem is

V(x) = \sup_{\tau} \mathbb{E}_x \left[ e^{-r\tau} g(S_\tau) \right]

where the payoff function is g(x) = (x-K)^+ for a call option and g(x) = (K-x)^+ for a put option. The variational inequality is

\max\left\{ \frac{1}{2} \sigma^2 x^2 V''(x) + (r-\delta) x V'(x) - rV(x), g(x) - V(x) \right\} = 0

for all x \in (0,\infty)\setminus \{b\} where b is the exercise boundary. The solution is known to be[3]

  • (Perpetual call) V(x) = \begin{cases} (b-K)(x/b)^\gamma & x\in(0,b) \\ x-K & x\in[b,\infty) \end{cases} where \gamma = (\sqrt{\nu^2 + 2r} - \nu) / \sigma and \nu = (r-\delta)/\sigma - \sigma / 2, \quad b = \gamma K / (\gamma - 1).
  • (Perpetual put) V(x) = \begin{cases} K - x & x\in(0,c] \\(K-c)(x/c)^\tilde{\gamma} & x\in(c,\infty) \end{cases} where \tilde{\gamma} = -(\sqrt{\nu^2 + 2r} + \nu) / \sigma and \nu = (r-\delta)/\sigma - \sigma / 2, \quad c = \tilde{\gamma} K / (\tilde{\gamma} - 1).

If the expiry date is finite, the problem is associated with a 2-dimensional free-boundary problem with no known closed-form solution. Various numerical methods can be used.

See also


  1. ^ a b Peskir, Goran;  
  2. ^  
  3. ^ Karatzas, Ioannis;  
  • Chow, Y.S., Robbins, H. and Siegmund, D. (1971) Great Expectations: The Theory of Optimal Stopping. Boston: Houghton Mifflin
  • T. P. Hill. "Knowing When to Stop". American Scientist, Vol. 97, 126-133 (2009). (For French translation, see cover story in the July issue of Pour la Science (2009))
  • Optimal Stopping and Applications, retrieved on 21 June 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)
  • R. Rogerson, R. Shimer, and R. Wright (2005), 'Search-theoretic models of the labor market: a survey'. Journal of Economic Literature 43, pp. 959–88.

External links

  • Neil Bearden's Optimal Search Page
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.