Generating Correlated Random Variables via Shared Randomness



Tuesday, 11 April 2017, 16:00 to 17:30


In coordination problems, agents have to perform actions so that their joint actions produce outputs according to some prescribed joint distribution. Such problems arise naturally in several diverse areas such as control, game theory and task assignment. An early work of this kind in information theory literature is due to Wyner(1975) who characterized the minimum rate of common randomness required by two agents to sample approximately from the joint distribution $p(x,y)$ of correlated random variables $X,Y$. In practice, shared randomness is also an important aspect of interest. We consider a problem in which in addition to Wyner's setting, the server has access to two independent sources of randomness each of which is shared with a different agent. The goal is to minimize the rate of common message. We present some results in relation to this.