Halmstad 2006
Dynamic programing and Markov chains

Jean-Philippe CHANCELIER

Version pdf de ce document
Version sans bandeaux

Table des matières

• 1 Stoping time problem

1 Stoping time problem

Let $(X_{n})_{n \in {\mathbb{N}}}$ be a finite Markov chain with transition matrix $M^{(n)}$. We want to compute :

$$u_n(x)=\sup_{\tau \;{\cal F}_n t.a., n \leq \tau \leq N} {\mathbb... ...eft[ \sum_{k=n}^{\tau-1} c^{(k)}(X^k)+\psi^\tau ( X^\tau) \vert X^n=x \right].$$

The control is a stopping time $n \le \tau \le N$. As shown in the course the value function can be recursively computed by :

$$\left\{ \begin{array}{ll} u_{n}(x) &= \max(M^{(n)} u_{n+1} +c^{(n)}, \psi^{n}), \; \; n=0,\ldots, N-1 u_N &= \psi^N. \end{array} \right.$$ (1)

And the optimal stopping time :

$$\tau_n = \inf \{ N \ge k \geq n, u_k(X^k) = \psi^k(X^k) \}$$

is such that :

$$u_n(X^n)= {\mathbb{E}} \left[ \sum_{k=n}^{\tau_n-1} c^{(k)}(X^k)+\psi^{\tau_n}(X^{\tau_n})\vert X^n \right].$$

    

Question 1   Write a first routine which returns a stochastic matrix $M$ of size NxN.

    

Question 2   Using the choosen matrix $M$ generate ans plot some samples of the homogeneous Markov chain with states in $[1,N]$ described by $M$ (using grand in Scilab).

    

Question 3   Choosing an instantaneous cost $c$ and a final cost $K$ recusively compute the value function $v^n(x)$ and draw the result as a surface (i.e $v(x,t)$). Compute also $u^n(x)$ which for a given state at time $n$ returns $1$ if the optimal strategy is to go on and $2$ is the optimal strategy is to stop. Note that the max function can be used to get the maximum value of two quantities but also to get the indice of the value which realize the max.

// A stoping time problem. 
c=... // instantaneous cost 
K=... // final cost 

r=0.05;
C=ones(N,T); // a matrix to store the value function 
U=2*ones(N,T); // a matrix to store the control (1 or 2) 

C(:,T) = ... ; 

for i=T-1:-1:1 
  .... 
  C(:,i)= Ci;
  U(:,i)= ki;
end

plot3d(1:N,1:T,C)

    

Question 4   Using samples of the markov chain for a given starting state evaluate by Monte Carlo the cost function $v_0(1)$ and compare the results with previous question.

m=10000; // number of samplings 
Cm=0;    // we want to evaluate C(1,1);
for k=1:m  // loop on sampling 
  // the k-th trajectory.
  X=.... // sample a trajectory 
  // the control along the trajectory 
  for i=1:T, u(i)=... end
  stop=... // the stopping time 
  cost=0; 
  ... 
  cost = .. // evaluate the cost for the m-th trajectory
  Cm=Cm+cost/m; // compute the mean 
end