Efficient inverse Z -transform and pricing barrier and lookback options with discrete monitoring

We prove a simple general formula for the expectations of a function of a random walk and its running extremum. Under additional conditions, we derive analytical formulas using the inverse Z-transform, Fourier inversion, and Wiener-Hopf factorization, and discuss efficient numerical methods for realization of these formulas. As applications, the cumulative probability distribution function of the process and its running maximum and the price of the option to exchange the maximum of a stock price for a power of the price are calculated. The most efficient numerical methods use a new efficient numerical realization of the inverse Z-transform, sinh-acceleration technique, and simplified trapezoid rule. The program in MATLAB running on a Mac with moderate characteristics achieves precision E-10 and better in several dozen milliseconds, and E-14 in a fraction of a second.