Efficient computation of Wiener-Hopf factorization of Markov-modulated Brownian motion
HTML articles powered by AMS MathViewer
- by Changli Liu and Jungong Xue;
- Math. Comp. 94 (2025), 2367-2408
- DOI: https://doi.org/10.1090/mcom/4055
- Published electronically: January 23, 2025
- PDF | Request permission
Abstract:
The Wiener-Hopf factorization, which is characterized as special solutions to a pair of nonlinear matrix equations, plays a crucial role in analysis of the Markov-modulated Brownian motion (mmbm). This paper deals with the general case where the diffusion coefficients are nonzero for some but not all states of the governing Markov chain. Based on a novel regrouping of the unknowns in the Wiener-Hopf factorization and a new form for the initialization phase, a doubling algorithm is proposed to solve the pair of nonlinear matrix equations simultaneously. With the parameters of the mmbm as input, this doubling algorithm is implemented in a subtraction-free manner to compute the Wiener-Hopf factorization to high entrywise relative accuracy. Numerical examples are presented to demonstrate and confirm our claims.References
- Soohan Ahn, Alternative fluid approximation approach for the steady-state distribution of the two-sided reflected Markov modulated Brownian motion and its computation, J. Korean Statist. Soc. 44 (2015), no. 3, 448–456. MR 3374593, DOI 10.1016/j.jkss.2014.12.005
- Soohan Ahn and V. Ramaswami, A quadratically convergent algorithm for first passage time distributions in the Markov-modulated Brownian motion, Stoch. Models 33 (2017), no. 1, 59–96. MR 3606616, DOI 10.1080/15326349.2016.1211018
- Attahiru Sule Alfa, Jungong Xue, and Qiang Ye, Accurate computation of the smallest eigenvalue of a diagonally dominant $M$-matrix, Math. Comp. 71 (2002), no. 237, 217–236. MR 1862996, DOI 10.1090/S0025-5718-01-01325-4
- Søren Asmussen, Stationary distributions for fluid flow models with or without Brownian noise, Comm. Statist. Stochastic Models 11 (1995), no. 1, 21–49. MR 1316767, DOI 10.1080/15326349508807330
- Zhong-Zhi Bai, Xiao-Xia Guo, and Jun-Feng Yin, On two iteration methods for the quadratic matrix equations, Int. J. Numer. Anal. Model. 2 (2005), no. suppl., 114–122. MR 2266942
- Abraham Berman and Robert J. Plemmons, Nonnegative matrices in the mathematical sciences, Computer Science and Applied Mathematics, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1979. MR 544666
- D. A. Bini, G. Latouche, and B. Meini, Numerical methods for structured Markov chains, Numerical Mathematics and Scientific Computation, Oxford University Press, New York, 2005. Oxford Science Publications. MR 2132031, DOI 10.1093/acprof:oso/9780198527688.001.0001
- Dario A. Bini, Beatrice Meini, and Federico Poloni, Transforming algebraic Riccati equations into unilateral quadratic matrix equations, Numer. Math. 116 (2010), no. 4, 553–578. MR 2721634, DOI 10.1007/s00211-010-0319-2
- Lothar Breuer, First passage times for Markov additive processes with positive jumps of phase type, J. Appl. Probab. 45 (2008), no. 3, 779–799. MR 2455184, DOI 10.1239/jap/1222441829
- B. D’Auria, J. Ivanovs, O. Kella, and M. Mandjes, Two-sided reflection of Markov-modulated Brownian motion, Stoch. Models 28 (2012), no. 2, 316–332. MR 2926589, DOI 10.1080/15326349.2012.672285
- Chun-Hua Guo, Nonsymmetric algebraic Riccati equations and Wiener-Hopf factorization for $M$-matrices, SIAM J. Matrix Anal. Appl. 23 (2001), no. 1, 225–242. MR 1856607, DOI 10.1137/S0895479800375680
- Chun-Hua Guo, On a quadratic matrix equation associated with an $M$-matrix, IMA J. Numer. Anal. 23 (2003), no. 1, 11–27. MR 1953980, DOI 10.1093/imanum/23.1.11
- Chun-Hua Guo, A new class of nonsymmetric algebraic Riccati equations, Linear Algebra Appl. 426 (2007), no. 2-3, 636–649. MR 2350683, DOI 10.1016/j.laa.2007.05.044
- Chun-Hua Guo and Nicholas J. Higham, Iterative solution of a nonsymmetric algebraic Riccati equation, SIAM J. Matrix Anal. Appl. 29 (2007), no. 2, 396–412. MR 2318355, DOI 10.1137/050647669
- Xin Guo, Information and option pricings, Quant. Finance 1 (2001), no. 1, 38–44. MR 1810015, DOI 10.1088/1469-7688/1/1/302
- Xiao-Xia Guo, Wen-Wei Lin, and Shu-Fang Xu, A structure-preserving doubling algorithm for nonsymmetric algebraic Riccati equation, Numer. Math. 103 (2006), no. 3, 393–412. MR 2221055, DOI 10.1007/s00211-005-0673-7
- M. A. Hernández-Verón and N. Romero, An efficient predictor-corrector iterative scheme for solving Wiener-Hopf problems, J. Comput. Appl. Math. 404 (2022), Paper No. 113554, 11. MR 4349321, DOI 10.1016/j.cam.2021.113554
- M. A. Hernández-Verón and N. Romero, Solving Wiener-Hopf problems via an efficient iterative scheme, J. Comput. Appl. Math. 405 (2022), Paper No. 113083, 8. MR 4357345, DOI 10.1016/j.cam.2020.113083
- Tsung-Ming Huang, Ren-Cang Li, and Wen-Wei Lin, Structure-preserving doubling algorithms for nonlinear matrix equations, Fundamentals of Algorithms, vol. 14, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2018. MR 3909433, DOI 10.1137/1.9781611975369.ch1
- Jevgenijs Ivanovs, Markov-modulated Brownian motion with two reflecting barriers, J. Appl. Probab. 47 (2010), no. 4, 1034–1047. MR 2752892, DOI 10.1239/jap/1294170517
- Zhengjun Jiang and Martijn R. Pistorius, On perpetual American put valuation and first-passage in a regime-switching model with jumps, Finance Stoch. 12 (2008), no. 3, 331–355. MR 2410841, DOI 10.1007/s00780-008-0065-9
- A. Jobert and L. C. G. Rogers, Option pricing with Markov-modulated dynamics, SIAM J. Control Optim. 44 (2006), no. 6, 2063–2078. MR 2248175, DOI 10.1137/050623279
- R. L. Karandikar and V. G. Kulkarni, Second-order fluid flow models: reflected Brownian motion in a random environment, Oper. Res. 43(1995), 77–88.
- Joanne Kennedy and David Williams, Probabilistic factorization of a quadratic matrix polynomial, Math. Proc. Cambridge Philos. Soc. 107 (1990), no. 3, 591–600. MR 1041488, DOI 10.1017/S0305004100068845
- C. Liu and J. Xue, Accurately and simultaneously computing M-matrix solutions to $X^2-EX-F = 0$ and $X^2+EX-F = 0$, Technical report, 2023.
- Changli Liu, Jungong Xue, and Ren-Cang Li, Accurate numerical solution for shifted $M$-matrix algebraic Riccati equations, J. Sci. Comput. 84 (2020), no. 1, Paper No. 15, 27. MR 4121186, DOI 10.1007/s10915-020-01263-4
- R. R. London, H. P. McKean, L. C. G. Rogers, and David Williams, A martingale approach to some Wiener-Hopf problems. I, II, Seminar on Probability, XVI, Lecture Notes in Math., vol. 920, Springer, Berlin-New York, 1982, pp. 41–67, 68–90. MR 658671
- Linzhang Lu, Zubair Ahmed, and Jinrui Guan, Numerical methods for a quadratic matrix equation with a nonsingular M-matrix, Appl. Math. Lett. 52 (2016), 46–52. MR 3416385, DOI 10.1016/j.aml.2015.08.006
- Giang T. Nguyen and Federico Poloni, Componentwise accurate fluid queue computations using doubling algorithms, Numer. Math. 130 (2015), no. 4, 763–792. MR 3357656, DOI 10.1007/s00211-014-0675-4
- G. T. Nguyen and F. Poloni, Componentwise accurate Brownian motion computations using cyclic reduction, arXiv:1605.01482, 2016.
- Martijn Pistorius, On maxima and ladder processes for a dense class of Lévy process, J. Appl. Probab. 43 (2006), no. 1, 208–220. MR 2225061, DOI 10.1239/jap/1143936254
- Federico Poloni, Algorithms for quadratic matrix and vector equations, Tesi. Scuola Normale Superiore di Pisa (Nuova Series) [Theses of Scuola Normale Superiore di Pisa (New Series)], vol. 16, Edizioni della Normale, Pisa, 2011. Dissertation, Scuola Normale Superiore, Pisa, 2011. MR 2840249, DOI 10.1007/978-88-7642-384-0
- V. Ramaswami, Matrix Analytic Methods for Stochastic Fluid Flows, In Teletraffic Engineering in a Competitive World. (Proc. 16th Internat. Teletraffic Congress), eds D. Smith and P. Key, Elsevier, New York, pp. 1019–1030.
- L. C. G. Rogers, Fluid models in queueing theory and Wiener-Hopf factorization of Markov chains, Ann. Appl. Probab. 4 (1994), no. 2, 390–413. MR 1272732
- L. C. G. Rogers and Z. Shi, Computing the invariant law of a fluid model, J. Appl. Probab. 31 (1994), no. 4, 885–896. MR 1303920, DOI 10.2307/3215314
- Wei-guo Wang, Wei-chao Wang, and Ren-Cang Li, Alternating-directional doubling algorithm for $M$-matrix algebraic Riccati equations, SIAM J. Matrix Anal. Appl. 33 (2012), no. 1, 170–194. MR 2902677, DOI 10.1137/110835463
- Jungong Xue and Ren-Cang Li, Highly accurate doubling algorithms for $M$-matrix algebraic Riccati equations, Numer. Math. 135 (2017), no. 3, 733–767. MR 3606461, DOI 10.1007/s00211-016-0815-0
- Jungong Xue, Shufang Xu, and Ren-Cang Li, Accurate solutions of $M$-matrix Sylvester equations, Numer. Math. 120 (2012), no. 4, 639–670. MR 2892947, DOI 10.1007/s00211-011-0420-1
Bibliographic Information
- Changli Liu
- Affiliation: College of Mathematics, Sichuan University, Chengdu 610065, People’s Republic of China
- Email: chliliu@hotmail.com
- Jungong Xue
- Affiliation: School of Mathematical Sciences, Fudan University, Shanghai 200433, People’s Republic of China
- Email: xuej@fudan.edu.cn
- Received by editor(s): September 19, 2023
- Received by editor(s) in revised form: June 20, 2024, and September 2, 2024
- Published electronically: January 23, 2025
- Additional Notes: The first author was supported in part by Sichuan Province Natural Science Foundation Grant 2023NSFSC0075. The second author was supported in part by the National Science Foundation of China Grant 12171101, the National Key R&D Program of China 2018YFA0703900 and Laboratory of Mathematics for Nonlinear Science, Fudan University.
The second author is the corresponding author - © Copyright 2025 American Mathematical Society
- Journal: Math. Comp. 94 (2025), 2367-2408
- MSC (2020): Primary 15A24, 60J65
- DOI: https://doi.org/10.1090/mcom/4055