  Inspired by the ideas from the field of stochastic approximation, we propose
a randomized algorithm to compute the capacity of a finite-state channel with a
Markovian input. When the mutual information rate of the channel is concave
with respect to the chosen parameterization, we show that the proposed
algorithm will almost surely converge to the capacity of the channel and derive
the rate of convergence. We also discuss the convergence behavior of the
algorithm without the concavity assumption.
