Consider the $\epsilon$-smoothed relative max-entropy of $\rho$ with respect to $Q$, defined as (following Watrous' notation from these notes): $$\mathrm D_{\rm max}^{\epsilon}(\rho\|Q) = \min_{\xi\in B_\epsilon(\rho)} \mathrm D_{\rm max}(\xi\|Q),\tag1$$ where $\rho$ is a state, $Q$ a positive semidefinite operator in the same space, and $B_\epsilon(\rho)$ is the ball of states $\epsilon$-close to $\rho$ (e.g. in trace distance).

Similarly, (Tomamichel 2015) defines the "$\epsilon$-smooth max-entropy" as $$ H_{\rm max}^\epsilon(X)_\rho \equiv \min_{\tilde\rho} H_{1/2}(X)_{\tilde\rho}, \tag2$$ where $H_{1/2}(X)$ is the Renyi entropy of order $1/2$, and the minimisation is performed over all states that are $\epsilon$-close to $\rho$ in trace distance. In page 6, they show that $H_{\rm max}^\epsilon(X)$ characterises the single-shot compressibility of a source $X$, in that given an error threshold $\epsilon$, the minimum possible $m\equiv m^*(\epsilon)$ such that there is an $(\epsilon,m)$-code for $X$ is bounded by $$H_{\rm max}^\epsilon(X)_\rho \le \log_2 m_*(\epsilon) \le \inf_{\delta\in(0,\epsilon)}\left[ H_{\rm max}^{\epsilon-\delta}(X)_\rho + \log_2(1/\delta) \right].$$

What I'm trying to understand better is why the operation of "smoothing" probability distributions/states works well to characterise single-shot compressibility/transmission rates/etc.

In the notes linked above, in page 26, Watrous writes that

The idea is that the smoothed max-relative entropy reflects a tolerance for small errors, which we often have or would like to express when analyzing operationally defined notions. Without smoothing, the max-relative entropy can sometimes, in certain settings at least, have unwanted hyper-sensitivities that smoothing eliminates.

This hints towards what I'm trying to get at, I think: min-max entropic quantities seem to not always behave nicely with respect to smooth changes of probability distribution/state, and thus we fix this by "smoothing" them. What are simple examples where this problem is evident, and then fixed via smoothing? Or more generally, is there a more precise or specific argument to see why smooth entropic quantities should be useful (as in, I can see that they are useful, but what specifically causes them to be so useful?)



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.