CHANNEL SIMULATION AND CODING WITH SIDE INFORMATION

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