Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-27T09:44:15.087Z Has data issue: false hasContentIssue false
  • English
  • Français

A matrix-analytic approach to the N-player ruin problem

Part of: Markov processes

Published online by Cambridge University Press:  14 July 2016

Yvik C. Swan  and
F. Thomas Bruss
Yvik C. Swan*
Affiliation:
Université Libre de Bruxelles
F. Thomas Bruss*
Affiliation:
Université Libre de Bruxelles
*
∗Postal address: Département de Mathématique et ISRO, Université Libre de Bruxelles, Campus Plaine, CP 210, B-1050 Brussels, Belgium.
∗Postal address: Département de Mathématique et ISRO, Université Libre de Bruxelles, Campus Plaine, CP 210, B-1050 Brussels, Belgium.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Consider N players, respectively owning x1, x2, …, xN monetary units, who play a sequence of games, winning from and losing to each other integer amounts according to fixed rules. The sequence stops as soon as (at least) one player is ruined. We are interested in the ruin process of these N players, i.e. in the probability that a given player is ruined first, and also in the expected ruin time. This problem is called the N-player ruin problem. In this paper, the problem is set up as a multivariate absorbing Markov chain with an absorbing state corresponding to the ruin of each player. This is then discussed in the context of phase-type distributions where each phase is represented by a vector of size N and the distribution has as many absorbing points as there are ruin events. We use this modified phase-type distribution to obtain an explicit solution to the N-player problem. We define a partition of the set of transient states into different levels, and on it give an extension of the folding algorithm (see Ye and Li (1994)). This provides an efficient computational procedure for calculating some of the key measures.

Keywords

Markov processphase-type distributionhitting timehitting probabilityfolding algorithm

MSC classification

Primary: 60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
Secondary: 60J20: Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
Type
Research Article
Information
Journal of Applied Probability , Volume 43 , Issue 3 , September 2006 , pp. 755 - 766
Copyright
© Applied Probability Trust 2006 

References

Alabert, A., Farré, M. and Roy, R. (2004). Exit times from equilateral triangles. Appl. Math. Optimization 49, 43–53.CrossRefGoogle Scholar
Bruss, F. T., Louchard, G. and Turner, J. W. (2003). On the N-tower-problem and related problems. Adv. Appl. Prob. 35, 278–294.Google Scholar
Engel, A. (1993). The computer solves the three tower problem. Amer. Math. Monthly 100, 62–64.Google Scholar
Ferguson, T. S. (1995). Gambler's Ruin in Three Dimensions. Unpublished manuscript. Available at http://www.math. ucla.edu/∼tom/.Google Scholar
Householder, A. S. (1964). The Theory of Matrices in Numerical Analysis. Blaisdell, New York.Google Scholar
Latouche, G. (1989). Distribution de type phase: tutorial. Cahiers Centre Études Rech. Opér. 31, 3–11.Google Scholar
Latouche, G. and Ramaswami, V. (1999). Introduction to Matrix Analytic Methods in Stochastic Modeling. Society for Industrial and Applied Mathematics, Philadelphia, PA.Google Scholar
Neuts, M. F. (1975). Probability distributions of phase type. In Liber Amicorum Professor Emeritus H. Florin, Department of Mathematics, University of Louvain, pp. 173–206.Google Scholar
Neuts, M. F. (1978). Renewal processes of phase type. Naval. Res. Logistics 25, 445–454.Google Scholar
Neuts, M. F. (1981). Matrix-Geometric Solutions in Stochastic Models. An Algorithmic Approach. The Johns Hopkins University Press, Baltimore, MD.Google Scholar
Stirzaker, D. (1994). Tower problems and martingales. Math. Scientist 19, 52–59.Google Scholar
Swan, Y. and Bruss, F. T. (2004). The Schwarz–Christoffel transformation as a tool in applied probability. Math. Scientist 29, 21–32.Google Scholar
Ye, J. and Li, S. Q. (1994). Folding algorithm: a computational method for finite QBD processes with level dependent transitions. IEEE Trans. Commun. 45, 625–639.Google Scholar