Stochastic Modeling and Analysis of Telecoms Networks

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