Consider a stochastic controllable dynamical system $P$ with action-space $A$ and countable state-space $S$. Thus $P=\left(p_{x y}(a): x, y \in S, a \in A\right)$ and $p_{x y}(a)$ denotes the transition probability from $x$ to $y$ when taking action $a$. Suppose that a cost $c(x, a)$ is incurred each time that action $a$ is taken in state $x$, and that this cost is uniformly bounded. Write down the dynamic optimality equation for the problem of minimizing the expected long-run average cost.

State in terms of this equation a general result, which can be used to identify an optimal control and the minimal long-run average cost.

A particle moves randomly on the integers, taking steps of size 1 . Suppose we can choose at each step a control parameter $u \in[\alpha, 1-\alpha]$, where $\alpha \in(0,1 / 2)$ is fixed, which has the effect that the particle moves in the positive direction with probability $u$ and in the negative direction with probability $1-u$. It is desired to maximize the long-run proportion of time $\pi$ spent by the particle at 0 . Show that there is a solution to the optimality equation for this example in which the relative cost function takes the form $\theta(x)=\mu|x|$, for some constant $\mu$.

Determine an optimal control and show that the maximal long-run proportion of time spent at 0 is given by

$$\pi=\frac{1-2 \alpha}{2(1-\alpha)} .$$

You may assume that it is valid to use an unbounded function $\theta$ in the optimality equation in this example.