Numerical methods for the exit time of a piecewise-deterministic Markov process.

*(English)*Zbl 1244.60073The paper introduces a method for numerically approximating the distribution and the moments of the first exit time of a piecewise deterministic process (PDMP) from a subset of its state space. The authors present direct approximation methods for both problems, although the moment approximations can in principle be calculated from the approximation to the distribution. In general, the method is based on the quantization of the embedded Markov chain of jump times and post-jump locations. The presented approach is flexible with respect to the domain for which the exit time is calculated in as such as the time-consuming initial problem of calculating the quantization depends only on the process and not on the domain. Storing these results off-line, the distribution and moments of exit times for different domains can be approximated very quickly. This provides an advantage over Monte-Carlo methods.

In brief the method is described as follows. First, the authors approximate the exit time \(\tau\) by \(\tau\wedge \tau_N\), where \(\tau_N\) is the \(N\)th jump time of the PDMP – for large enough \(N\), as \(\tau_N\to\infty\) almost surely is assumed, this is expected to be a reasonable approximation. The question of choosing the time horizon \(\tau_N\) is only marginally addressed in the study. Next, the problem of calculating the survivor function of \(\tau\wedge\tau_N\) and its moment is reduced to calculate two sequences which can be obtained from the Markov chain. Then the quantized Markov chain is substituted, resulting in approximations to these sequences which then in turn provide approximation to the desired quantities. The study contains a detailed list of assumptions on the local characteristics defining PDMPs and quantities related to the exit time problems under which the authors prove convergence of the quantized sequences to the exact sequences when the quantization error converges to zero. This then extends to the pointwise convergence almost everywhere of the survivor function of the exit time and to the convergence of the moments. For the latter, additionally, also a rate of convergence is obtained.

The findings are illustrated by two numerical examples. The first, a simple Poisson process example allows for the exact calculation of the distribution of the exit time. The authors compare the exact and approximate survivor functions and also the first and second moments. They find good agreement with their theoretical results. The second, more realistic example is a corrosion model. The authors show that the conditions of their theorems are satisfied. They calculate approximations of the distribution and the mean exit time and compare them to Monte-Carlo estimates of these quantities. Again a good agreement with the theory is found.

In brief the method is described as follows. First, the authors approximate the exit time \(\tau\) by \(\tau\wedge \tau_N\), where \(\tau_N\) is the \(N\)th jump time of the PDMP – for large enough \(N\), as \(\tau_N\to\infty\) almost surely is assumed, this is expected to be a reasonable approximation. The question of choosing the time horizon \(\tau_N\) is only marginally addressed in the study. Next, the problem of calculating the survivor function of \(\tau\wedge\tau_N\) and its moment is reduced to calculate two sequences which can be obtained from the Markov chain. Then the quantized Markov chain is substituted, resulting in approximations to these sequences which then in turn provide approximation to the desired quantities. The study contains a detailed list of assumptions on the local characteristics defining PDMPs and quantities related to the exit time problems under which the authors prove convergence of the quantized sequences to the exact sequences when the quantization error converges to zero. This then extends to the pointwise convergence almost everywhere of the survivor function of the exit time and to the convergence of the moments. For the latter, additionally, also a rate of convergence is obtained.

The findings are illustrated by two numerical examples. The first, a simple Poisson process example allows for the exact calculation of the distribution of the exit time. The authors compare the exact and approximate survivor functions and also the first and second moments. They find good agreement with their theoretical results. The second, more realistic example is a corrosion model. The authors show that the conditions of their theorems are satisfied. They calculate approximations of the distribution and the mean exit time and compare them to Monte-Carlo estimates of these quantities. Again a good agreement with the theory is found.

Reviewer: Martin Riedler (Linz)

##### MSC:

60J22 | Computational methods in Markov chains |

60J25 | Continuous-time Markov processes on general state spaces |

60J75 | Jump processes (MSC2010) |

60K10 | Applications of renewal theory (reliability, demand theory, etc.) |

65C20 | Probabilistic models, generic numerical methods in probability and statistics |

PDF
BibTeX
XML
Cite

\textit{A. Brandejsky} et al., Adv. Appl. Probab. 44, No. 1, 196--225 (2012; Zbl 1244.60073)

**OpenURL**

##### References:

[1] | Bally, V. and Pagès, G. (2003). A quantization algorithm for solving multi-dimensional discrete-time optimal stopping problems. Bernoulli 9 , 1003-1049. · Zbl 1042.60021 |

[2] | Bally, V., Pagès, G. and Printemps, J. (2005). A quantization tree method for pricing and hedging multidimensional American options. Math. Finance 15 , 119-168. · Zbl 1127.91023 |

[3] | Bouton, C. and Pagès, G. (1997). About the multidimensional competitive learning vector quantization algorithm with constant gain. Ann. Appl. Prob. 7 , 679-710. · Zbl 0892.60082 |

[4] | Chiquet, J. and Limnios, N. (2008). A method to compute the transition function of a piecewise deterministic Markov process with application to reliability. {Statist. Prob.} · Zbl 1190.60065 |

[5] | Davis, M. H. A. (1993). Markov Models and Optimization (Monogr. Statist. Appl. Prob. 49 ). Chapman & Hall, London. · Zbl 0780.60002 |

[6] | De Saporta, B., Dufour, F. and Gonzalez, K. (2010). Numerical method for optimal stopping of piecewise deterministic Markov processes. Ann. Appl. Prob. 20 , 1607-1637. · Zbl 1197.93162 |

[7] | Gray, R. M. and Neuhoff, D. L. (1998). Quantization. IEEE Trans. Inf. Theory 44 , 2325-2383. · Zbl 1016.94016 |

[8] | Helmes, K., Röhl, S. and Stockbridge, R. H. (2001). Computing moments of the exit time distribution for Markov processes by linear programming. Operat. Res. 49 , 516-530. · Zbl 1163.60321 |

[9] | Lasserre, J.-B. and Prieto-Rumeau, T. (2004). SDP vs. LP relaxations for the moment approach in some performance evaluation problems. Stoch. Models 20 , 439-456. · Zbl 1067.60059 |

[10] | Pagès, G., Pham, H. and Printemps, J. (2004). Optimal quantization methods and applications to numerical problems in finance. In Handbook of Computational and Numerical Methods in Finance , Birkhäuser, Boston, MA, pp. 253-297. · Zbl 1138.91467 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.