Parada óptima

Clase de problemas matemáticos.

En matemáticas , la teoría de la parada óptima ^{[1] [2]} o parada temprana ^[3] se ocupa del problema de elegir un momento para realizar una acción particular, con el fin de maximizar una recompensa esperada o minimizar un costo esperado. Los problemas de parada óptima se pueden encontrar en áreas de estadística , economía y finanzas matemáticas (relacionadas con la fijación de precios de las opciones estadounidenses ). Un ejemplo clave de un problema de parada óptima es el problema de la secretaria . Los problemas de parada óptima a menudo se pueden escribir en forma de ecuación de Bellman y, por lo tanto, a menudo se resuelven mediante programación dinámica .

Definición

Caso de tiempo discreto

Los problemas de reglas de detención están asociados con dos objetos:

1. Una secuencia de variables aleatorias , cuya distribución conjunta se supone conocida. ${\displaystyle X_{1},X_{2},\ldots }$
2. Una secuencia de funciones de 'recompensa' que dependen de los valores observados de las variables aleatorias en 1: ${\displaystyle (y_{i})_{i\geq 1}}$

   ${\displaystyle y_{i}=y_{i}(x_{1},\ldots ,x_{i})}$

Dados esos objetos, el problema es el siguiente:

• Estás observando la secuencia de variables aleatorias y, en cada paso , puedes elegir dejar de observar o continuar. ${\displaystyle i}$
• Si dejas de observar en el paso , recibirás recompensa. ${\displaystyle i}$ ${\displaystyle y_{i}}$
• Quiere elegir una regla de detención para maximizar su recompensa esperada (o, de manera equivalente, minimizar su pérdida esperada)

Caso de tiempo continuo

Considere un proceso de ganancia definido en un espacio de probabilidad filtrado y suponga que está adaptado a la filtración. El problema de parada óptima es encontrar el tiempo de parada que maximice la ganancia esperada. ${\displaystyle G=(G_{t})_{t\geq 0}}$ ${\displaystyle (\Omega ,{\mathcal {F}},({\mathcal {F}}_{t})_{t\geq 0},\mathbb {P} )}$ ${\displaystyle G}$ ${\displaystyle \tau ^{*}}$

${\displaystyle V_{t}^{T}=\mathbb {E} G_{\tau ^{*}}=\sup _{t\leq \tau \leq T}\mathbb {E} G_{\tau }}$

donde se llama función de valor . Aquí puede tomar valor . ${\displaystyle V_{t}^{T}}$ ${\displaystyle T}$ ${\displaystyle \infty }$

Una formulación más específica es la siguiente. Consideramos un proceso de Markov fuerte adaptado definido en un espacio de probabilidad filtrado donde denota la medida de probabilidad donde comienza el proceso estocástico . Dadas funciones continuas , y , el problema de parada óptimo es ${\displaystyle X=(X_{t})_{t\geq 0}}$ ${\displaystyle (\Omega ,{\mathcal {F}},({\mathcal {F}}_{t})_{t\geq 0},\mathbb {P} _{x})}$ ${\displaystyle \mathbb {P} _{x}}$ ${\displaystyle x}$ ${\displaystyle M,L}$ ${\displaystyle K}$

${\displaystyle V(x)=\sup _{0\leq \tau \leq T}\mathbb {E} _{x}\left(M(X_{\tau })+\int _{0}^{\tau }L(X_{t})dt+\sup _{0\leq t\leq \tau }K(X_{t})\right).}$

A esto a veces se le llama formulación MLS (que significa Mayer, Lagrange y supremum, respectivamente). ^[4]

Métodos de solución

Generalmente existen dos enfoques para resolver problemas de parada óptima. ^[4] Cuando el proceso subyacente (o el proceso de ganancia) se describe mediante sus distribuciones incondicionales de dimensión finita , la técnica de solución adecuada es el enfoque martingala, llamado así porque utiliza la teoría de la martingala , siendo el concepto más importante la envolvente de Snell . En el caso del tiempo discreto, si el horizonte de planificación es finito, el problema también puede resolverse fácilmente mediante programación dinámica . ${\displaystyle T}$

