A Discrete-Time Homing Problem with Two Optimizers

Abstract

A stochastic difference game is considered in which a player wants to minimize the time spent by a controlled one-dimensional symmetric random walk {Xn,n=0,1,…} in the continuation region C:={1,2,…}, and the second player seeks to maximize the survival time in C. The process starts at X0=x>0 and the game ends the first time Xn≤0. An exact expression is derived for the value function, from which the optimal solution is obtained, and particular problems are solved explicitly.

Keywords

• random walk
• first-passage time
• homing problem
• difference game
• dynamic programming
• difference equation