Accession Number:

ADA043521

Title:

Optimal Control of Random Walks.

Descriptive Note:

Interim rept.,

Corporate Author:

SYRACUSE UNIV N Y DEPT OF INDUSTRIAL ENGINEERING AND OPERATIONS RESEARCH

Personal Author(s):

Report Date:

1977-01-01

Pagination or Media Count:

38.0

Abstract:

This is a study of 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 prescribed set, a reward ri,p,q is received and the next step takes the walk to locations i1, i-1, or i, with respective probabilities p, q and 1-p-q when i0 these probabilities are p, 0 and 1-p. This is repeated indefinitely. A rule for successively selecting the probabilities p,q is a control policy. Conditions are identified on the rewards and probabilities under which there exist monotonic optimal policies for discounted and average rewards. For example, in one case it is optimal to increase the probability of backward steps as the location i increases. Our results are based on 1 a criterion for monotone optimal policies, 2 a result describing when an upper envelope of concave functions is concave, and 3 a relation between optimal Policies for the discounted and average reward criteria. Procedures for computing optimal policies are also presented. Author

Subject Categories:

  • Statistics and Probability
  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE