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
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 ...