  This paper addresses the problem of finding a minimum-cost $m$-state Markov
chain $(S_0,\ldots,S_{m-1})$ in a large set of chains. The chains studied have
a reward associated with each state. The cost of a chain is its "gain", i.e.,
its average reward under its stationary distribution.
  Specifically, for each $k=0,\ldots,m-1$ there is a known set ${\mathbb S}_k$
of type-$k$ states. A permissible Markov chain contains exactly one state of
each type; the problem is to find a minimum-cost permissible chain.
  The original motivation was to find a cheapest binary AIFV-$m$ lossless code
on a source alphabet of size $n$. Such a code is an $m$-tuple of trees, in
which each tree can be viewed as a Markov Chain state. This formulation was
then used to address other problems in lossless compression. The known solution
techniques for finding minimum-cost Markov chains were iterative and ran in
exponential time.
  This paper shows how to map every possible type-$k$ state into a type-$k$
hyperplane and then define a "Markov Chain Polytope" as the lower envelope of
all such hyperplanes. Finding a minimum-cost Markov chain can then be shown to
be equivalent to finding a "highest" point on this polytope.
  The local optimization procedures used in the previous iterative algorithms
are shown to be separation oracles for this polytope. Since these were often
polynomial time, an application of the Ellipsoid method immediately leads to
polynomial time algorithms for these problems.
