Title: Stochastic interpretation for the Arimoto algorithm
Abstract: The Arimoto algorithm computes the Gallager function max <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Q</sub> E <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</sub> (ρ, Q) for a given channel P (y | x) and parameter ρ, by means of alternating maximization. Along the way, it generates a sequence of input distributions Q <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> (x), Q <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> (x), ..., that converges to the maximizing input Q*(x). We propose a stochastic interpretation for the Arimoto algorithm. We show that for a random (i.i.d.) codebook with a distribution Q <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sub> (x), the next distribution Q <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k+1</sub> (x) in the Arimoto algorithm is equal to the type (Q') of the feasible transmitted codeword that maximizes the conditional Gallager exponent (conditioned on a specific transmitted codeword type Q'). This interpretation is a first step toward finding a stochastic mechanism for on-line channel input adaptation.