Optimal Control of Random Walks, Birth and Death Processes and Queues.
Abstract
We first consider a random walk on the nonnegative integers whose steps are controlled as follows. Upon arriving at a location i, a pair of probabilities (p,q) is selected from a given set, a reward r(i,p,q) is received, and the next step takes the walk to locations i+1, i-1 or i, with respective probabilities p, q and l-p-q (q=0 when i=0). This is repeated indefinitely. A rule for successively selecting the probabilities (p,q) is a control policy. We identify conditions on the rewards and probabilities under which there exist monotone optimal policies, for discounted and average rewards, and we show how to compute some of these policies. For example, in certain settings it is optimal to increase the tendency of backward movement of the walk as its location increases. We also present similar results for controlling the parameters of a birth and death process and an M/M/1 queue. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1978
- Accession Number
- ADA060682
Entities
People
- Richard F. Serfozo
Organizations
- Syracuse University