LU -Factorization Versus Wiener-Hopf Factorization for Markov Chains
- PDF / 1,259,339 Bytes
- 37 Pages / 439.37 x 666.142 pts Page_size
- 104 Downloads / 205 Views
LU-Factorization Versus Wiener-Hopf Factorization for Markov Chains Vincent Vigon
Received: 21 March 2012 / Accepted: 12 January 2013 / Published online: 14 February 2013 © Springer Science+Business Media Dordrecht 2013
Abstract Our initial motivation was to understand links between Wiener-Hopf factorizations for random walks and LU-factorizations for Markov chains as interpreted by Grassman (Eur. J. Oper. Res. 31(1):132–139, 1987). Actually, the first ones are particular cases of the second ones, up to Fourier transforms. To show this, we produce a new proof of LU-factorizations which is valid for any Markov chain with a denumerable state space equipped with a preorder relation. Factors have nice interpretations in terms of subordinated Markov chains. In particular, the LU-factorization of the potential matrix determines the law of the global minimum of the Markov chain. For any matrix, there are two main LU-factorizations according as you decide to enter 1 in the diagonal of the first or of the second factor. When we factorize the generator of a Markov chain, one factorization is always valid while the other requires some hypothesis on the graph of the transition matrix. This dissymmetry comes from the fact that the class of sub-stochastic matrices is not stable under transposition. We generalize our work to the class of matrices with spectral radius less than one; this allows us to play with transposition and thus with time-reversal. We study some particular cases such as: skip-free Markov chains, random walks (this gives the WH-factorization), reversible Markov chains (this gives the Cholesky factorization). We use the LU-factorization to compute invariant measures. We present some pathologies: non-associativity, non-unicity; these can be cured by smooth assumptions (e.g. irreductibility). Keywords Markov chains · Random walks · LU-factorization · Path-decomposition · Fluctuation theory · Probabilistic potential theory · Infinite matrices Mathematics Subject Classification 60J10 · 60J45 · 47A68 · 15A23
V. Vigon () IRMA, Université de Strasbourg, Strasbourg, France e-mail: [email protected]
2
V. Vigon
1 Introduction The generator of a Markov chain admits a LU-factorization which can be proved and interpreted in terms of probabilities. This was shown by Grassman [11], extended by [12], and Zhao, Li, Braun [33]. In many special cases, this factorization leads to interesting methods to compute invariant measures and more generally to study structured Markov chains as the one appearing in queuing systems cf. Cao, Li, Zhao [17–19]. Recently, a book by Li [16] was completely devoted to this subject. In another part of the mathematical world, the LU-factorization was extensively studied for M-matrices (which includes generators of finite Markov chains); see Fiedler, Ptátk [7], Kuo [14], Funderlic, Plemmons [10], Varga, Cai [24], McDonald, Schneider [22]. But these studies are concentrated on finite matrices while probabilistic methods allow one to work with infinite matrices (e.g. matrices indexed by
Data Loading...
