Affiliations: [a] Department of Computer Science, University of California at Los Angeles, Los Angeles, CA, USA | [b] Department of Computer Science and Engineering, National Taiwan Ocean University, Keeling, Taiwan | [c] Institute of Information Science, Academia Sinica, Taipei, Taiwan | [d] Research Center for Information Technology Innovation, Academia Sinica, Taipei, Taiwan | [e] Department of Electrical Engineering & Computer Science, Northwestern University, Evanston, IL, USA
Correspondence:
[*]
Corresponding author: William W.Y. Hsu, Department of Computer Science and Engineering, National Taiwan Ocean University, Keeling 202, Taiwan; Institute of Information Science, Academia Sinica, Taipei 115, Taiwan. Tel.: +886 2 2462 2192; Ext. 6657; Fax: +886 2 2462 3249; E-mails: wwyhsu@ntou.edu.tw (William W.Y. Hsu); bryantrchen@gmail.com (Bryant Chen); hoho@iis.sinica.edu.tw (Jan-Ming Ho); kao@northwestern.edu (Ming-Yang Kao).
Abstract: This paper proposes novel lattice algorithms to compute tail conditional expectation of European calls and puts in linear time. We incorporate the technique of prefix-sum into tilting, trinomial, and extrapolation algorithms as well as some syntheses of these algorithms. Furthermore, we introduce fractional-step lattices to help reduce interpolation error in the extrapolation algorithms. We demonstrate the efficiency and accuracy of these algorithms with numerical results. A key finding is that combining the techniques of tilting lattice, extrapolation, and fractional steps substantially increases speed and accuracy.