Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-27T08:53:29.307Z Has data issue: false hasContentIssue false
  • English
  • Français

Monotone Stochastic Recursions and their Duals

Published online by Cambridge University Press:  27 July 2009

Søren Asmussen  and
Karl Sigman
Søren Asmussen
Affiliation:
Department of Mathematical Statistics, University of Lund, Box 118S-221 00 Lund, Sweden
Karl Sigman
Affiliation:
Department of Industrial Engineering and Operations Research, Columbia University, 500 West 120th Street, New York, New York 10027–6699, USA
Get access Rights & Permissions [Opens in a new window]

Abstract

A duality is presented for real-valued stochastic sequences [Vn] defined by a general recursion of the form Vn+1 = f(Vn, Un), with [Un] a stationary driving sequence and f nonnegative, continuous, and monotone in its first variable. The duality is obtained by defining a dual function g of f, which if used recursively on the time reversal of [Un] defines a dual risk process. As a consequence, we prove that steady-state probabilities for Vn can always be expressed as transient probabilities of the dual risk process. The construction is related to duality of stochastically monotone Markov processes as studied by Siegmund (1976, The equivalence of absorbing and reflecting barrier problems for stochastically monotone Markov processes, Annals of Probability 4: 914–924). Our method of proof involves an elementary sample-path analysis. A variety of examples are given, including random walks with stationary increments and two reflecting barriers, reservoir models, autoregressive processes, and branching processes. Finally, general stability issues of the content process are dealt with by expressing them in terms of the dual risk process.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 10 , Issue 1 , January 1996 , pp. 1 - 20
Copyright
Copyright © Cambridge University Press 1996

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Anick, D., Mitra, D. & Sondhi, M.M. (1982). Stochastic theory of a data-handling system with multiple sources. Bell System Technical Journal 61: 1871–1894.CrossRefGoogle Scholar
2.Asmussen, S. (1993/1994). Siegmund duality and Markov-dependence, with applications to finite buffer problems and rare events simulation. Working Paper, Aalborg University.Google Scholar
3.Asmussen, S. (1995). Stationary distributions for fluid flow models with or without Brownian noise. Stochastic Models 11: 21–49.CrossRefGoogle Scholar
4.Asmussen, S. & Hering, H. (1983). Branching processes. Basel: Birkhäuser.CrossRefGoogle Scholar
5.Asmussen, S. & Kella, O. (1995). Rate modulation in dams and ruin problems. Journal of Applied Probability 32 (to appear).Google Scholar
6.Asmussen, S. & Rubinstein, R. (1995). Complexity properties of steady-state rare events simulation in queueing models. In Dhashalow, J. (ed.), Frontiers in queueing. Boca Raton, FL: CRC Press, pp. 429–462.Google Scholar
7.Asmussen, S. & Schock Petersen, S. (1989). Ruin probabilities expressed in terms of storage processes. Advances in Applied Probability 20: 913–916.CrossRefGoogle Scholar
8.Baccelli, F. & Brémaud, P. (1994). Elements of queueing theory: Palm-Martingale calculus and stochastic recurrences. New York: Springer-Verlag.Google Scholar
9.Borovkov, A.A. (1984). Asymptotic methods in queueing theory. New York: Wiley.Google Scholar
10.Borovkov, A.A. & Foss, S.G. (1992). Stochastically recursive sequences and their generalizations. Sib. Advances in Mathematics 2: 16–81.Google Scholar
11.Borovkov, A.A. & Foss, S.G. (1994). Two ergodicity criteria for stochastically recursive sequences. Acta Applicandae Mathematicae 34: 125–134.CrossRefGoogle Scholar
12.Brandt, A., Franken, P. & Lisek, B. (1992). Stationary stochastic models. New York: Wiley.Google Scholar
13.Clifford, P. & Sudbury, A. (1985). A sample path proof of the duality for stochastically monotone Markov processes. Annals of Probability 13: 558–565.CrossRefGoogle Scholar
14.Daley, D.J. (1968). Stochastically monotone Markov chains. Zeitschrift für Wahrscheinlichkeitstheorie und Verwunde Cebiete 10: 305–317.CrossRefGoogle Scholar
15.Harrison, J.M. & Resnick, S.I. (1977). The recurrence classification of risk and storage processes. Mathematics of Operations Research 3: 57–66.CrossRefGoogle Scholar
16.Liggett, T.M. (1985). Interacting particle system. New York: Springer-Verlag.CrossRefGoogle Scholar
17.Lindley, D. (1952). The theory of queues with a single server. Proceedings of the Cambridge Philosophical Society 48: 277–289.CrossRefGoogle Scholar
18.Lindley, D. (1959). Discussion of a paper of C.B. Winsten. Journal of the Royal Statistical Society, Series B 21: 22–23.Google Scholar
19.Loynes, R. (1962). The stability of a queue with non-independent inter-arrival and service times. Proceedings of the Cambridge Philosophical Society 58: 497–520.CrossRefGoogle Scholar
20.Neuts, M.F. (1981). Matrix-geometric solutions in stochastic models. Baltimore and London: Johns Hopkins University Press.Google Scholar
21.Neuts, M.F. (1989). Structured stochastic matrices of the M/G/l type and their applications.New York: Marcel Dekker.Google Scholar
22.Prabhu, N.U. (1961). On the ruin problem of collective risk theory. Annals of Mathematical Statistics 32: 757–764.CrossRefGoogle Scholar
23.Rogers, C.L.G. (1994). Fluid models in queueing theory and Wiener-Hopf factorisation of Markov chains. Annals of Applied Probability 4: 390–413.CrossRefGoogle Scholar
24.Rolski, T. (1981). Stationary random processes associated with point processes. New York: Springer-Verlag.CrossRefGoogle Scholar
25.Seal, H.L. (1972). Risk theory and the single server queue. Mitt. Verein Schweiz. Versich. Math. 72: 171–178.Google Scholar
26.Siegmund, D. (1976). The equivalence of absorbing and reflecting barrier problems for stochastically monotone Markov processes. Annals of Probability 4: 914–924.CrossRefGoogle Scholar
27.Sigman, K. (1995). Stationary marked point processes: An intuitive approach. New York: Chapman and Hall.Google Scholar
28.Stadje, W. (1993). A new look at the Moran dam. Journal of Applied Probability 30: 489–495.CrossRefGoogle Scholar