A discrete-time homing problem with two optimizers

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

Uncontrolled Keywords

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