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 opciones americanas ). 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 utilizando programación dinámica .

Definición

Caso de tiempo discreto

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

1. Una secuencia de variables aleatorias , cuya distribución conjunta es algo que se supone que es conocido ${\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 entre dejar de observar o continuar. ${\displaystyle i}$
• Si dejas de observar en el paso 1 , recibirás recompensa. ${\displaystyle i}$ ${\displaystyle y_{i}}$
• Quiere elegir una regla de detención para maximizar su recompensa esperada (o equivalentemente, minimizar su pérdida esperada)

Caso de tiempo continuo

Consideremos un proceso de ganancia definido en un espacio de probabilidad filtrado y supongamos que está adaptado a la filtración. El problema de parada óptimo consiste en 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 fuerte de Markov adaptado definido en un espacio de probabilidad filtrado donde denota la medida de probabilidad donde el proceso estocástico comienza en . Dadas las 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 supremo, respectivamente). ^[4]

Métodos de solución

En general, existen dos enfoques para resolver problemas de parada óptima. ^[4] Cuando el proceso subyacente (o el proceso de ganancia) se describe mediante sus distribuciones de dimensión finita incondicionales , la técnica de solución adecuada es el enfoque martingala, llamado así porque utiliza la teoría de martingala , siendo el concepto más importante la envolvente de Snell . En el caso de tiempo discreto, si el horizonte de planificación es finito, el problema también se puede resolver 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 las potentes herramientas analíticas proporcionadas por la teoría de procesos de Markov ; este enfoque se conoce como el método de Markov. La solución se obtiene generalmente resolviendo los problemas de contorno libre 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 -dimensional , es una medida aleatoria de Poisson compensada -dimensional , , , y son funciones dadas 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}}\}}$

Es 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 ciertas 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 la región de continuación es , ${\displaystyle D=\{y\in {\mathcal {S}}:\phi (y)>M(y)\}}$
• ${\displaystyle \phi \geq M}$en , y ${\displaystyle {\mathcal {S}}}$
• ${\displaystyle {\mathcal {A}}\phi +L\leq 0}$en , donde está el generador infinitesimal de ${\displaystyle {\mathcal {S}}\setminus \partial D}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle (Y_{t})}$

Entonces para todos . Ademá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 tiempo de parada óptimo. ${\displaystyle \phi (y)=V(y)}$ ${\displaystyle y\in {\bar {\mathcal {S}}}}$ ${\displaystyle \tau ^{*}=\inf\{t>0:Y_{t}\notin D\}}$

Estas condiciones también pueden escribirse en una forma más compacta (la desigualdad integro-variacional ):

• ${\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 lanzarla, puedes elegir dejar de lanzarla y recibir un pago (en dólares, por ejemplo) por la cantidad promedio de caras observadas.

Desea maximizar la cantidad que recibe eligiendo una regla de detención. Si X _i (para i ≥ 1) forma una secuencia de variables aleatorias independientes, idénticamente distribuidas 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}}$

Entonces 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 el día , ganarás , donde . ${\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 tu casa, y la secuencia de funciones de recompensa es cuánto ganarás. ^[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. Quieres elegir una regla de detención que maximice tus posibilidades de elegir el mejor objeto.

Aquí, si ( n es un número grande) son los rangos de los objetos, y es la probabilidad 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 la década de 1960 por varias personas. Una solución elegante al problema de la secretaria y varias modificaciones de este problema la proporciona el algoritmo de probabilidades de detención óptima (algoritmo de Bruss). ${\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 suelen denominar 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 empleo bien remunerado o en la búsqueda de un consumidor de un bien de bajo precio.

Problema de estacionamiento

Un ejemplo particular de aplicación de la teoría de búsqueda es la tarea de selección óptima de plaza de aparcamiento por parte de un conductor que se dirige a la ópera (teatro, centro comercial, etc.). Al acercarse al destino, el conductor recorre la calle en la que hay plazas de aparcamiento disponibles; normalmente, solo algunas plazas del aparcamiento están libres. El objetivo es claramente visible, por lo que la distancia hasta el objetivo se puede evaluar fácilmente. La tarea del conductor consiste en elegir una plaza de aparcamiento libre lo más cerca posible del destino sin dar la vuelta, de modo 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 a comprar (o vender) el activo subyacente a un precio predeterminado en cualquier momento antes o en la fecha de vencimiento. Por lo tanto, la valoración de las opciones estadounidenses es esencialmente un problema de parada óptima. Consideremos una configuración clásica de Black-Scholes y sea la tasa de interés libre de riesgo y y la tasa de dividendos y la volatilidad de la acción. El precio de la acción 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 de neutralidad de riesgo.

Cuando la opción es perpetua, el problema de parada óptima 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 los casos donde es 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) donde 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 otra parte, cuando la fecha de vencimiento es finita, el problema se asocia a un problema de borde libre bidimensional sin solución de forma cerrada conocida. Sin embargo, se pueden utilizar varios métodos numéricos. Véase el modelo Black-Scholes#Opciones americanas para varios métodos de valoración aquí, así como Fugit para un cálculo discreto basado en árboles del momento óptimo para el ejercicio.

Véase también

• Problema de parada
• Proceso de decisión de Markov
• Teorema de parada opcional
• Profeta desigualdad
• Control estocástico
• Análisis secuencial

Referencias

Citas

1. Chow, YS; Robbins, H. ; Siegmund, D. (1971). Grandes esperanzas: la teoría de la detención óptima . Boston: Houghton Mifflin .
2. Ferguson, Thomas S. (2007). Frenado óptimo y aplicaciones. UCLA.
3. Hill, Theodore P. (2009). "Saber cuándo parar". American Scientist . 97 (2): 126–133. doi :10.1511/2009.77.126. ISSN  1545-2786. S2CID  124798270.

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

4. Peskir, Goran; Shiryaev, Albert (2006). Problemas de detención óptima y de borde libre . Lecciones 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. Número de identificación del sujeto  123531718.
6. Ferguson, Thomas S. ; Klass, Michael J. (2010). "La búsqueda de una 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". 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 . Modelado estocástico 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?" , Statistical Science , vol. 4, 282-296, (1989)
• F. Thomas Bruss . "Suma las probabilidades a uno y detente". Anales de probabilidad , vol. 28, 1384-1391, (2000)
• F. Thomas Bruss. "El arte de tomar la decisión correcta: por qué los que toman 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.