Probability: An Introduction with Statistical Applications, 2nd Edition

Chapter 6Recursions and Markov Chains

6.1 Introduction

In this chapter, we study two important parts of the theory of probability: recursions and Markov chains.

It happens that many interesting probability problems can be posed in a recursive manner; indeed, it is often most natural to consider some problems in this way. While we have seen several recursive functions in our previous work, we have not established their solution. Some of our examples will be recalled here and we will show the solution of some recursions. We will also show some new problems and solve them using recursive functions. In particular, we will devote some time to a class of probability problems known as waiting time problems.

Finally, we consider some of the theory of Markov chains, which arise in a number of practical situations. This theory is quite extensive, so we are able to give only a brief introduction in this book.

6.2 Some Recursions and their Solutions

We return now to problems involving recursions, considerably expanding our work in this area and considering more complex problems than we have previously.

Consider again the simple problem of counting the number of permutations of distinct objects, letting denote the number of permutations of these distinct objects. is, of course, a function ...