Sharp Inequalities for $f$-divergences

Suppose that the Kullback-Leibler divergence between two probability measures is bounded from above by 2. What then is the maximum possible value of the Hellinger distance between them? Such questions naturally arise in many fields including mathematical statistics and machine learning, information theory, probability, statistical physics etc. and the goal of this paper is to provide a way of answering them. From the variational viewpoint, this problem can be posed as: maximize the Hellinger distance subject to a constraint on the Kullback-Leibler divergence over the space of all pairs of probability measures over all possible sample spaces. We shall prove in this paper that the value of this maximization problem remains unchanged if one restricts the sample space to be the three-element set{ 1, 2, 3} . In other words, in order to find the maximum Hellinger distance subject to an upper bound on the Kullback-Leibler divergence, one can just restrict attention to pairs of probability measures on {1, 2, 3}. Thus, the large infinite-dimensional optimization problem is reduced to an optimization problem over a small finite-dimensional space (of dimension 4) which makes it tractable.