Optimum durdurma - Optimal stopping

In matematik , teorisi optimum durdurulması veya erken durdurma amacıyla, belirli bir eylemde bir zaman seçme sorunuyla ilgilidir maksimize beklenen ödül veya beklenen maliyeti en aza indirmek. Optimum durma problemleri istatistik , ekonomi ve matematiksel finans ( Amerikan opsiyonlarının fiyatlandırılmasıyla ilgili ) alanlarında bulunabilir. Optimal durma probleminin önemli bir örneği sekreter problemidir . Optimal durma problemleri genellikle bir Bellman denklemi şeklinde yazılabilir ve bu nedenle genellikle dinamik programlama kullanılarak çözülür .

Tanım

Ayrık zaman durumu

Durdurma kuralı sorunları iki nesneyle ilişkilendirilir:

1. Ortak dağılımı bilindiği varsayılan bir rastgele değişkenler dizisi${\displaystyle X_{1},X_{2},\ldots }$
2. 1'de rastgele değişkenlerin gözlenen değerlerine bağlı olan bir dizi 'ödül' işlevi : ${\displaystyle (y_{i})_{i\geq 1}}$

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

Bu nesneler göz önüne alındığında, sorun aşağıdaki gibidir:

• Rastgele değişkenlerin sırasını gözlemliyorsunuz ve her adımda gözlemi durdurmayı veya devam etmeyi seçebilirsiniz.${\görüntüleme stili ben}$
• Adımda gözlemlemeyi bırakırsanız, ödül alacaksınız.${\görüntüleme stili ben}$${\görüntüleme stili y_{i}}$
• Beklenen ödülünüzü en üst düzeye çıkarmak (veya eşdeğer olarak, beklenen kaybınızı en aza indirmek) için bir durdurma kuralı seçmek istiyorsunuz.

Sürekli zaman durumu

Bir kazanç sürecini göz önünde bir tanımlanmış , süzüldü olasılık alanı ve varsayalım edilir adapte filtrasyona. Optimum durma problemi, beklenen kazancı maksimize eden durma zamanını bulmaktır.${\displaystyle G=(G_{t})_{t\geq 0}}$ ${\displaystyle (\Omega ,{\mathcal {F}},({\mathcal {F}}_{t})_{t\geq 0},\mathbb {P} )}$${\görüntüleme stili G}$ ${\görüntüleme stili\tau ^{*}}$

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

burada değer işlevi denir . Burada değer alabilir . ${\ Displaystyle V_{t}^{T}}$${\görüntüleme stili T}$${\görüntüleme stili \infty }$

Daha spesifik bir formülasyon aşağıdaki gibidir. Bu uyarlanmış bir güçlü dikkate Markov işlemi bir filtre olasılık uzayında tanımlanan belirtmektedir olasılık ölçü burada stokastik süreç başlar en . Verilen sürekli fonksiyonlar ve optimal durma problemi ${\displaystyle X=(X_{t})_{t\geq 0}}$${\displaystyle (\Omega ,{\mathcal {F}},({\mathcal {F}}_{t})_{t\geq 0},\mathbb {P} _{x})}$${\displaystyle \mathbb {P} _{x}}$${\görüntüleme stili x}$${\görüntüleme stili M,L}$${\görüntüleme stili 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})\sağ).}$

Buna bazen MLS (sırasıyla Mayer, Lagrange ve supremum anlamına gelir) formülasyonu denir.

Çözüm yöntemleri

Optimum durma problemlerini çözmek için genellikle iki yaklaşım vardır. Altta yatan süreç (veya kazanç süreci) koşulsuz sonlu boyutlu dağılımlarıyla tanımlandığında , uygun çözüm tekniği martingale yaklaşımıdır, çünkü martingale teorisini kullanır , en önemli kavram Snell zarfıdır . Ayrık zaman durumunda, eğer planlama ufku sonlu ise, problem dinamik programlama ile de kolaylıkla çözülebilir . ${\görüntüleme stili T}$

Altta yatan süreç, bir Markov geçiş olasılıkları ailesine yol açan bir (koşullu) geçiş fonksiyonları ailesi tarafından belirlendiğinde, Markov süreçleri teorisi tarafından sağlanan güçlü analitik araçlar sıklıkla kullanılabilir ve bu yaklaşım Markov yöntemi olarak adlandırılır. Çözüm genellikle ilgili serbest sınır problemleri ( Stefan problemleri ) çözülerek elde edilir .

Bir sıçrama difüzyon sonucu

SDE tarafından verilen bir Lévy difüzyonu olsun${\görüntüleme stili 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}$

nerede bir -boyutlu Brownian hareketi , bir -boyutlu kompanzasyonlu Poisson rasgele ölçüsüdür , , , ve benzersiz bir çözüm olacak şekilde fonksiyonlar verilir . Izin açık kümesi (ödeme gücü bölge) olmak ve ${\görüntüleme stili B}$${\görüntüleme stili m}$${\görüntüleme stili {\bar {N}}}$${\görüntüleme stili 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}}$${\görüntüleme stili (Y_{t})}$${\displaystyle {\mathcal {S}}\subset \mathbb {R} ^{k}}$

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

