Channel Simulation and Coding With Side Information

We study the minimum random bit rate required to simulate a random system (channel), where the simulator operates with a given external input, As measures of simulation accuracy we use both the variational distance and the d distance between joint input-output distributions. We find the asymptotic number of random bits per input sample required for accurate simulation, as a function of the distribution of the input process. These results hold for arbitrary channels and input processes, including nonstationary and nonergodic processes and do not hinge on a specific simulation scheme. A by-product of our analysis is a general formula for the minimal achievable source coding rate with side information.