Problem 1.1 When pricing an American option, the dynamic programming principle states that (with time-discretized decision-making) V-At = max{P(X-At), eAtEtat [V]}, where P(X) denotes the payoff of executing the option at time t and E, is the risk-neutral expectation conditioned at time t. Given asset prices Xt, the payoff is known, but Et-At[Vt] is not. One method of solving this is to evaluate Et-At[V] by Monte-Carlo simulation. However, we need the expectation for every possible value of Xt, so a naive implementation is likely to suffer from performance issues. The following method combines Monte Carlo with linear regression in an efficient way. Given simulated asset prices Xt, each path will be associated with a sequence of option values V. At maturity, the value is know to be VT = P(XT)+. Least Squares Monte-Carlo iterates backward using dynamic programming to construct the values along the full path. Given V values for each sample, step back to time t - At and 1. Construct polynomials of asset prices Construct polynomial variables as N-vectors = Xt for d = 0, 1, ...,p and p 5; So xa are powers of the stock prices at time t - At. t-At 2. Regress the continuation value on current asset prices For each sample i, we have (x,...,x) and a corresponding value for V. Using these values, run the least squares regression V = a Baxa+e and compute the estimate V =a Baxd, i.e., regress V on the xa variables and compute the prediction; Hint: Use the backslash operator to run the linear regression.