数理解析研究所講究録
第 1554 巻 2007 年 56-63

56

アメリカン・アジアンオプションの価格付けに対する計算幾何手法を用いた近似アルゴリズム
渋谷彰信 (Akinobu Shibuya)

塩浦昭義 (Akiyoshi Shioura)
東北大学大学院情報科学研究科

徳山豪 (Takeshi Tokuyama)

Graduate School of Information Sciences, Tohoku University

1

はじめに

オプションとは, 金融市場で取引されている金融派生商晶 (デリバティブ) の一つである. 本論
文では, アメリカンアジアンオプションと呼ばれるオプションに対し, オプション価格の近似

値を効率的に求めるアルゴリズムを提案する.
狭義には, オプションは株式などの原資産を, 指定された時点もしくは期間に, 決められた価格で売買する権利のことである. より広義には. オプションは原資産の価格の履歴に依存して決まる報酬 (ペイオフと呼ばれる) をオプションの所有者が得ることができる, という契約である.
オプションは資産売買に伴うリスクのヘッジや, 少ない投資で多額の利益を得るという目的のために使われている. 様々なオプションが世界の金融市場で取引されている現在, オプションの適正な価格付けは重要な計算問題となっている.
本論文では, 資産価格の変動を離散的に表現する確率モデルである 2 項モデル ([1] 参照) において, アメリカンアジアンオプションの価格を計算する, という問題を扱う. オプションの価格は(利子を割り引いた) ペイオフの期待値として与えられるので, アメリカンアジアンオブションのペイオフの期待値を計算する問題と言い換えることができる. この問題は非常に計算困難な問題であるが, その主な理由は次の 2 つである.
1 っ目の理由は、 このオプションがアジアン型であり, ペイオフの値が資産価格の過去の履歴に依存するので, 厳密値の計算のためには資産価格の履歴の全ての可能性を列挙しなければならな
い, ということである. したがって, アジアンオプションの価格を厳密に計算するには指数時間が必要となる. 現実的な問題を解くためにはオプション価格の近似値を高速に求めるアルゴリズ
ムが求められる.

2 つ目の理由は, アメリカンオプションでは任意の時期において権利行使が可能であるが, 最適な行使時期の決定は計算困難である, ということである. 例えば, モンテカルロ法はオプショ