iflas zamanı olsun. Optimum durdurma problemi:

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

Bazı düzenlilik koşulları altında aşağıdaki doğrulama teoreminin geçerli olduğu ortaya çıktı:

Bir işlev tatmin ederse${\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 \kısmi D)}$devam bölgesi nerede ,${\displaystyle D=\{y\in {\mathcal {S}}:\phi (y)>M(y)\}}$
• ${\displaystyle \phi \geq M}$üzerinde ve${\görüntüleme stili {\matematiksel {S}}}$
• ${\displaystyle {\mathcal {A}}\phi +L\leq 0}$üzerinde nerede olduğunu sonsuzküçük jeneratör arasında${\displaystyle {\mathcal {S}}\setminus \kısmi D}$${\görüntüleme stili {\matematiksel {A}}}$${\görüntüleme stili (Y_{t})}$

sonra hepsi için . Ayrıca, eğer ${\görüntüleme stili \phi (y)\geq V(y)}$${\displaystyle y\in {\bar {\mathcal {S}}}}$

• ${\displaystyle {\mathcal {A}}\phi +L=0}$ üzerinde ${\görüntüleme stili D}$

O zaman herkes için ve en uygun durma süresidir. ${\görüntüleme stili \phi (y)=V(y)}$${\displaystyle y\in {\bar {\mathcal {S}}}}$${\displaystyle \tau ^{*}=\inf\{t>0:Y_{t}\notin D\}}$

Bu koşullar, daha kompakt bir biçimde de yazılabilir ( bütünsel-değişim eşitsizliği ):

• ${\displaystyle \max \sol\{{\mathcal {A}}\phi +L,M-\phi \sağ\}=0}$ üzerinde ${\displaystyle {\mathcal {S}}\setminus \kısmi D.}$

Örnekler

Madeni para atma

(Örnek nerede birleşir) ${\displaystyle \mathbb {E} (y_{i})}$

Adil bir madeni paranız var ve tekrar tekrar atıyorsunuz. Her seferinde, atılmadan önce, atmayı bırakıp gözlemlenen ortalama tura sayısı kadar ödeme (örneğin dolar olarak) almayı seçebilirsiniz.

