Redeconomia.org.ve

Sergio Rojas, Ph.D.(srojas@usb.ve) Dpto. de F´ısica, USB MULTINOMIAL (FINITE BETHE) TREES AND THE NUMERICAL Sergio Rojassrojas@usb.veDepto. de F´ısica, Universidad Sim´on Bol´ıvar, Ofic. 220, Apdo. 89000, Caracas 1080A,Venezuela.
Abstract. Accurate valuation of financial instruments via efficient computational methodsis among the most important and challenging problem in the modern financial industry. Willbe presenting numerical estimates for the price of American options based in a simulationalgorithm presented by Broadie, M. and Glasserman, P. (1997), Journal of Economic Dy-namics and Control, 21, 1323-1352. The approach is based on multinomial tree methods andprovides two estimates, one biased high and one biased low, unbiased converging to the trueprice of the option. Our implementation shows agreement with the pricing of a put Ameri-can option valued via the other pricing tecniques, including the binomial tree approach. Adiscussion related to the accuracy of each estimate price and the number of branches in thetree is also presented.
Keywords: Trinomial trees, American options, Derivative pricing, Financial engineering,Free boundary.
Options are financial instruments that give the holder the right to buy (call option) or sell (put option) the underlying asset (i.e. a stock, a currency or the temperature at somelocation). Accordingly, since a right without obligation has a value in the financial industry,to hold an option one needs to pay certain amount and consequently one needs to value theoption under consideration.
Call and put are among the most basic type of options. While a call option gives the holder the right to buy the underlying asset by a certain date T (known as expiration ormaturity date) for a certain prespecified price K (known as exercise or strike price), a putoption gives the holder the right to sell the underlying asset by a certain date for a certainprice. In addition, whenever the holder could exercise its right at any time up to the expiration Sergio Rojas, Ph.D.(srojas@usb.ve) Dpto. de F´ısica, USB date, one is in front of an American type option. If the holder could exercise its right onlyon the expiration date, one is dealing with an European type option [1, 2].
Most of the options traded on exchanges (including equity, fixed income, commodity and credit financial markets) are of the American type. Hence the importance of properly valuingsuch options and the literature on the subject, since the appearance in 1973 of the seminalwork by Black and Scholes [3] and Merton [4], is copious and overwhelming. Nevertheless,it still remains a topic of active research. Recent reviews can be found in [5, 6, 7]. Thissituation has its roots in the nature of the solution which requires the determination of theoptimal exercise strategy as well as the value of the option, which requires the design andimplementation of efficient numerical procedures.
In contrast to the valuation of European options via the celebrated Black Scholes for- mula, this equation does not has closed form solutions for American option valuation problems[7]. Correspondingly, a vast array of approximation schemes has been advanced to tackle thisimportant problem, which include standard numerical techniques for partial differential equa-tions [8, 9], path-simulation models via Monte Carlo sampling [10], finite Bethe lattice ormultinomial random tree techniques [11], and quantum field theory sophisticated approach[12], which is just one of the many fruitful attempts of applying recent computational devel-opments of physics to the field of financial engineering [13, 14, 15, 16].
In this article we’ll be considering an implementation of the multinomial random tree algorithm proposed in [11] for the pricing of path-dependent American options, which hasbeen recently reviewed in [17, 6, 10]. The technique is essentially a graph with values of thenodes at each branch determined via Monte Carlo sampling. A glance to the geometry ofthe setup (i.e. Fig. 1) resembles what is known in statistical physics as a finite Caley orBethe tree, which is a successful modeling alternative for analyzing phase transitions andfinding critical exponents in some physical systems [18]. Let’s just mention the idea that theunderlying methodology of the Bethe tree in dealing with the Ising model, properly adaptedcould eventually be applied to price continuous American options, which will enlarge the listof the methods of statistical physics applied to financial modeling.
The American option pricing problem is to find C = maxE[e−rτ (Sτ − K)+] over all stopping times τ ≤ T (r is the riskless rate of interest and Sτ is the stock price at timeτ ). The idea is to simulate a path of asset prices S0, S1, · · · , ST at corresponding times0 = t0 < t1 < · · · < td = T , then compute a discounted option value corresponding to thispath, and finally average the results over many simulated paths. Since the optimal stoppingpolicy is unknown and, correspondingly, it also must be determined using the simulation, thequestion is how to compute a discounted option value corresponding to the asset price path.
The answer to this question reported in [11], which we’ll be following closely in this section,leads to the computation of two estimators based on simulated trees, one biased high and theother biased low being both asymptotically unbiased as the computational effort increases.
The simulated trees are parametrized by the number of branches b per node. An illustrationis shown in Fig. 1a. The connection between nodes indicates the dependence structure of thestock prices (i.e. both S11 and S13 depend on S1 but neither depends on S2). That is, any two of such sequences evolve independently each one of the other. Let’s point out that the Sergio Rojas, Ph.D.(srojas@usb.ve) Dpto. de F´ısica, USB nodes at fixed time (subscript label in Fig. 1a) appear according to the order in which theyare generated, not according to their node value. Note also that at the mth time step thereare bm nodes, which indicates exponential growth in the required computational resources.
In order to specify the high (Θ) and low (θ) estimator the following notation is used [11]: Figure 1: (a) Random tree for b=3. The subscript indicates the time step (T = t = 2 in this example). (b) Example of the high estimator Θ (darker numbers) at each node of a randomtree to value a call option with a single simulated underlying asset price (lighter numbers).
Working from right to left, according to the formulation of Eqs. (1), it is obtained Θ = 9.
(c) Example of the low estimator θ (darker numbers) in the same random tree as in (b).
Working from right to left, according to the formulation of Eqs. (2), it is obtained θ = 8. Inboth cases, (b) and (c), K = 100, S0 = 100, T = 1, r = 0, and ht(x) = (x − 100)+.
• Time is indexed by subscripts t = 0, 1, 2, · · · , T .
• State variables are registered as a risk-neutralized Markov chain {St : t = 0, 1, 2, · · · , T }.
• The discount factor from time t − 1 to time t is denoted by e−Rt, Rt ≥ 0 for all t.
• ht(s) is the payoff from exercise at time t in state s.
• At expiration, the option is worth the payoff from immediate exercise (i.e. f (s) = = s] is the continuation value at time t in state s.
• The option value at time t in state s is given by f (s) = max{h According to this notation, a random tree having b branches per node is represented in the form {Si1,··· ,it : t = 0, 1, · · · , T ; ij = 1, · · · , b; j = 1, · · · , t}. For example, a realization of the Markov chain {S : t = 0, 1, · · · , T } is given by the sequence S , Si1, Si1i2, · · · , Si1,··· ,iT , and any two of such sequences evolve independently of each other once they differ in some it(Fig. 1a is an illustration).
Sergio Rojas, Ph.D.(srojas@usb.ve) Dpto. de F´ısica, USB The high estimator Θ chooses, at each node of the random tree, the maximum of the early exercise payoff and the continuation value estimated from all successor nodes. It isdefined recursively by It can be shown [11] that the estimator Θ is indeed biased high, in the sense that E[Θ0(b) ≥f0(S0)] for all b (a quantity subscripted by t = 0 does not have superscript). Figure 1b showsan example of computing the estimator Θ [10].
The low estimator θ is defined recursively by the following setup: Figure 1c shows an example of computing the low estimator θ [10]. For example, to obtainθ = 3 (node at the top on the first exercise date) we start the computation when the firstsuccessor is left out, obtaining a continuation value of (4 + 0)/2 = 2, indicating to exercisethe call option to get a payoff of 5 at that time. We repeat the averaging process by leavingout the second successor, from which we obtain a continuation value of (14 + 0)/2 = 7,indicating not to exercise the call option, so we continue to get a payoff of 4 at the nextstep. Finally, leaving out the third successor, the averaging process leads to a continuationvalue of (14 + 4)/2 = 9, which indicates not to exercise the call option, so we continue toget a payoff of 0 at the next step. The average of these payoffs leads to a value for the lowestimator θ = 3 at that node. By similar reasoning one could complete the computation atthe other nodes, to obtain the low estimator of θ = 8 at the root of the random tree.
This example makes it clear the idea on which the low estimator was built on: separation of the branches at each node into two sets, one set is used to decide whether or not to exerciseand the other set is used to estimate the continuation value. Specifically, at each node(b − 1) branches are used to estimate the exercise or continuation decision, a process which isrepeated until all the possibilities are exhausted. Then the corresponding b values obtainedare averaged to determined the option estimated value at the respective node. In [11] it isshown that this estimated value is indeed biased low, in the sense that E[θ0(b) ≤ f0(S0)] forall b.
Sergio Rojas, Ph.D.(srojas@usb.ve) Dpto. de F´ısica, USB Table 1 shows numerical results for the high (Θ) and low (θ) estimates values for a PUT American option. The number of branches (NB) at each node of the random tree for thiscomputations were set to three and five. A set of simulations (NS) were performed for severaltime steps (NT). The table also shows 95% confidence interval for each estimator and therespective standard error (SE). We also show for future reference the corresponding CPUtime (in seconds) required to obtain each row in the table.
First, results in Table 1 are consistent in the sense that the high estimate Θ is always greater than the low estimate θ. In addition, as compared with the “true” (4.1873) valueof this put American option, obtained via the binomial tree, it always happens that forreasonable values of the standard error θ < 4.1873 < Θ. Moreover, we also observe that thestandard error for each estimator decrease as we increase the number of simulations (NS)while keeping fixed the number of branches (NB) and time steps (NT). It also decrease aswe increase NT with fixed NS and NB. The same behavior is observed when NS and NT arefixed while NB is increased.
Performing the average of the two estimators for the best reported standard error, cor- responding to the line for which N S = 500, N B = 5 and N T = 6, we obtain the value 4.605+3.797 = 4.201, representing a relative error of 0.3% respect to the true price of the op- tion. In spite of this, one needs to perform further tests in order to draw a fair conclusionfrom this result, which is also in agreement with the ones reported in [11] for the Americancall options studied there.
The results reported in Table 1 also suggest that in terms of CPU time better estimated, as measured by the standard error, are computed in less time by increasing the number ofbranches (NB) rather than increasing the number of time steps (NT). See for example thelines corresponding to NS=200, NB=5 and NT=3 (case a) and compare it with the linecorresponding to NS=50, NB=3 and NT=9 (case b). The standard errors for the first caseare slightly lower than the respective value for the later case. But the amount of CPU timeto obtain the line corresponding to case b is 800 times the CPU time required to obtain thecorresponding computations for case b.
Our implementation of the algorithm reported in [11] seems to be working properly but some further tests will need to be performed. Given the generality of the method, a majorundertaking is the implementation of an efficient version in parallel. In passing, table 2 weshow the value of the option obtained by other methods. Note that these values are close tothe high estimator Θ.
Sergio Rojas, Ph.D.(srojas@usb.ve) Dpto. de F´ısica, USB Table 1: Random tree results for the high (Θ) and low (θ) estimates values for a PUTAmerican option. The parameters are Spot price S = 50; Strike price X = 51; Risk freeinterest rate r = 6%; Time to maturity T = 0.7 (years) ; Volatility v = 25%; Dividend rateq = 3%. The “true” value of this option, obtained via the binomial tree with 5000 time steps,is 4.187 Sergio Rojas, Ph.D.(srojas@usb.ve) Dpto. de F´ısica, USB Table 2: Value of the American option of Table 1 obtained according other methods via thelibrary QuantLib (a free/open-source library for quantitative finance [19]) [1] Wilmott, P., Howison, S., and Dewynne, J. The Mathematics of Financial Derivatives: A Student Introduction. Cambridge University Press.
[2] Brealey, R. A. and Myers, S. C. Principles of Corporate Finance. McGraw-Hill, sixth [3] Black, F. and Scholes, M. The pricing of options and corporate liabilities. Journal of Political Economy, 81:637–659, 1973.
[4] Merton, R. C. The theory of rational option pricing. Bell Journal of Economics and Management Science, 4:141–183, 1973.
[5] Merton, R. C. Applications of option-pricing theory: Twenty-five years later. The American Economic Review, 88(3):323–349, 1998.
[6] Broadie, M. and Detemple, J. B. Option pricing: Valuation models and applications.
Management Science, 50(9):1145–1177, 2004.
[7] Hull, J. C. Options, Futures And Other Derivatives. Prentice Hall, sixth edition, 2005.
[8] Wilmott, P., Dewynne, J., and Howison, S. Option Pricing: Mathematical Models and Computation. Oxford Financial Press.
[9] Tavella, D. and Randall, C. Pricing Financial Instruments: The Finite Difference Sergio Rojas, Ph.D.(srojas@usb.ve) Dpto. de F´ısica, USB [10] Glasserman, P. Monte Carlo Methods in Financial Engineering. Springer Verlag, 2004.
[11] Broadie, M. and Glasserman, P. Pricing american-style securities using simulation.
Journal of Economic Dynamics and Control, 21(8):1323–1352, 1997.
[12] Baaquie, B. E. and Marakani, S. Comparison of field theory models of interest rates with market data. Physical Review E, 69(036129):036129:1–8, 2004.
[13] Mantegna, R. N. and Stanley, H. E. Introduction to Econophysics: Correlations & Complexity in Finance. Cambridge University Press, 2000.
[14] Voit, J. . The Statistical Mechanics of Financial Markets. Springer, 2001.
[15] Bouchaud, J-P.M. P. Theory of Financial Risk and Derivative Pricing: From Statistical Physics to Risk Management. Cambridge University Press, 2nd. edition, 2003.
PRAMANA journal of physics, 64(5):645–660, 2005.
http://polymer.bu.edu/hes/articles/.
[17] Broadie, M. and Detemple, J. B. A stochastic mesh method for pricing high-dimensional american options. The Journal of Computational Finance, 7(4):35–72, 2004.
[18] Baxter, R. J. Exactly solved models in statistical mechanics. Academic Press, 1989.
[19] . Quantlib is currently available at http://quantlib.org/.

Source: http://www.redeconomia.org.ve/redeconomia/admin_redeconomia/uploads/investigacion/RojasS_AmericanOptions20061201542asS_AmericanOptions.pdf