For variable-length coding with an almost-sure distortion constraint, Zhang et al. show that for discrete sources the redundancy is upper bounded by $\log n/n$ and lower bounded (in most cases) by $\log n/(2n)$, ignoring lower order terms. For a uniform source with a distortion measure satisfying certain symmetry conditions, we show that $\log n/(2n)$ is achievable and that this cannot be improved even if one relaxes the distortion constraint to be in expectation rather than with probability one.

We consider the redundancy of the exact channel synthesis problem under an i.i.d. assumption. Existing results provide an upper bound on the unnormalized redundancy that is logarithmic in the block length. We show, via an improved scheme, that the logarithmic term can be halved for most channels and eliminated for all others. For full-support discrete memory less channels, we show that this is the best possible.

We consider the design of practically-implementable schemes for the task of channel simulation. Existing methods do not scale with the number of simultaneous uses of the channel and are therefore unable to harness the amortization gains associated with simulating many uses of the channel at once. We show how techniques from the theory of error-correcting codes can be applied to achieve scalability and hence improved performance. As an exemplar, we focus on how polar codes can be used to efficiently simulate i.i.d. copies of a class of binary-output channels.