Cuando el proceso subyacente está determinado por una familia de funciones de transición (condicionales) que conducen a una familia de probabilidades de transición de Markov, a menudo se pueden utilizar poderosas herramientas analíticas proporcionadas por la teoría de los procesos de Markov y este enfoque se conoce como método de Markov. La solución suele obtenerse resolviendo los problemas de límites libres asociados ( problemas de Stefan ).

Un resultado de difusión de salto

Sea una difusión de Lévy dada por la SDE ${\displaystyle Y_{t}}$ ${\displaystyle \mathbb {R} ^{k}}$

${\displaystyle 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}$

donde es un movimiento browniano de dimensiones , es una medida aleatoria de Poisson compensada de dimensiones , y se les dan funciones tales que existe una solución única. Sea un conjunto abierto (la región de solvencia) y ${\displaystyle B}$ ${\displaystyle m}$ ${\displaystyle {\bar {N}}}$ ${\displaystyle l}$ ${\displaystyle b:\mathbb {R} ^{k}\to \mathbb {R} ^{k}}$ ${\displaystyle \sigma :\mathbb {R} ^{k}\to \mathbb {R} ^{k\times m}}$ ${\displaystyle \gamma :\mathbb {R} ^{k}\times \mathbb {R} ^{k}\to \mathbb {R} ^{k\times l}}$ ${\displaystyle (Y_{t})}$ ${\displaystyle {\mathcal {S}}\subset \mathbb {R} ^{k}}$

${\displaystyle \tau _{\mathcal {S}}=\inf\{t>0:Y_{t}\notin {\mathcal {S}}\}}$

será el momento de la quiebra. El problema de parada óptimo es:

${\displaystyle V(y)=\sup _{\tau \leq \tau _{\mathcal {S}}}J^{\tau }(y)=\sup _{\tau \leq \tau _{\mathcal {S}}}\mathbb {E} _{y}\left[M(Y_{\tau })+\int _{0}^{\tau }L(Y_{t})dt\right].}$

Resulta que bajo algunas condiciones de regularidad, ^[5] se cumple el siguiente teorema de verificación:

Si una función satisface ${\displaystyle \phi :{\bar {\mathcal {S}}}\to \mathbb {R} }$

• ${\displaystyle \phi \in C({\bar {\mathcal {S}}})\cap C^{1}({\mathcal {S}})\cap C^{2}({\mathcal {S}}\setminus \partial D)}$donde está la región de continuación , ${\displaystyle D=\{y\in {\mathcal {S}}:\phi (y)>M(y)\}}$
• ${\displaystyle \phi \geq M}$y en ${\displaystyle {\mathcal {S}}}$
• ${\displaystyle {\mathcal {A}}\phi +L\leq 0}$en , ¿dónde está el generador infinitesimal de ${\displaystyle {\mathcal {S}}\setminus \partial D}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle (Y_{t})}$

entonces para todos . Es más, si ${\displaystyle \phi (y)\geq V(y)}$ ${\displaystyle y\in {\bar {\mathcal {S}}}}$

• ${\displaystyle {\mathcal {A}}\phi +L=0}$en ${\displaystyle D}$

Entonces para todos y es un momento óptimo para detenerse. ${\displaystyle \phi (y)=V(y)}$ ${\displaystyle y\in {\bar {\mathcal {S}}}}$ ${\displaystyle \tau ^{*}=\inf\{t>0:Y_{t}\notin D\}}$

Estas condiciones también se pueden escribir en una forma más compacta (la desigualdad integrovariacional ):

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

Ejemplos

lanzamiento de moneda

(Ejemplo donde converge) ${\displaystyle \mathbb {E} (y_{i})}$

Tienes una moneda justa y la lanzas repetidamente. Cada vez, antes de tirarlo, puedes optar por dejar de tirarlo y recibir un pago (en dólares, por ejemplo) por el número medio de caras observadas.

Desea maximizar la cantidad que le pagan eligiendo una regla de detención. Si X _i (para i ≥ 1) forma una secuencia de variables aleatorias independientes distribuidas idénticamente con distribución de Bernoulli

${\displaystyle {\text{Bern}}\left({\frac {1}{2}}\right),}$

y si

${\displaystyle y_{i}={\frac {1}{i}}\sum _{k=1}^{i}X_{k}}$

