# Chapter 2Stochastic Recursive Sequences

The modeling of discrete-time deterministic dynamical systems is based on recursive sequences of the form *u*_{n}_{+1} = *f* (*u*_{n}). 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 W_{n+1} of the server at the arrival of the *n*+1th customer is deduced from the workload at the arrival of the *n*th customer by Lindley's equation

[2.1]

If the two sequences are independent (GI/GI/1 queue), then the sequence (*W*_{n}, *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 (*W*_{n}, *n* ∈ N) toward the same limit, but we can expect a convergence “in distribution” that is **P**(*W*_{n} ∈ [*a, b*]) (*W*_{∞} ∈ [*a*, *b*]) for a random variable *W*_{∞} whose distribution must be determined. We then say that the ...