Optimal stopping
   HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the theory of optimal stopping or early stopping : (For French translation, se
cover story
in the July issue of ''Pour la Science'' (2009).)
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 Statistics (from German language, German: ''wikt:Statistik#German, Statistik'', "description of a State (polity), state, a country") is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of ...
,
economics Economics () is the social science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goods and services. Economics focuses on the behaviour and intera ...
, and
mathematical finance Mathematical finance, also known as quantitative finance and financial mathematics, is a field of applied mathematics, concerned with mathematical modeling of financial markets. In general, there exist two separate branches of finance that require ...
(related to the pricing of American options). A key example of an optimal stopping problem is the
secretary problem The secretary problem demonstrates a scenario involving optimal stopping theory For French translation, secover storyin the July issue of ''Pour la Science'' (2009). that is studied extensively in the fields of applied probability, statistics, ...
. Optimal stopping problems can often be written in the form of a
Bellman equation A Bellman equation, named after Richard E. Bellman, is a necessary condition for optimality associated with the mathematical optimization method known as dynamic programming. It writes the "value" of a decision problem at a certain point in time ...
, and are therefore often solved using
dynamic programming Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. ...
.


Definition


Discrete time case

Stopping rule problems are associated with two objects: # A sequence of random variables X_1, X_2, \ldots, whose joint distribution is something assumed to be known # A sequence of 'reward' functions (y_i)_ 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 maximize your expected reward (or equivalently, minimize your expected loss)


Continuous time case

Consider a gain process G=(G_t)_ defined on a
filtered probability space Filtration is a physical separation process that separates solid matter and fluid from a mixture using a ''filter medium'' that has a complex structure through which only the fluid can pass. Solid particles that cannot pass through the filter ...
(\Omega,\mathcal,(\mathcal_t)_,\mathbb) and assume that G is
adapted In biology, adaptation has three related meanings. Firstly, it is the dynamic evolutionary process of natural selection that fits organisms to their environment, enhancing their evolutionary fitness. Secondly, it is a state reached by the po ...
to the filtration. The optimal stopping problem is to find the
stopping time In probability theory, in particular in the study of stochastic processes, a stopping time (also Markov time, Markov moment, optional stopping time or optional time ) is a specific type of “random time”: a random variable whose value is inter ...
\tau^* which maximizes the expected gain : V_t^T = \mathbb G_ = \sup_ \mathbb G_\tau where V_t^T is called the
value function The value function of an optimization problem gives the value attained by the objective function at a solution, while only depending on the parameters of the problem. In a controlled dynamical system, the value function represents the optimal payof ...
. Here T can take value \infty. A more specific formulation is as follows. We consider an adapted strong
Markov process A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happe ...
X = (X_t)_ defined on a filtered probability space (\Omega,\mathcal,(\mathcal_t)_,\mathbb_x) where \mathbb_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_ \mathbb_x \left( M(X_\tau) + \int_0^\tau L(X_t) dt + \sup_ K(X_t) \right). This is sometimes called the MLS (which stand for Mayer, Lagrange, and supremum, respectively) formulation.


Solution methods

There are generally two approaches to solving optimal stopping problems. When the underlying process (or the gain process) is described by its unconditional
finite-dimensional distribution In mathematics, finite-dimensional distributions are a tool in the study of measures and stochastic processes. A lot of information can be gained by studying the "projection" of a measure (or process) onto a finite-dimensional vector space (or fi ...
s, 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 Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. ...
. When the underlying process is determined by a family of (conditional) transition functions leading to a Markov family of transition probabilities, powerful analytical tools provided by the theory of
Markov process A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happe ...
es can often be utilized and this approach is referred to as the Markov method. The solution is usually obtained by solving the associated free-boundary problems (
Stefan problem In mathematics and its applications, particularly to phase transitions in matter, a Stefan problem is a particular kind of boundary value problem for a system of partial differential equations (PDE), in which the boundary between the phases can m ...
s).


A jump diffusion result

Let Y_t be a Lévy diffusion in \mathbb^k given by the SDE : dY_t = b(Y_t) dt + \sigma (Y_t) dB_t + \int_ \gamma (Y_,z)\bar(dt,dz),\quad Y_0 = y where B is an m-dimensional
Brownian motion Brownian motion, or pedesis (from grc, πήδησις "leaping"), is the random motion of particles suspended in a medium (a liquid or a gas). This pattern of motion typically consists of random fluctuations in a particle's position insi ...
, \bar is an l -dimensional compensated
Poisson random measure Let (E, \mathcal A, \mu) be some measure space with \sigma-finite measure \mu. The Poisson random measure with intensity measure \mu is a family of random variables \_ defined on some probability space (\Omega, \mathcal F, \mathrm) such that i) ...
, b:\mathbb^k \to \mathbb^k , \sigma:\mathbb^k \to \mathbb^ , and \gamma:\mathbb^k \times \mathbb^k \to \mathbb^ are given functions such that a unique solution (Y_t) exists. Let \mathcal\subset \mathbb^k be an open set (the solvency region) and : \tau_\mathcal = \inf\ be the bankruptcy time. The optimal stopping problem is: : V(y) = \sup_ J^\tau (y) = \sup_ \mathbb_y \left M(Y_\tau) + \int_0^\tau L(Y_t) dt \right It turns out that under some regularity conditions, the following verification theorem holds: If a function \phi:\bar\to \mathbb satisfies * \phi \in C(\bar) \cap C^1(\mathcal) \cap C^2(\mathcal\setminus \partial D) where the continuation region is D = \ , * \phi \ge M on \mathcal , and * \mathcal\phi + L \le 0 on \mathcal \setminus \partial D , where \mathcal is the infinitesimal generator of (Y_t) then \phi(y) \ge V(y) for all y\in \bar . Moreover, if * \mathcal\phi + L = 0 on D Then \phi(y) = V(y) for all y\in \bar and \tau^* = \inf\ is an optimal stopping time. These conditions can also be written is a more compact form (the integro-variational inequality): * \max\left\ = 0 on \mathcal \setminus \partial D.


Examples


Coin tossing

(Example where \mathbb(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 ''X''''i'' (for ''i'' ≥ 1) forms a sequence of independent, identically distributed random variables with
Bernoulli distribution In probability theory and statistics, the Bernoulli distribution, named after Swiss mathematician Jacob Bernoulli,James Victor Uspensky: ''Introduction to Mathematical Probability'', McGraw-Hill, New York 1937, page 45 is the discrete probabi ...
: \text\left(\frac\right), and if : y_i = \frac 1 i \sum_^ X_k then the sequences (X_i)_, and (y_i)_ are the objects associated with this problem.


House selling

(Example where \mathbb(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) 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 The odds algorithm (or Bruss algorithm) is a mathematical method for computing optimal strategies for a class of problems that belong to the domain of optimal stopping problems. Their solution follows from the ''odds strategy'', and the importance ...
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.


Parking problem

A special example of an application of search theory is the task of optimal selection of parking space by a driver going to the opera (theater, shopping, etc.). Approaching the destination, the driver goes down the street along which there are parking spaces – usually, only some places in the parking lot are free. The goal is clearly visible, so the distance from the target is easily assessed. The driver's task is to choose a free parking space as close to the destination as possible without turning around so that the distance from this place to the destination is the shortest.


Option trading

In the trading of options on
financial market A financial market is a market in which people trade financial securities and derivatives at low transaction costs. Some of the securities include stocks and bonds, raw materials and precious metals, which are known in the financial market ...
s, the holder of an
American option In finance, the style or family of an option (finance), option is the class into which the option falls, usually defined by the dates on which the option may be Exercise (options), exercised. The vast majority of options are either European or Amer ...
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 The risk-free rate of return, usually shortened to the risk-free rate, is the rate of return of a hypothetical investment with scheduled payments over a fixed period of time that is assumed to meet all payment obligations. Since the risk-free ra ...
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\ under the risk-neutral measure. When the option is perpetual, the optimal stopping problem is : V(x) = \sup_ \mathbb_x \left e^ 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\ = 0 for all x \in (0,\infty)\setminus \ where b is the exercise boundary. The solution is known to be * (Perpetual call) V(x) = \begin (b-K)(x/b)^\gamma & x\in(0,b) \\ x-K & x\in[b,\infty) \end where \gamma = (\sqrt - \nu) / \sigma and \nu = (r-\delta)/\sigma - \sigma / 2, \quad b = \gamma K / (\gamma - 1). * (Perpetual put) V(x) = \begin K - x & x\in(0,c] \\(K-c)(x/c)^\tilde & x\in(c,\infty) \end where \tilde = -(\sqrt + \nu) / \sigma and \nu = (r-\delta)/\sigma - \sigma / 2, \quad c = \tilde K / (\tilde - 1). On the other hand, when 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, however, be used. See Black–Scholes model#American options for various valuation methods here, as well as
Fugit In mathematical finance, fugit is the expected (or optimal) date to exercise an American- or Bermudan option. It is useful for hedging purposes here; see Greeks (finance) and . The term was first introduced by Mark Garman in an article "Sempe ...
for a discrete, tree based, calculation of the optimal time to exercise.


See also

*
Halting problem In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a ...
* Markov decision process * Optional stopping theorem * Prophet inequality * Stochastic control


References


Citations


Sources

* Thomas S. Ferguson
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 The European Mathematical Society (EMS) is a European organization dedicated to the development of mathematics in Europe. Its members are different mathematical societies in Europe, academic institutions and individual mathematicians. The current ...
'', Issue 62, 14–20, (2006) * {{DEFAULTSORT:Optimal Stopping Mathematical finance Sequential methods Dynamic programming