the Decoder
=================================================================

The one-shot lossy source coding setting with side information at the decoder is described as follows. Upon observing $X\sim P_{X}$, the encoder produces $M\in[1:\mathsf{L}]$. The decoder observes $M$ and $Y\sim P_{Y|X}$ and recovers $\hat{Z}\in\mathcal{Z}$ with probability of excess distortion $P_{e}=\mathbf{P}\{\mathsf{d}(X,\hat{Z})>\mathsf{D}\}$, where $\mathsf{d}:\mathcal{X}\times\mathcal{Z}\to\mathbb{R}_{\ge0}$ is a distortion measure.

We show a one-shot version of the Wyner-Ziv theorem [@wyner1976ratedistort; @wyner1978rate]. Our bound is stronger than those in [@verdu2012nonasymp; @watanabe2015nonasymp], and significantly simpler to state and prove. Unlike previous approaches, our proof does not require binning.

\[thm:lscsi\]Fix any $P_{U|X}$ and function $z:\mathcal{U}\times\mathcal{Y}\to\mathcal{Z}$. There exists a code for lossy source coding with source distribution $P_{X}$, side information at the decoder given by $P_{Y|X}$, and message size $\mathsf{L}$, with probability of excess distortion $$P_{e}\le\mathbf{E}\left[1-\mathbf{1}\{\mathsf{d}(X,Z)\le\mathsf{D}\}(1+\mathsf{L}^{-1}2^{\iota_{U;X}(U;X)-\iota_{U;Y}(U;Y)})^{-1}\right]$$ if $P_{UX}\ll P_{U}\times P_{X}$ and $P_{UY}\ll P_{U}\times P_{Y}$, where $(X,Y,U,Z)\sim P_{X}P_{Y|X}P_{U|X}\delta_{z(U,Y)}$.

Let $\{(\bar{U}_{i},\bar{M}_{i}),T_{i}\}_{i\in\mathbb{N}}$ be the points of a Poisson process with intensity measure $P_{U}\times P_{M}\times\lambda_{\mathbb{R}_{\ge0}}$ independent of $X$, where $P_{M}$ is $\mathrm{Unif}[1:\mathsf{L}]$. The encoding function is $x\mapsto\tilde{M}_{P_{U|X}(\cdot|x)\times P_{M}}$ (i.e., $M=\tilde{M}_{P_{U|X}(\cdot|X)\times P_{M}}$), and the decoding function is $(m,y)\mapsto z(\tilde{U}_{P_{U|Y}(\cdot|y)\times\delta_{m}},y)$ (let $\hat{U}=\tilde{U}_{P_{U|Y}(\cdot|Y)\times\delta_{M}}$, $\hat{Z}=z(\hat{U},Y)$). Also define $U=\tilde{U}_{P_{U|X}(\cdot|X)\times P_{M}}$, $Z=z(U,Y)$. Note that $(M,X,Y,U,Z)\sim P_{M}\times P_{X}P_{Y|X}P_{U|X}\delta_{z(U,Y)}$. We have $$\begin{aligned}
 & \mathbf{P}\{\mathsf{d}(X,\hat{Z})>\mathsf{D}\}\\
 & \le1-\mathbf{P}\{\mathsf{d}(X,Z)\le\mathsf{D}\,\mathrm{and}\,U=\hat{U}\}\\
 & \le\mathbf{E}\left[1-\mathbf{1}\{\mathsf{d}(X,Z)\le\mathsf{D}\}\mathbf{P}\{(U,M)=(\tilde{U},\tilde{M})_{P_{U|Y}(\cdot|Y)\times\delta_{M}}\,|\,M,X,Y,U\}\right]\\
 & \stackrel{(a)}{\le}\mathbf{E}\left[1-\mathbf{1}\{\mathsf{d}(X,Z)\le\mathsf{D}\}\left(1+\frac{dP_{U|X}(\cdot|X)\times P_{M}}{dP_{U|Y}(\cdot|Y)\times\delta_{M}}(U,M)\right)^{-1}\right]\\
 & \le\mathbf{E}\left[1-\mathbf{1}\{\mathsf{d}(X,Z)\le\mathsf{D}\}(1+\mathsf{L}^{-1}2^{\iota_{U;X}(U;X)-\iota_{U;Y}(U;Y)})^{-1}\right].\end{aligned}$$ where (a) is by 