ン価格の近似アルゴリズムとしてしばしば用いられ成功を収めているが, アメリカンオプションの場合にはその行使時期決定の問題からモンテカルロ法の適用には様々な工夫が必要とされる.
2 項モデルにおけるアメリカンアジアンオプションの近似アルゴリズムは HuU-White [31, Neave[5], Chalasa 並ほか [4], Dai ほか [2] によって提案されている. しかし, いずれのアルゴリズムについても近似精度は実験的に検証されているだけであり, 理論的な近似精度保証は与えられていない. アメリカン. アジアンオプションの価格付けに対して近似精度を理論的に保証した近似アルゴリズムは著者らの知る限りこれまでに提案されていない.
本論文では, アメリカン. アジアンオブションの価格付けに対し, 近似精度を保証する多項式時
間近似アルゴリズムを提案する. アメリカン・アジアンオプションの価格の厳密値は, 各時点でのベイオフの期待値を表す区分線形関数を繰り返し計算することにより求めることが可能である.
しかし, 計算の過程で区分線形関数の複雑度は指数オーダーとなり, 計算には指数時間が必要となる. これに対し, 本論文では計算幾何学的な手法を用いて区分線形関数をより複雑度の小さい
区分線形関数により近似する. これにより, 近似精度を保証しっつアルゴリズムの高速化を計る.

57

格が書かれている.

2

準備

2 項モデル 深さ の 2 項木とは, 以下のように定義される閉路を持たない有向グラフのことである (図 1 参照). 深さ の 2 項木は $n+1$ 個のレベルをもつ. 第 番目 $(0\leq i\leq n)$ のレベル
レベルには $i+1$ 個のノードがあり, 各ノードは $(i,j)(0\leq j\leq i)$ のようなラベルをもつ. 第$(i<n)$ の各ノード $(i,j)$ は 2 つのノード $(i+1,j),$ $(i+1,j+1)$ への有向枝をもつ.
2 項モデルは, 資産価格の変動を離散的に表現した確率モデルであり, 資産価格の変動は 2 項木を使って表現される (図 1 参照). 2 項モデルでは, 現時点からオプションの満期までの期間を第 期期間に分割し, 現時点を第 期, 分割された各期間の終了時を順に第 1 期, 第 2 期, ..
と呼ぷことにする. 第 期はオプションの満期に対応する. 既知である現時点の資産価格を $S0$ とという確率変数により表す. 2 項モデルでおき, 各 $i=1,2,$ $\ldots,n$ に対し第 期の資産価格をは. 各期において資産価格は確率 で $uS$ に上がる, もしくは確率 $1-p$ で $dS$ に下がる, といは定数であり, $u>d$ および $u=1/d$ を満たす. 2 項モデとう 2 通りのみを考える. ここでルでは, 2 項木の第 レベルの頂点により第 期の資産価格を表す. 第 期 $(i<n)$ のノード $(i,j)$
$n$

$i$

$n$

$i$

.

$0$

$n$

$n$

$n$

$i$

$S_{i}$

$p$

$u$

$d$

$i$

$i$

$i$

における資彦価格が $S$ であるとすると, 資産価格が $uS$ に増加するときはノード $(i+1,j)$ に移動
し, 資産価格が $uS$ に減少するときはノード $(i+1,j+1)$ に移動する. したがって, ノード $(i,j)$
における資産価格は $S_{i,j}=u^{i-j}d^{j}S_{0}$ と表せる.

オプション オブションは, 株式などの原資産を, 指定された時点もしくは期間に. 決められた価格で売買する権利のことである. 原資産を指定価格で買う権利のことをコールオプション, 指
定価格で売る権利のことをプットオプションと呼ぶ. 本論文ではコールオプションに限定して話を進めるが, 本論文の主結果はプットオブションについても同様に成り立っ.
もっとも基本的なオプションであるヨーロピアンオプションは, 満期と呼ばれる将来の決められた時点において, 行使価格と呼ばれる価格で原資産を買う権利のことである. 行使価格が $X$ のが $X$ より大きい場合には, オプションを行使して資産を価格 $X$
とき, 満期における資産価格で購入し, 直ちに市場価格で資産を売ることにより $S_{n}-X$ の利益を得る. したがって, ヨー$S_{n}$$S_{n}$

ロッパオブションにより得られるペイオフは $\max\{S_{n}-X, 0\}$ と表せる.
一方, アメリカンオブションでは満期までの任意の時点において権利行使が可能である. ヨー
ロピアンオブションと同様の考え方により, 第 期においてアメリカンオプションを行使すると$i$$\max\{S_{i}-X,0\}$というペイオフが得られる. 満期以外の期においてオプションを行使することを

58
早期行使というが, アメリカンオプションでは各期において権利を早期行使するか否かの決定をする必要がある. そのためには, 権利を早期行使した場合のペイオフと早期行使しなかった場合のペイオフの期待値を計算し, 比較する必要があるが, ペイオフの期待値の計算は本質的にオプ
ション価格の計算と等価な問題であり, 非常に困難である.

次にアジアンオプションについて説明する. オプションの行使価格が $X$ のとき, 先に紹介した 2
っのオプションのペイオフは権利行使時点での資産価格呂に依存していたが, アジアンオプショ
ンのペイオフ値は過去の資産価格の平均値 $A_{i}=( \sum_{k-\triangleleft}^{1}S_{k})/(i+1)$ に依存する. 例えば, ヨーロ
ピアン・アジアンオブションの場合には権利は満期においてのみ行使可能であり, そのペイオフ
は $\max\{A_{n}-X, 0\}$ となる. また, アメリカン・アジアンオプションの場合には任意の時点で権利を行使可能であり, 第 期で行使した場合にはペイオフが $\max\{A_{i}-X, 0\}$ となる.
$i$

3

オプション価格の厳密値の計算

アメリカンアジアンオプションの価格の厳密値 $U$ を計算するアルゴリズムについて説明する.
各ノード $(i,j)$ に対し, 根 $(0,0)$ から (i, のに至るパスのノードにおける資産価格の合計値をノード (i, のでのペイオフの期待値は資産価格の合計値 $T$ の関数として表せる$T=T_{i,j}$ とおく.
が, これを $f_{i,j}(T)$ とおき, 期待ペイオフ関数と呼ぷことにする. すると, オプション価格の厳密
値 $U$ は. ノード $(0,0)$ での期待ペイオフ関数の初期資産価格 $T=S0$ における値 $fo,o(S_{0})$ として与えられる. したがって, オプション価格の厳密値を計算するためには, ノード $(0,0)$ における期待ペイオフ関数ん,o(T) を計算すれば良い. 本節で紹介するアルゴリズムは, 各ノードの期待ペイオフ関数 $f_{*,j}(T)$ を第 期のノード 第 $n-1$ 期のノード, . .., 第 期のノード, という順に後進的に求めていき. 最終的に $fo,o(T)$ を求める.
について考える. 第まず, 満期である第 期のノード (n, のにおける期待ペイオフ関数は次のよう期では. 権利行使するかしないかの 2 つの選択肢があるため, 期待ペイオフ関数に与えられる.
$0$$n$$f_{n,j}$

$n$

$n$

$f_{n,j}$$f_{n},j(T)= \max(0,$ $\frac{T}{n+1}-x)$.

(1)について考える. 第 期で次に, 第 期 $(i<n)$ のノード $(i,j)$ における期待ペイオフ関数
権利を早期行使する場合のペイオフ
は, 権利を早期行使するかしないかの 2 つの選択肢がある.
と表飢 すると,早期行使しない場合のペイオフの期待値を
の期待値を
$i$

$i$

$f_{i,j}$$f_{i,j}^{P}(T)$$f_{8j}^{B}(T)_{*})$(2)$f_{i,j}(T)= \max(f_{i}^{E_{j}}(T), f_{i}^{P_{j}}(T))$の計算方法を説明する.
については, 第 期のノードの場合と同様の権利を早期行使する場合のペイオフの期待値
考え方により, 次の式により与えられる.

が成り立っ. 以下では

$f_{i}^{E_{j}}(T)$および$f_{i}^{P_{j}}(T)$$n$$f_{i}^{E_{j}}$$f_{\mathfrak{i},j}^{E}(T)= \max(0,$ $\frac{T}{i+1}-x)$.

(3)の計算方法を説明する. ノード $(i,j)$
次に, 権利を早期行使しない場合のペイオフの期待値のから確率 でノード $(i+1,j)$ へ移動し, 確率 $1-p$ でノード $(i+1,j+1)$ へ移動するので,$f_{1,j}^{P}$$f_{i}^{P_{j}}$$P$

値は次のようになる.
$f_{i,j}^{P}(T)=e^{-r\Delta t}[pf_{1+1,j}(T+uS_{i,j})+(1-p)f_{i+1,j+1}(T+dS_{1j})]$

.

(4)

59
ここで右辺の値は 1 期間分の利子を割り引いたものになっている.
以上の式 (1), (2), (3), (4) を用いて再帰的に計算することにより, 各期におけるノードの期待ペイオフ関数が得られる.
最後にこのアルゴリズムの時間および空間計算量について議論する. その定義により, 期待ペイオフ関数
は区分線形な凸関数であるが, アルゴリズムの計算量はその区分線形関数の線分の数に比例する. 式 (2), (3), (4) を使って関数 $f_{i+1,j}(T),$ $f_{i+1,j+1}(T)$ から関数 $f_{1j}(T)$ を求める際, 線分の数は最悪の場合 2 倍に増えてしまう. このことより, 本節で紹介したアルゴリズムの時間計算量は $O(n2^{n})$ , 空間計算量は $O(2^{n})$ となる.
$e^{-r\Delta t}$$f_{\dot{*},J}(T)$4

オプション価格の近似アルゴリズム

4.1

アルゴリズムの概要

本節では, オプション価格の近似値を求めるアルゴリズムを提案する. 提案するアルゴリズム
は, 与えられた近似誤差パラメータ $\epsilon(>0)$ に対し. $U\leq\Phi\leq(1+\epsilon)U$ を満たす近似値
を求める.
$\Phi$

提案する近似アルゴリズムは, 前節で紹介した厳密値を求めるアルゴリズムを修正したものになっている. 厳密値を求めるアルゴリズムでは. 区分線形関数 $f_{i,j}(T)$ の線分の数が最悪の場合に指数オーダーとなっていた. 提案する近似アルゴリズムでは, 関数 $f_{1j}(T)$ を求める代わりに. 多

項式個の線分をもつ区分線形関数 $g_{i}J(T)$ により関数 $f_{i},’(T)$ を近似する. これにより, 多項式時
間アルゴリズムを実現するとともに, 求められた近似値の精度を保証する.
提案する近似アルゴリズムの流れは以下のようになる. まず, 満期である第 期のノード $(n,j)$$n$においては.

$g_{n,j}(T)=f_{n,j}(T)$$g_{i,j}^{E}(T),g_{1j}^{P}(T)$とおく. 次に, 第 期 $(i<n)$ のノード (i, のについては, 関数$i$を$g_{i,j}^{E}(T)=f_{i,j}^{E}(T)$,$g_{i,j}^{P}(T)=e^{-}n\underline{r}_{\Lambda}[pg_{i+1,j}(T+uS_{t,j})+(1-p)g_{i+1,j+1}(T+dS_{1j})]$により定義し,$\sim g_{i,j}(T)=\max(g_{i,j}^{E}(T),g_{i,j}^{P}(T))$

とおく. 区分線形凸関数

を, 線分の数の少ない区分線形関数で近似したものを $g_{i,j}(T)$ と定める. ここで用いる区分線形凸関数の近似方法については第 42 節で詳しく説明する.
このようにして後進的に $f_{i,j}(T)$ の近似関数 $gt,J(T)$ を求めたら, 関数値 $\Phi=g0,o(S_{0})$ をオプ$g_{l}\sim,’(T)$ション価格の近似値として出力する.

42

計算幾何学手法を用いた区分線形凸関数の近似

以下では, 区間 $[0, +\infty$ ) 上で定義された, 単調非減少かつ非負の値をとる区分線形凸関数 $g\sim(T)$および膿差パラメータ $\delta(0<\delta\leq 1)$ が与えられたとき,$\sim g(T)\leq g(T)\leq(1+\delta)g\sim(T)$$(0\leq T<+\infty)$を満たす区分線形凸関数 $g(T)$ を求める 2 つの方法について説明する.

(5)

60

図 2: 近似方法その 1

4.2.1

近似方法その 1のを満たす最小の値 $T_{0}(\geq 0)$ , および $T=T_{0}$ における関数
を通過する傾き $(1+\delta)a_{0}$ の直腺を求める (図 2 参照). そして. 点
右側微分係数とする.
との交点をを描き, その直線と関数を求める. そして, 点 (T1,\tilde (乃)) を通過すの右側微分係数
次に, $T=T_{1}$ おける関数
とする.
との交点を
る傾き $(1+\delta)a_{1}$ の直線を描き, その直線と関数を通過する傾き回目 $(k\geq 0)$ の反復に入ったとき. 点
この操作を繰り返し,関数を次の式によ$g(T)$
このとき,が交点をもたなかったとする.
$(1+\delta)a_{k}$ の直線と関数り定義する.

まず,$g\sim(T)>0(\forall T>T_{0})$$g\sim(T)$$(T_{0},g\sim(T_{0}))$$a_{0}$$(T_{1},g\sim(T_{1}))$$g\sim(T)$$\sim g(T)$$a_{1}$$g\sim(T)$$(T_{2},g\sim(T_{2}))$$(T_{k},g\sim(T_{k}))$$k$$g\sim(T)$$g(T)=\{\begin{array}{ll}0 (0\leq T<T_{0}),(l+\delta)ao(T- TD+9(\text{乃}) (To\leq T\leq T_{1}),:.

(1+\delta)a_{k-1}(T-T_{k-1})+\tilde{g}(T_{k-1}) (T_{k-1}<T\leq T_{k}),a_{\max}(T-T_{k})+\tilde{g}(T_{k}) (T_{k}<T<+\infty).\end{array}$

関数の線分の傾きの最大値をヘユとおいた. この関数 $g(T)$ が条件 (5) を満たす
ことは, その定義より明らかである.
に対して
ここで, 区分線形関数 $g(T)$ の線分の数について解析を行う. 傾き $a0,$

ここで,$\sim g(T)$$a_{i},$$a_{i}>(1+\delta)a:-1$$\ldots,$$a_{k}$$(i=1,2,\ldots,k)$が成り立っ. これより, $a_{\max}\geq a_{k}>(1+\delta)^{k}a0$ が導かれる. ゆえに, $\log(1+\delta)>\delta/2(0\leq\forall\delta\leq 1)$という事実を使うと,$k< \frac{2\log(a_{\max}/a_{0})}{\delta}$という不等式が得られる. なお,値である.

$a_{0}$

は関数$g\sim(T)$の線分の傾きのうち, 非零のものの中での最小61

図 3: 近似方法その 2

4.2.2

近似方法その 2

この方法では, 2 つの関数\tilde g(T) と $(1+\delta)g\sim(T)$ に対し, この 2 つに挟まれるような区分線形関数を描く (図 3 参照). そのとき, 一つ一つの線分がなるべく長くなるように 「食欲」 に関数を描いていく.

より具体的には以下の通りである. 第 421 節と同様にを定める. 点 $(T_{0}, f(T_{0}))$ から右側に線分を描くが, その傾きが最大になるようにする. すなわち,$\tau_{0}$$b_{0}$$b_{0}(T-T_{0})+f(T_{0})\leq(1+\delta)g\sim(T)$$(\forall T\geq T_{0})$の条件のもとで最大の恥を求める.

そして, 直線 $b_{0}(T-T_{0})+f(T_{0})$ とる) 交点を $(T_{1}, f(T_{1}))$ とする.
次に, 点 $(T_{1}, f(T_{1}))$ から右側に線分を描くが, その傾きが$g\sim(T)$の (To の右側にあ$b_{1}$$b_{1}(T-T_{1})+f(T_{1})\leq(1+\delta)_{9}^{\sim}(T)$$(\forall T\geq T_{1})$の条件のもとで最大になるようにする. そして, 直線 $b_{1}(T-T_{1})+f(T_{1})$ とある) 交点を $(T_{2},f(T_{2}))$ とする.
この操作を繰り返し,$k$$g\sim(T)$の ($T_{1}$

回目 $(k\geq 0)$ の反復に入ったとき, 直線 $b_{k}(T-T_{k})+f(T_{k})$ と寡の右側において交わりをもたなかったとする. すると,
このとき, 関数 $g(T)$ を次の式により定義する.

$g(T)=\{\begin{array}{ll}0 (0\leq T\leq T_{0}),(1+\delta)b_{0}(T-T_{0})+\tilde{g}(T_{0}) (T_{0}<T\leq T_{1}),:$a_{\max}\leq b_{k}\leq(1+\delta)a_{\max}$の右側に$\sim g(T)$が,が成り立っ.

(1+\delta)b_{k-1}(T-T_{k-1})+\tilde{g}(T_{k-1}) (T_{k-1}<T\leq T_{k}),a_{\max}(T-T_{k})+\tilde{g}(T_{k}) (T_{k}<T<+\infty).\end{array}$

以下では, この近似方法で得られた区分線形関数 $g(T)$ の線分の数の最悪値オーダーが, 第 1 の近似方法のオーダー $O(\log(a_{\iota nax}/a_{0})/\delta)$ に等しいことを示す. そのためには,$b_{i}>(1+\delta)b_{\mathfrak{i}-1}$$(i=1,2, \ldots,k-1)$

(6)

62
を示せば十分である.
関数の $T=T_{i}$$g\sim(T)$での右側微分係数を$\alpha_{i}$とおく. すると $\alpha_{i}>b_{1-1}$ が成り立っ. また. 線

分 $(1+\delta)b_{i}(T-$ 丁の $+\overline{g}(T_{i})(T_{i}<T<T_{i+1})$ は, $T_{i}<T_{*}<T_{i+1}$ を満たすある処において関数とおく$(1+\delta)g\sim(T)$ に接しているが,
関数 $(1+\delta)g\sim(T)$ の $T=T_{*}$ での左側微分係数をが成り立つ. 以上の不等式をまと,醜が成り立っ. さらに, $T_{i}<T_{*}$ なので$(1+\delta)\alpha_{i}’$$\alpha_{i}\leq\alpha_{i}’$$(1+\delta)\alpha_{i}’\leq$

とめると. (6) が導かれる.

4.3

アルゴリズムの解析

第 4.1 節で説明した近似アルゴリズムに. 第 4.2 節で提案した区分線形関数の近似手法を組み合わせたときの. アルゴリズムの近似精度と時間計算量を解析する.

4.3.1

近似鶉度

第 42 節で述べたように, 近似アルゴリズムで求められた関数 $g_{i},j(T)$ は $i<n$ のときに条件$(0\leq T<+\infty)$$g_{1j}\sim,(T)\leq g_{i,j}(T)\leq(1+\delta)g_{i,j}\sim(T)$を満たす. また, その定義により $g_{\hslash},j(T)=f_{n,j}(T)$ が成り立っ.

$(0\leq T<+\infty)$$f_{i,j}(T)\leq g_{i,j}(T)\leq(1+\delta)^{n-i}f_{i,j}(T)$が示せる.

したがって, 帰納法によりとくに, アルゴリズムの出力 $\Phi=g0,o(S_{0})$ に対して
$U=f_{0,0}(S_{0})\leq\Phi\leq(1+\delta)^{n}f_{0,0}(S_{0})=(1+\delta)^{\mathfrak{n}}U$が成り立っ. よって, 与えられた近似誤差パラメータ$\epsilon$に対して$\delta=\epsilon/2n$とおけば$U\leq\Phi\leq(1+\epsilon)U$が導かれる.

4.3.2

時間計算量

区分線形関数 $g_{i}j(T)(0\leq i\leq n, 0\leq j\leq i)$ の線分の数の最大値を $m$ とする. 各ノード $(i,j)$での関数 $g_{i,j}(T)$ の計算は $o(m)$ 時間で出来るので, アルゴリズム全体での計算時間は $O(n^{2}m)$ 時
間となる.
次に. $m$ のオーダーを求めるために, 関数 $g_{i,j}(T)$ の線分の数を解析する. 第 42 節の結果よ
の線分の傾
は関数
り, 線分の数のオーダーは $o(\log(a_{\max}/ao)/\delta)$ である. ここで,の線分の傾きのうち, 非零のものの中での最小値である.
は関数
きの最大値,
傾き am。については, 帰納的により $1/(i+1)$ に等しいことを証明できる. また, 関数$a_{\max}$$g_{1}\sim,:l(T)$$g_{i}\sim,’(T)$$a_{0}$$\sim 9i,j(T)$かっ関数 $f_{i,j}(T)$ の線分の傾きのうち非零のものは $\{\min(p,$ $1-$$p)\}^{n}/(n+1)$ 以上であることが示せるので, $a_{0} \geq\{\min(p, 1-p)\}^{n}/(n+1)$ が成り立っ.
以上の事実より, 関数 $g_{i}j(T)$ の線分の数のオーダーは, 確率 を定数と見なすと,は $\sim g_{i},(T)\geq f_{i,j}(T)$ を満たし,

$P$

$O$

( log
$\frac{1}{\delta}$$\frac{a_{\max}}{a_{0}})=O(\frac{1}{\delta}$

log $\frac{n+1}{(i+1)\{m\dot{m}(p,1-p)\}^{n}})=O(\frac{n}{\delta})$

63
となる.

したがって, 第 43.1 節で求めた次の結果を得る.

.

$\delta$の決め方と合わせると, 値 $m$ のオーダーは定理 4. $l$ 提案した近似アルゴリズムは
を求める.
近似値

$O(n^{4}/\epsilon)$$O(n^{2}/\epsilon)$となり,の計算時間で $U\leq\Phi\leq(1+\epsilon)U$ を満たす $U$ の$\Phi$

なお, 第 42 節で提案した 2 つの区分線形関数の近似手法のどちらを用いても, 理論的な結果は同じであるが, 計算機実験をしたところ性能に大きな違いが現れた.

どちらの近似手法を用いた場合でも, 実際に得られた近似値の精度は理論値 よりかなり小さ
かったが, 第 1 の近似方法を適用した場合には極めて良い精度が得られた. 例えば. 実験で $\epsilon=0.1$と設定したときに, 第 2 の方法の誤差は最大で 003 であったのに対し, 第 1 の方法では 0005 程度であった. これは, 第 1 の近似方法により得られる関数を非常に良く近似しが元の関数$\epsilon$$g_{t,j}$$f_{i,j}$ていることを示している.

次に計算時間であるが, どちらの方法でもほぼ理論値通りのオーダーで計算時間は増加しているが, 第 2 の方法の計算時間は第 1 の方法に比べ 4 分の 1 程度である. これは. 第 2 の近似方法
により得られる関数の線分の数が第 1 の方法に比べ非常に少ないことを示している.
$g_{i,j}$4.4

アルゴリズム 1 の計算時間の改良であったが. 近似の際に加法的誤差(additive error) を許すことにより, 計算時間を $O(n^{3}\log n/\epsilon)$ に減らすことができる.
前節で握案した近似アルゴリズムで求められた近似関数の最小の傾きの値は $\{\min(p,$ $1-$$p)\}^{n}/(n+1)$ まで小さくなる可能性があった. これにより, 近似関数の腺分の数のオーダーがと大きくなっていた. これに対し. 近似関数の最小の傾きの値が与えられたしきい値より常に大きくなるようにアルゴリズムを改良することで, 近似関数の線分の数の増加を防ぐ. この改良により, 近似関数の線分の数のオーダーを $O(n\log n/\epsilon)$ と削減することができる. 詳細については省略する.

前節で提案した近似アルゴリズムの計算時間は$O(n^{4}/\epsilon)$$g_{i,j}$$O(n^{2}/\epsilon)$

参考文献[1] J. C. Cox, S. A. Ross, and M. Rubenstein, Option pricing: a simplified approach, J. Financial Econ. 7 (1979), 229-263.
[2] T.-S. Dai, G.-S. Huang, and Y.-D. Lyuu, Extremely accurate and efficient tree algorithms
for Asian options with range bounds, 2002 NTU Int 1 Conf. on Finance, National 丁団 wan
University, Taiwan, May 2002.
[3] J. Hull and A. White, Efficient procedures for valuing European and Americen pathdependent options, J. Derivatives 1 (1993), 21-31.

[4] P. Chalasani, S. Jha, F. Egriboyun, and A. Varikooty, A reflned binominal lattice for pricing
American Asian options, Review of Derivatives Research 3 (1999), 85-105.

[5] E. H. Neave, A frequency distribution method for valuing average options, ASTIN Buletin
27 (1997), 173-205.