luego las secuencias , y son los objetos asociados con este problema. ${\displaystyle (X_{i})_{i\geq 1}}$ ${\displaystyle (y_{i})_{i\geq 1}}$

venta de casa

(Ejemplo donde no necesariamente converge) ${\displaystyle \mathbb {E} (y_{i})}$

Tienes una casa y deseas venderla. Cada día te ofrecen por tu casa, y pagas para seguir publicitándola. Si vendes tu casa en el día , ganarás , dónde . ${\displaystyle X_{n}}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle y_{n}}$ ${\displaystyle y_{n}=(X_{n}-nk)}$

Desea maximizar la cantidad que gana eligiendo una regla de detención.

En este ejemplo, la secuencia ( ) es la secuencia de ofertas para su casa y la secuencia de funciones de recompensa es cuánto ganará. ^[6] ${\displaystyle X_{i}}$

problema de secretaria

(Ejemplo donde es una secuencia finita) ${\displaystyle (X_{i})}$

Estás observando una secuencia de objetos que se pueden clasificar de mejor a peor. Desea elegir una regla de detención que maximice sus posibilidades de elegir el mejor objeto.

Aquí, si ( n es un número grande) son los rangos de los objetos, y es la posibilidad de que elija el mejor objeto si deja de rechazar objetos intencionalmente en el paso i, entonces y son las secuencias asociadas con este problema. Este problema fue resuelto a principios de los años 1960 por varias personas. El algoritmo de probabilidades más reciente de detención óptima (algoritmo de Bruss) proporciona una solución elegante al problema de la secretaria y varias modificaciones de este problema . ${\displaystyle R_{1},\ldots ,R_{n}}$ ${\displaystyle y_{i}}$ ${\displaystyle (R_{i})}$ ${\displaystyle (y_{i})}$

Teoría de la búsqueda

Los economistas han estudiado una serie de problemas de parada óptima similares al "problema de la secretaria" y normalmente llaman a este tipo de análisis "teoría de la búsqueda". La teoría de la búsqueda se ha centrado especialmente en la búsqueda de un trabajador de un trabajo bien remunerado o en la búsqueda de un consumidor de un bien de bajo precio.

Problema de aparcamiento

Un ejemplo especial de aplicación de la teoría de la búsqueda es la tarea de seleccionar óptimamente una plaza de aparcamiento por parte de un conductor que se dirige a la ópera (teatro, compras, etc.). Al acercarse a su destino, el conductor baja por la calle en la que hay plazas de aparcamiento; normalmente, sólo algunas plazas del aparcamiento están libres. El objetivo es claramente visible, por lo que la distancia desde el objetivo se puede evaluar fácilmente. La tarea del conductor es elegir una plaza de aparcamiento libre lo más cerca posible del destino sin dar la vuelta para que la distancia desde este lugar hasta el destino sea la más corta. ^[7]

Comercio de opciones

En la negociación de opciones en los mercados financieros , el titular de una opción estadounidense puede ejercer el derecho de comprar (o vender) el activo subyacente a un precio predeterminado en cualquier momento antes o en la fecha de vencimiento. Por tanto, la valoración de las opciones americanas es esencialmente un problema de parada óptima. Considere una configuración clásica de Black-Scholes y sea la tasa de interés libre de riesgo y la tasa de dividendos y la volatilidad de la acción. El precio de las acciones sigue un movimiento browniano geométrico. ${\displaystyle r}$ ${\displaystyle \delta }$ ${\displaystyle \sigma }$ ${\displaystyle S}$

${\displaystyle S_{t}=S_{0}\exp \left\{\left(r-\delta -{\frac {\sigma ^{2}}{2}}\right)t+\sigma B_{t}\right\}}$

bajo la medida neutral al riesgo.

Cuando la opción es perpetua, el problema de parada óptimo es

${\displaystyle V(x)=\sup _{\tau }\mathbb {E} _{x}\left[e^{-r\tau }g(S_{\tau })\right]}$

donde la función de pago es para una opción de compra y para una opción de venta. La desigualdad variacional es ${\displaystyle g(x)=(x-K)^{+}}$ ${\displaystyle g(x)=(K-x)^{+}}$

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

para todos, ¿dónde está el límite del ejercicio? Se sabe que la solución es ^[8] ${\displaystyle x\in (0,\infty )\setminus \{b\}}$ ${\displaystyle b}$

