Efficient and Robust Combinatorial Option Pricing Algorithms on the Trinomial Lattice for Polynomial and Barrier Options

Options can be priced by the lattice model, the results of which converge to the theoretical option value as the lattice's number of time steps n approaches infinity. The time complexity of a common dynamic programming pricing approach on the lattice is slow (at least On2), and a large n is required to obtain accurate option values. Although On-time combinatorial pricing algorithms have been developed for the classical binomial lattice, significantly oscillating convergence behavior makes them impractical. The flexibility of trinomial lattices can be leveraged to reduce the oscillation, but there are as yet no linear-time algorithms on trinomial lattices. We develop On-time combinatorial pricing algorithms for polynomial options that cannot be analytically priced. The commonly traded plain vanilla and power options are degenerated cases of polynomial options. Barrier options that cannot be stably priced by the binomial lattice can be stably priced by our On-time algorithm on a trinomial lattice. Numerical experiments demonstrate the efficiency and accuracy of our On-time trinomial lattice algorithms.