large numbers.

Various non-asymptotic alternatives to typicality have been proposed, e.g. one-shot packing and covering lemmas [@verdu2012nonasymp; @liu2015oneshotmutual], stochastic likelihood coder [@yassaee2013oneshot], likelihood encoder [@song2016likelihood] and random binning [@yassaee2013binning]. However, these non-asymptotic approaches generally require more complex proofs than their asymptotic counterparts, whereas proofs using the Poisson matching lemma can be even simpler than asymptotic proofs.

Our approach is better than the conventional asymptotic approach using typicality (and previous one-shot results, e.g. [@verdu2012nonasymp; @yassaee2013oneshot]), in the following ways:

1.  We can give one-shot bounds stronger than the best known one-shot bounds in many settings discussed in this paper, with the exception of channel coding, multiple access channels, channel resolvability and wiretap channels, which are included for demonstration purposes, where we recover bounds comparable to the best known bounds.

2.  Our proofs work for random variables in general Polish spaces.

3.  To the best of our knowledge, for the achievability in the Gelfand-Pinsker theorem [@gelfand1980coding] (for channels with state information at the encoder) and the Wyner-Ziv theorem [@wyner1976ratedistort; @wyner1978rate] (for lossy source coding with side information at the decoder), our proofs are significantly shorter than all previous proofs (another short proof of the achievability in the Gelfand-Pinsker theorem is given in 