![]() | ||
16 backward induction and optimal stopping times
In mathematics, the theory of optimal stopping or early 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.
Contents
- 16 backward induction and optimal stopping times
- Discrete time case
- Continuous time case
- Solution methods
- A jump diffusion result
- Coin tossing
- House selling
- Secretary problem
- Search theory
- Option trading
- References
Discrete time case
Stopping rule problems are associated with two objects:
- A sequence of random variables
X 1 , X 2 , … , whose joint distribution is something assumed to be known - A sequence of 'reward' functions
( y i ) i ≥ 1 y i = y i ( x 1 , … , x i )
Given those objects, the problem is as follows:
Continuous time case
Consider a gain processes
where
A more specific formulation is as follows. We consider an adapted strong Markov process
This is sometimes called the MLS (which stand for Mayer, Lagrange, and supremum, respectively) formulation.
Solution methods
There are generally two approaches of solving optimal stopping problems. 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
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 processes 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 problems).
A jump diffusion result
Let
where
be the bankruptcy time. The optimal stopping problem is:
It turns out that under some regularity conditions, the following verification theorem holds:
If a function
then
Then
These conditions can also be written is a more compact form (the integro-variational inequality):
Coin tossing
(Example where
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
then the sequences
House selling
(Example where
You have a house and wish to sell it. Each day you are offered
You wish to maximise the amount you earn by choosing a stopping rule.
In this example, the sequence (
Secretary problem
(Example where
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
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
under the risk-neutral measure.
When the option is perpetual, the optimal stopping problem is
where the payoff function is
for all
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 for a discrete, tree based, calculation of the optimal time to exercise.