Simulation of a Random Variable and its Application to Game Theory
提出一种从带边信息的随机源模拟目标随机变量的新工具，精度随Rényi熵差指数衰减，并应用于有限阶段零和重复博弈中，研究最大最小值如何收敛到长期值。
We provide a new tool for simulation of a random variable (target source) from a randomness source with side information. Considering the total variation distance as the measure of precision, this tool offers an upper bound for the precision of simulation, which is vanishing exponentially in the difference of Rényi entropies of the randomness and target sources. This tool finds application in games in which the players wish to generate their actions (target source) as a function of a randomness source such that they are almost independent of the observations of the opponent (side information). In particular, we study zero-sum repeated games in which the players are restricted to strategies that require only a limited amount of randomness. Let be the max-min value of the n stage game. Previous works have characterized [Formula: see text], that is, the long-run max-min value, but they have not provided any result on the value of v n for a given finite n-stage game. Here, we utilize our new tool to study how v n converges to the long-run max-min value.