Chapter 2Stochastic Recursive Sequences




The modeling of discrete-time deterministic dynamical systems is based on recursive sequences of the form un+1 = f (un). One addresses the question of convergence of the sequence as n goes to infinity, and the value of the limit which, assuming that f is continuous, is necessarily the solution of the equation l = f (l).

The purpose of this chapter is to develop the tools that will enable us to answer such questions for stochastic recursive sequences.

For example, let us consider a G/G/1 queue (which will be dealt with in section 4.1). Denoting (ξn, n ∈ N) the sequence of inter-arrival times and (σn, n ∈ N) the sequence of service times, the workload Wn+1 of the server at the arrival of the n+1th customer is deduced from the workload at the arrival of the nth customer by Lindley's equation

[2.1] images

If the two sequences are independent (GI/GI/1 queue), then the sequence (Wn, n ∈ N) is a Markov chain with values in the uncountable space R+. Its analysis is impossible with the tools of Chapter 3 since we restrict it to Markov chains having finite or countable state space.

Obviously, there can be no almost sure convergence of the sequence (Wn, n ∈ N) toward the same limit, but we can expect a convergence “in distribution” that is P(Wn ∈ [a, b]) (W ∈ [a, b]) for a random variable W whose distribution must be determined. We then say that the ...

Get Stochastic Modeling and Analysis of Telecoms Networks now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.