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.

Mots clés

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