Stochastic Interpretation for the Arimoto Algorithm

Abstract

The Arimoto algorithm computes the Gallager function ${\max }_Q{E}_0^{}(\rho ,Q)$ for a given channel $P_{}^{}(y|x)$ and parameter $\rho$, by means of alternating maximization. Along the way, it generates a sequence of input distributions $Q_1^{}(x)$, $Q_2^{}(x)$, ... , that converges to the maximizing input $Q_{}^{\ast }(x)$. We propose a stochastic interpretation for the Arimoto algorithm. We show that for a random (i.i.d.) codebook with a distribution $Q_k^{}(x)$, the next distribution $Q_{k+1}^{}(x)$ in the Arimoto algorithm is equal to the type ($Q^{\prime }$) of the feasible transmitted codeword that maximizes the conditional Gallager exponent (conditioned on a specific transmitted codeword type $Q^{\prime }$). This interpretation is a first step toward finding a stochastic mechanism for on-line channel input adaptation.

5 pages, 1 figure, accepted for 2015 IEEE Information Theory Workshop, Jerusalem, Israel