Halmstad 2006
Dynamic programing and Markov chains

Jean-Philippe CHANCELIER
Version pdf de ce document
Version sans bandeaux

Table des matières

1 Stopping time problem with the Cox-Ross Model

The Cox-Ross random walk, widely used in Finance, is defined as follows. Let $ (U_n,n \geq 0)$ be a sequence of independent random variables with common law $ {\mathbb{P}}(U_n=1+b=d)=p$, $ {\mathbb{P}}(U_n=1+a=u)=1-p$ where $ 0<p<1$, $ u$ and $ d$ being two fixed real numbers. Let $ X_0=x$ and

$\displaystyle X_{n+1} = X_n U_{n+1}. $

Thus, $ X_n = x\prod_{i=1}^n U_i$. It is easy to check that $ (X_n)$ is an homogeneous Markov.

Let $ (X_{n})_{n \in {\mathbb{N}}}$ be a finite Markov chain following a Cox-Ross model, we want to recursively compute for $ n \in [0,T]$ :

$\displaystyle u_n(x)=\sup_{\tau \;{\cal F}_n t.a., n \leq \tau \leq N} {\mathbb{E}} \left[ \frac{1}{(1+r)^{\tau+1-n}} f^\tau ( X^\tau) \vert X^n=x \right]. $

We will use the following numerical values : 

r=log(1 + 0.05);    // non risky interest rate
mu=0.05;   // unused 
sigma=0.2; // volatility of risky asset 
S0=40;    // price at time 0 of the risky asset 
T=4.0/12.0;   // horizon 
K=40;     //  strike value 
N = 10;    // number of time steps 
Dt = T/N;  // step size 
R = r* Dt; // interest rate on time step 
down = (1+R) * exp(- sigma * sqrt(Dt)); // state "up"
up = (1+R) * exp(+ sigma * sqrt(Dt)); // state "down"
p = (up-(1+R))/(up-down); // probability to go down !

a=up-1; 
b=down-1;
X0=S0;

    

Question 1   For a given discrete time $ t$ compute in a vector the possible states of $ X_t$. 
  t=3;
  I=0:t;
  X=....



    

Question 2   Draw on a figure all the possible states that can be reached from X0 when discrete time evolves from 0 to $ N$ 
t=N;
xbasc();
for i=0:t
  .... 
  plot2d(...) // plot the states at time i with a mark 
end



    

Question 3   The number of possible states at time $ t$ are $ X_0(1+a)^i*(1+b)^(t-i)$ for $ i\in [0,t]$. Thus a given state at time $ t$ can be labeled by its indice $ i$. Suppose that we are at time $ t$ in a state labeled $ i$ what are the possible labels for the state at time $ t+1$. What are the probabilities of the possible states.



    

Question 4   We want now to recursively compute the value function V(x,n) and store all the results in a matrix V. The number of rows of the matrix is given by the number of possible states at the last discrete time $ t=N$. At position V(i,t) we will store the value function at time t for the state labelled i. Choosing $ f(x)=(x-K)_{+}$ or $ f(x)=(K-x)_{+}$ , give a function which recursively computes the value function $ u_n(x)$. During the computation we also want to compute U(x,n) which for a state labeled x at time n return 1 or 2 (2 if the optimal strategy is to stop).



    

Question 5   Compute also for each discrete time, the values of the state variables and plot the value function according to the state value. 
// The cost function at time T 
function y=f(x,K) .... endfunction

// at each time we compute in a column of V the function value associated to states 
// X_0(1+a)^i*(1+b)^(t-i) 

T=10;
I=0:T;
XT=... 
n=.. // maximum number of states for t in [0,T]
V=zeros(n,T); // initialize V 
X=zeros(n,T); // initialize X 


V(:,T)=...
X(:,T)=... 

for t=T-1:-1:1
  ...
  X(I+1,t)=... // I is the vector of possible indices at time t 
  V(I+1,t) =... 
end

// plot the value function at each step 

for t=1:T 
  xbasc();
  I=0:t;
  plot2d(X(I+1,t),V(I+1,t))
  halt();
end



    

Question 6   Use the U matrix to plot the tree of discrete value for the state according to time using a different mark for stopping or non-stopping states.



    

Question 7   Use the previous code to implement a function which computes the value function at time $ t$ for a given grid of state values. Draw these functions for time evolving from 0 to $ N$.