1. Speeding Up Two-Level Simulation for Tail Conditional Expectations by Means of Prefix Sum Based Algorithms.
- Author
-
Yi-Cheng Tsai, Hsin-Tsung Peng, Jan-Ming Ho, Chen, Bryant, and Ming-Yang Kao
- Subjects
- *
SIMULATION methods & models , *STOCKS (Finance) , *RISK management in business , *STOCK options , *ALGORITHMS - Abstract
In this paper, we study the problem of computing tail conditional expectations (TCE) or portfolio gains at specific times (T) in the future. We present efficient algorithms to handle the following two cases: (1) we have only one option (call or put) in our portfolio, denoted as a single-stock-single-option portfolio (SSSO); (2) we have a stock and some of its options in our portfolio, denoted as a single-stock-multiple-option portfolio (SSMO). Compared with previous simulation algorithms, our algorithms compute TCE of a given portfolio more efficiently and still maintain the same degree of accuracy. In the SSSO case, we reduce the computational time complexity from the SSSO-Naïve Algorithm's O(m*n) to SSSO algorithm's O(m+n), where m is the number of possible price outcomes for an underlying stock at time T and n is the number of possible price outcomes for an underlying stock at time U (maturity) in respect to each possible price outcome for an underlying stock at time T. In the SSMO case, we provide two algorithms to compute the TCE. The computational time complexity of the SSMO-Naive Algorithm is O(q*m*n+m*log(m)), where q is the number of options. The computational time complexities of our two algorithms are O(q*(m+n)+m*log(m)), and O(q*log(q)+n+m*q+ m*q*log(q)+m*log(m)) or O(q*log(q)+n+m*q+m*q*log(m)+m* log(m)). In both cases, our experiments show that when m and n are greater than five thousand, our algorithms run thousands of times faster than the naive algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2009