A FIRST COURSE IN STOCHASTIC MODELS
CONTENTS THE POISSON PROCESS AND RELATED PROCESSES 1 0 INTRODUCTION 1 1 THE POISSON PROCESS 1 1 1 THE MEMORYLESS PROPERTY 1 1 2 MERGING AND SPLITTING OF POISSON PROCESSES 1 1 3 THE M/G/?QUEUE 1 1 4 THE POISSON PROCESS AND THE UNIFORM DISTRIBUTION 1 2 COMPOUND POISSON PROCESSES 1 3 NON-STATIONARY POISSON PROCESSES 1 4 MARKOV MODULATED BATCH POISSON PROCESSES EXERCISES BIBLIOGRAPHIC NOTES REFERENCES 2 RENEWAL-REWARD PROCESSES 2 0 INTRODUCTION 2 1 RENEWAL THEORY 2 1 1 THE RENEWAL FUNCTION 2 1 2 THE EXCESS VARIABLE 2 2 RENEWAL-REWARD PROCESSES 2 3 THE FORMULA OF LITTLE 2 4 POISSON ARRIVALS SEE TIME AVERAGES 2 5 THE POLLACZEK–KHINTCHINE FORMULA 2 6 A CONTROLLED QUEUE WITH REMOVABLE SERVER 2 7 AN UP- AND DOWNCROSSING TECHNIQUE 3 DISCRETE-TIME MARKOV CHAINS 3 0 INTRODUCTION 3 1 THE MODEL 3 2 TRANSIENT ANALYSIS 3 2 1 ABSORBING STATES 3 2 2 MEAN FIRST-PASSAGE TIMES 3 2 3 TRANSIENT AND RECURRENT STATES 3 3 THE EQUILIBRIUM PROBABILITIES 3 3 1 PRELIMINARIES 3 3 2 THE EQUILIBRIUM EQUATIONS 3 3 3 THE LONG-RUN AVERAGE REWARD PER TIME UNIT 3 4 COMPUTATION OF THE EQUILIBRIUM PROBABILITIES 3 4 1 METHODS FOR A FINITE-STATE MARKOV CHAIN 3 4 2 GEOMETRIC TAIL APPROACH FOR AN IN?NITE STATE SPACE 3 4 3 METROPOLIS—HASTINGS ALGORITHM 3 5 THEORETICAL CONSIDERATIONS 3 5 1 STATE CLASSI?CATION 3 5 2 ERGODIC THEOREMS 4 CONTINUOUS-TIME MARKOV CHAINS 4 0 INTRODUCTION 4 1 THE MODEL 4 2 THE FLOW RATE EQUATION METHOD 4 3 ERGODIC THEOREMS 4 4 MARKOV PROCESSES ON A SEMI-IN?NITE STRIP 4 5 TRANSIENT STATE PROBABILITIES 4 5 1 THE METHOD OF LINEAR DIFFERENTIAL EQUATIONS 4 5 2 THE UNIFORMIZATION METHOD 4 5 3 FIRST PASSAGE TIME PROBABILITIES 4 6 TRANSIENT DISTRIBUTION OF CUMULATIVE REWARDS 4 6 1 TRANSIENT DISTRIBUTION OF CUMULATIVE SOJOURN TIMES 4 6 2 TRANSIENT REWARD DISTRIBUTION FOR THE GENERAL CASE 5 MARKOV CHAINS AND QUEUES 5 0 INTRODUCTION 5 1 THE ERLANG DELAY MODEL 5 1 1 THE M/M/1 QUEUE 5 1 2 THE M/M/C QUEUE 5 1 3 THE OUTPUT PROCESS AND TIME REVERSIBILITY 5 2 LOSS MODELS 5 2 1 THE ERLANG LOSS MODEL 5 2 2 THE ENGSET MODEL 5 3 SERVICE-SYSTEM DESIGN 5 4 INSENSITIVITY 5 4 1 A CLOSED TWO-NODE NETWORK WITH BLOCKING 5 4 2 THE M/G/1 QUEUE WITH PROCESSOR SHARING 5 5 A PHASE METHOD 5 6 QUEUEING NETWORKS 5 6 1 OPEN NETWORK MODEL 5 6 2 CLOSED NETWORK MODEL 6 DISCRETE-TIME MARKOV DECISION PROCESSES 6 0 INTRODUCTION 6 1 THE MODEL 6 2 THE POLICY-IMPROVEMENT IDEA 6 3 THE RELATIVE VALUE FUNCTION 6 4 POLICY-ITERATION ALGORITHM 6 5 LINEAR PROGRAMMING APPROACH 6 6 VALUE-ITERATION ALGORITHM 6 7 CONVERGENCE PROOFS 7 SEMI-MARKOV DECISION PROCESSES 7 0 INTRODUCTION 7 1 THE SEMI-MARKOV DECISION MODEL 7 2 ALGORITHMS FOR AN OPTIMAL POLICY 7 3 VALUE ITERATION AND FICTITIOUS DECISIONS 7 4 OPTIMIZATION OF QUEUES 7 5 ONE-STEP POLICY IMPROVEMENT 8 ADVANCED RENEWAL THEORY 8 0 INTRODUCTION 8 1 THE RENEWAL FUNCTION 8 1 1 THE RENEWAL EQUATION 8 1 2 COMPUTATION OF THE RENEWAL FUNCTION 8 2 ASYMPTOTIC EXPANSIONS 8 3 ALTERNATING RENEWAL PROCESSES 8 4 RUIN PROBABILITIES 9 ALGORITHMIC ANALYSIS OF QUEUEING MODELS 9 0 INTRODUCTION 9 1 BASIC CONCEPTS 9 2 THE M/G/1 QUEUE 9 2 1 THE STATE PROBABILITIES 9 2 2 THE WAITING-TIME PROBABILITIES 9 2 3 BUSY PERIOD ANALYSIS 9 2 4 WORK IN SYSTEM 9 3 THE MX/G/1 QUEUE 9 3 1 THE STATE PROBABILITIES 9 3 2 THE WAITING-TIME PROBABILITIES 9 4 M/G/1 QUEUES WITH BOUNDED WAITING TIMES 9 4 1 THE FINITE-BUFFER M/G/1 QUEUE 9 4 2 AN M/G/1 QUEUE WITH IMPATIENT CUSTOMERS 9 5 THE GI /G/1 QUEUE 9 5 1 GENERALIZED ERLANGIAN SERVICES 9 5 2 COXIAN-2 SERVICES 9 5 3 THE GI /PH/1 QUEUE 9 5 4 THE PH/G/1 QUEUE 9 5 5 TWO-MOMENT APPROXIMATIONS 9 6 MULTI-SERVER QUEUES WITH POISSON INPUT 9 6 1 THE M/D/C QUEUE 9 6 2 THE M/G/C QUEUE 9 6 3 THE MX/G/C QUEUE 9 7 THE GI /G/C QUEUE 9 7 1 THE GI /M/C QUEUE 9 7 2 THE GI /D/C QUEUE 9 8 FINITE-CAPACITY QUEUES 9 8 1 THE M/G/C/C + N QUEUE 9 8 2 A BASIC RELATION FOR THE REJECTION PROBABILITY 9 8 3 THE MX/G/C/C + N QUEUE WITH BATCH ARRIVALS 9 8 4 DISCRETE-TIME QUEUEING SYSTEMS CHAPTER THE POISSON PROCESS THERE ARE SEVERAL EQUIVALENT DE?NITIONS OF THE POISSON PROCESS OUR STARTING POINT IS A SEQUENCE X1, X2, OF POSITIVE, INDEPENDENT RANDOM VARIABLES WITH A COMMON PROBABILITY DISTRIBUTION THINK OF XN AS THE TIME ELAPSED BETWEEN THE (N?1)TH AND NTH OCCURRENCE OF SOME SPECI?C EVENT IN A PROBABILISTIC SITUATION LET S0 =