Bir durdurma kuralı seçerek ödediğiniz tutarı en üst düzeye çıkarmak istiyorsunuz. Eğer X, _i için ( i 1 '≥) bağımsız bir dizi oluşturur, aynı rastgele değişkenler dağıtılmış Bernoulli dağılımı

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

ve eğer

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

sonra diziler ve bu sorunla ilişkili nesnelerdir. ${\displaystyle (X_{i})_{i\geq 1}}$${\displaystyle (y_{i})_{i\geq 1}}$

ev satışı

(Örnek , mutlaka yakınsak değildir) ${\displaystyle \mathbb {E} (y_{i})}$

Bir eviniz var ve onu satmak istiyorsunuz. Her gün eviniz için size teklif verilir ve reklamını yapmaya devam etmek için ödeme yaparsınız . Evinizi gününde satarsanız nerede kazanırsınız . ${\displaystyle X_{n}}$${\görüntüleme stili k}$${\görüntüleme stili n}$${\görüntüleme stili y_{n}}$${\displaystyle y_{n}=(X_{n}-nk)}$

Bir durdurma kuralı seçerek kazandığınız miktarı en üst düzeye çıkarmak istiyorsunuz.

Bu örnekte, ( ) sırası, eviniz için tekliflerin sırasıdır ve ödül fonksiyonlarının sırası, ne kadar kazanacağınızdır. ${\displaystyle X_{i}}$

Sekreter sorunu

(Örnek nerede sonlu bir dizidir) ${\görüntüleme stili (X_{i})}$

En iyiden en kötüye doğru sıralanabilen bir dizi nesne gözlemliyorsunuz. En iyi nesneyi seçme şansınızı en üst düzeye çıkaran bir durdurma kuralı seçmek istiyorsunuz.

Burada, eğer ( n büyük bir sayıdır) nesnelerin sıralarıysa ve i. adımda nesneleri kasıtlı olarak reddetmeyi bırakırsanız en iyi nesneyi seçme şansınız ise ve bu sorunla ilişkili dizilerdir. Bu sorun 1960'ların başında birkaç kişi tarafından çözüldü. Sekreter sorununa zarif bir çözüm ve bu sorunun çeşitli modifikasyonları, daha yeni olan en iyi olasılık algoritması optimal durdurma (Bruss algoritması) tarafından sağlanır. ${\displaystyle R_{1},\ldots ,R_{n}}$${\görüntüleme stili y_{i}}$${\görüntüleme stili (R_{i})}$${\görüntüleme stili (y_{i})}$

Arama teorisi

Ekonomistler, "sekreter problemi"ne benzer bir dizi optimal durdurma problemi üzerinde çalışmışlardır ve tipik olarak bu tip analizlere "arama teorisi" adını verirler. Arama teorisi, özellikle bir işçinin yüksek ücretli bir iş arayışına veya bir tüketicinin düşük fiyatlı bir mal arayışına odaklanmıştır.

Park sorunu

Arama teorisi uygulamasının özel bir örneği, operaya (tiyatro, alışveriş, vb.) giden bir sürücü tarafından en uygun park yeri seçimi görevidir. Hedefe yaklaşırken sürücü, park yerlerinin bulunduğu caddeden aşağı iner - genellikle park yerinde sadece bazı yerler ücretsizdir. Hedef açıkça görülebilir, bu nedenle hedefe olan mesafe kolayca değerlendirilir. Sürücünün görevi, bu yerden varış noktasına olan mesafenin en kısa olması için dönmeden hedefe mümkün olduğunca yakın ücretsiz bir park yeri seçmektir.

Opsiyon ticareti

Ticareti seçenekler üzerinde mali piyasalar , bir sahibinin Amerikan seçeneği önce veya son kullanma tarihi de herhangi bir zamanda önceden belirlenmiş bir fiyattan dayanak varlığı satın (veya satış) hakkını kullanma izin verilir. Bu nedenle, Amerikan seçeneklerinin değerlemesi esasen optimal bir durdurma problemidir. Klasik bir düşünün Black-Scholes set-up ve izin olmak risksiz faiz oranı ve ve temettü oranı ve hisse senedi oynaklığı olabilir. Hisse senedi fiyatı geometrik Brownian hareketini takip ediyor ${\görüntüleme stili r}$${\görüntüleme stili \delta }$${\görüntüleme stili \sigma }$${\görüntüleme stili S}$

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

risk nötr önlem kapsamında.

Seçenek sürekli olduğunda, optimal durma problemi

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

burada ödeme fonksiyonu bir alım opsiyonu ve bir satım opsiyonu içindir. Varyasyon eşitsizliği ${\görüntüleme stili g(x)=(xK)^{+}}$${\görüntüleme stili g(x)=(Kx)^{+}}$

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

herkes için egzersiz sınırı nerede . Çözüm biliniyor ${\displaystyle x\in (0,\infty )\setminus \{b\}}$${\görüntüleme stili b}$

• (Sürekli arama) nerede ve${\displaystyle V(x)={\başlangıç{durumlar}(bK)(x/b)^{\gamma }&x\in (0,b)\\xK&x\in [b,\infty )\end{durumlar }}}$${\displaystyle \gamma =({\sqrt {\nu ^{2}+2r}}-\nu )/\sigma }$${\displaystyle \nu =(r-\delta )/\sigma -\sigma /2,\quad b=\gamma K/(\gamma -1).}$
• (Sürekli koymak) nerede ve${\displaystyle V(x)={\begin{durumlar}Kx&x\in (0,c]\\(Kc)(x/c)^{\tilde {\gamma }}&x\in (c,\infty ) \end{durumlar}}}$${\displaystyle {\tilde {\gamma }}=-({\sqrt {\nu ^{2}+2r}}+\nu )/\sigma }$${\displaystyle \nu =(r-\delta )/\sigma -\sigma /2,\quad c={\tilde {\gamma }}K/({\tilde {\gamma }}-1).}$

Öte yandan, son kullanma tarihi sonlu olduğunda, problem bilinen kapalı form çözümü olmayan 2 boyutlu serbest sınır problemi ile ilişkilidir. Bununla birlikte, çeşitli sayısal yöntemler kullanılabilir. Bkz Black-Scholes modeli # Amerikalı seçenekleri burada çeşitli değerleme yöntemleri için, hem de fugit bir ayrık için esaslı ağaca egzersiz optimal zamanın hesaplama.

Ayrıca bakınız

• Durma sorunu
• Markov karar süreci
• Opsiyonel durdurma teoremi
• stokastik kontrol

Referanslar

• Thomas S. Ferguson , Optimal Durdurma ve Uygulamalar , alındı ​​21 Haziran 2007
• Thomas S. Ferguson , " Sekreter sorununu kim çözdü? " İstatistik Bilimi , Cilt. 4.,282–296, (1989)
• F. Thomas Bruss . "Oranları bire topla ve dur." Olasılık Annals , Cilt. 28, 1384-1391,(2000)
• F. Thomas Bruss. "Doğru karar verme sanatı: Karar vericiler neden olasılık algoritmasını bilmek ister?" Avrupa Matematik Derneği Bülteni , Sayı 62, 14–20, (2006)
• Rogerson, R.; Şimer, R.; Wright, R. (2005). "İşgücü piyasasının araştırma teorik modelleri: bir anket". İktisat Edebiyatı Dergisi . 43 (4): 959-88. JSTOR  4129380 .