• (Llamada perpetua) donde y ${\displaystyle V(x)={\begin{cases}(b-K)(x/b)^{\gamma }&x\in (0,b)\\x-K&x\in [b,\infty )\end{cases}}}$ ${\displaystyle \gamma =({\sqrt {\nu ^{2}+2r}}-\nu )/\sigma }$ ${\displaystyle \nu =(r-\delta )/\sigma -\sigma /2,\quad b=\gamma K/(\gamma -1).}$
• (Puesto perpetuo) dónde y ${\displaystyle V(x)={\begin{cases}K-x&x\in (0,c]\\(K-c)(x/c)^{\tilde {\gamma }}&x\in (c,\infty )\end{cases}}}$ ${\displaystyle {\tilde {\gamma }}=-({\sqrt {\nu ^{2}+2r}}+\nu )/\sigma }$ ${\displaystyle \nu =(r-\delta )/\sigma -\sigma /2,\quad c={\tilde {\gamma }}K/({\tilde {\gamma }}-1).}$

Por otro lado, cuando la fecha de caducidad es finita, el problema se asocia con un problema bidimensional de límites libres sin solución conocida en forma cerrada. Sin embargo, se pueden utilizar varios métodos numéricos. Consulte el modelo Black-Scholes#Opciones americanas para conocer varios métodos de valoración aquí, así como Fugit para obtener un cálculo discreto, basado en árboles , del momento óptimo para hacer ejercicio.

Ver también

• Problema de detención
• proceso de decisión de markov
• Teorema de parada opcional
• Profeta desigualdad
• control estocástico

Referencias

Citas

1. Chow, YS; Robbins, H .; Siegmund, D. (1971). Grandes expectativas: la teoría de la parada óptima . Boston: Houghton Mifflin .
2. Ferguson, Thomas S. (2007). Paradas y aplicaciones óptimas. UCLA.
3. Colina, Theodore P. (2009). "Saber cuándo parar". Científico americano . 97 (2): 126-133. doi :10.1511/2009.77.126. ISSN  1545-2786. S2CID  124798270.

   (Para la traducción al francés, consulte el artículo de portada de la edición de julio de Pour la Science (2009).)

4. Peskir, Goran; Shiryaev, Albert (2006). Problemas de parada óptima y límites libres . Conferencias de Matemáticas. ETH Zúrich. doi :10.1007/978-3-7643-7390-0. ISBN 978-3-7643-2419-3.
5. Øksendal, B .; Sulem, A. (2007). Control estocástico aplicado de difusiones de salto . doi :10.1007/978-3-540-69826-5. ISBN 978-3-540-69825-8. S2CID  123531718.
6. Ferguson, Thomas S .; Klass, Michael J. (2010). "Búsqueda de casa sin segundos momentos". Análisis secuencial . 29 (3): 236–244. doi :10.1080/07474946.2010.487423. ISSN  0747-4946.
7. MacQueen, J.; Miller Jr., RG (1960). "Políticas óptimas de persistencia". La investigación de operaciones . 8 (3): 362–380. doi :10.1287/opre.8.3.362. ISSN  0030-364X.
8. Karatzas, Ioannis; Shreve, Steven E. (1998). Métodos de Finanzas Matemáticas . Modelización estocástica y probabilidad aplicada. vol. 39. doi :10.1007/b98840. ISBN 978-0-387-94839-3.

Fuentes

• Thomas S. Ferguson , "¿Quién resolvió el problema de la secretaria?" Ciencia estadística , vol. 4., 282–296, (1989)
• F. Thomas Bruss . "Sume las probabilidades a uno y deténgase". Anales de probabilidad , vol. 28, 1384-1391, (2000)
• F. Tomás Bruss. "El arte de tomar una decisión correcta: por qué los tomadores de decisiones quieren conocer el algoritmo de probabilidades". Boletín de la Sociedad Matemática Europea , número 62, 14-20, (2006)
• Rogerson, R.; Shimer, R.; Wright, R. (2005). "Modelos teóricos de búsqueda del mercado laboral: una encuesta" (PDF) . Revista de Literatura Económica . 43 (4): 959–88. doi :10.1257/002205105775362014. JSTOR  4129380.