We characterize the exact redundancy of lossy source coding under average and almost-sure distortion constraints. For general source and output alphabets, we establish the asymptotic redundancy coefficients under suitable regularity conditions. Under the average distortion constraint, the coefficient is half of the minimum probability that an output reveals information about the source, among all rate-distortion optimal channels. Under the almost-sure distortion constraint, the coefficient is either $1/2$ or $1$, depending on whether the $D$-tilted information is constant or not. Both converse results follow from a common change-of-measure inequality. Finally, we verify the required conditions under both distortion requirements always hold for finite alphabets.
Histogram estimation is a fundamental primitive in distributed data analysis, with applications in counting queries and federated learning. In many settings, the universe of categories is enormous, yet each user's data involves only a small subset, yielding sparse local histograms. This raises a natural question: To what extent can local sparsity reduce the communication needed to estimate the global histogram? We answer this question by characterizing the communication complexity of distributed sparse histogram estimation under prescribed $\ell_1$ distortion and failure probability constraints. Our upper bound is achieved by a randomized covering scheme that optimizes how accurately each user represents its local histogram to reduce communication. By exploiting the distortion budget directly rather than imposing unbiasedness, the scheme achieves lower communication costs than standard unbiased sampling and hashing constructions. We establish the scheme's first-order optimality through a lower bound based on local support identification. The key step is to relate communication cost directly to the number of active coordinates revealed by each user's message, rather than to bound information about the aggregate via distance-based Fano's inequalities. This characterization further quantifies how the communication advantage of heterogeneous over homogeneous encoders varies across parameter regimes.