Let $\mathcal{X} \neq \phi $ be a finite set. Let $P_{XY_1Y_2}$ be a fixed joint distribution over $\mathcal{X}\times\mathcal{X}\times\mathcal{X}\ $ and that a random sample $(X,Y_1,Y_2 )$ is drawn using $P_{XY_1Y_2}$. Suppose there are two parties, $A$ and $B$ such that $A$ gets to observes $Y_1$ and $B$ gets to observes $Y_2$. Additionally $A$ knows the conditional distribution $P_{Y_1|X}$ and similarly $B$ knows the distribution $P_{Y_2|X}$.

I'm interested in finding a method which makes party $A$ construct $\hat{X}_1$ using the information $P_{Y_1|X}$ and $Y_1$ and similarly $B$ construct $\hat{X}_2$ using the information $P_{Y_2|X}$ and $Y_2$ such that $P(\hat{X}_1 \neq \hat{X}_2)$ is 'small' and $P(\hat{X}_1\neq X)$ is 'small'.

In other words I am interested in constructing a random variable based on correlated observations.

I do agree that the problem is not well posed. I look for only informal suggestions. Any relevant literature would also be really helpful.

Thanks in advance for your help.

  • 1
    $\begingroup$ This sounds like an interesting problem. I wonder if it can be mapped into a paper I wrote on optimal distributed scheduling (where correlating the schedule via a commonly known source of psuedorandomness is optimal). I usually don't provide stackexchange refs to myself but this one seems direclty related: ee.usc.edu/stochastic-nets/docs/… $\endgroup$
    – Michael
    Commented Jul 27, 2016 at 23:12
  • 1
    $\begingroup$ The mapping seems to be: $(\omega_i, \alpha_i)$ in the paper is like your $(Y_i, \hat{X}_i)$ variables. The utility function is $u=1\{\hat{X}_1=\hat{X}_2\}$ (we want to maximize its expectation) and the penalty function is $p=1\{\hat{X}_1\neq X\}$ (we want to constrain its expectation). One difference is that your problem has a variable $X$ that nobody knows, so the problems are a bit different. But perhaps similar methods are useful. I suspect Theorem 1 in the above paper implies that for your max-utility problem with one constraint, it is optimal to timeshare over 2 pure strategies. $\endgroup$
    – Michael
    Commented Jul 27, 2016 at 23:34
  • 1
    $\begingroup$ In essence, you're talking about extracting common randomness $X$ given $Y_1$ and $Y_2$ separately. This was first studied by Gacs and Korner in the 70s, and googling for Gacs-Korner common information would likely be useful to you. IIRC, there are also relatively recent papers by Anatharam et al that study such problems over the Gray-Wyner system in a unified way, and may thus be germane. $\endgroup$ Commented Jul 28, 2016 at 0:15
  • $\begingroup$ Thank you all for your suggestions. $\endgroup$
    – Dinesh
    Commented Jul 28, 2016 at 6:36
  • $\begingroup$ Given the posted solution, I should mention that the previous comment is in an information theoretic context. $\endgroup$ Commented Jul 28, 2016 at 20:16

1 Answer 1


Here is a trick to map an instance of your problem to the framework of the paper "Distributed Stochastic Optimization via Correlated Scheduling" (IEEE Trans Netw. April 2016): http://ee.usc.edu/stochastic-nets/docs/distributed-optimization-ton.pdf

Let's perform a notation shift: \begin{align} (Y_1,Y_2) &\leftrightarrow (\omega_1, \omega_2) \quad \mbox{[distributed observations]} \\ (\hat{X}_1, \hat{X}_2) &\leftrightarrow (\alpha_1, \alpha_2) \quad \mbox{[distributed actions]} \end{align}

Fix $\delta \geq 0$. Suppose you want each device $i \in \{1,2\}$ to choose an estimate $\hat{X}_i \in \mathcal{X}$ as a (potentially random) function of its observation $Y_i$ to solve the following optimization:

Problem 1:

\begin{align} \mbox{Maximize:} & \quad P\left[\hat{X}_1 =X\right]\\ \mbox{Subject to:} & \quad P\left[\hat{X}_1 \neq \hat{X}_2\right] \leq \delta \end{align}

Notice that Problem 1 is always feasible (so it is possible to satisfy the constraint, for any $\delta \geq 0$), since we can choose the trivial strategy of always using $\hat{X}_1=\hat{X}_2=c$ for some pre-agreed-upon constant $c \in \mathcal{X}$. Intuitively, relaxing the value of $\delta$ allows for a larger utility $P[\hat{X}_1 = X]$.

Define the following utility function $u(\cdot)$ and penalty function $p(\cdot)$: \begin{align} p:\mathcal{X}^4 \rightarrow \mathbb{R} &, \quad p(x_1,x_2, y_1, y_2) = 1\{x_1\neq x_2\}\\ u:\mathcal{X}^4 \rightarrow \mathbb{R} &, \quad u(x_1,x_2,y_1,y_2) = \sum_{a\in \mathcal{X}}\sum_{b \in \mathcal{X}}\sum_{c \in \mathcal{X}} 1\{y_1=a, y_2=b, x_1=c\}P[X=c|Y_1=a,Y_2=b] \end{align} where $1\{F\}$ is a binary indicator function for the event $F$. This fits the general structure for $u(\cdot)$ and $p(\cdot)$ functions in the paper. So the "trick" is to define the utility function in terms of the conditional mass function $P[X=c|Y_1=a,Y_2=b]$. This allows treatment of the random variable $X$ that nobody knows. The paper considers optimal selection of $\hat{X}_1$ and $\hat{X}_2$ to solve the following:

Problem 2:

\begin{align*} \mbox{Maximize:} & \quad E[u(\hat{X}_1, \hat{X}_2, Y_1,Y_2)] \\ \mbox{Subject to:} & \quad E[p(\hat{X}_1,\hat{X}_2, Y_1,Y_2)] \leq \delta \end{align*}

With some thought, it can be shown that Problem 2 is equivalent to Problem 1.

Hence, Theorem 1 of the paper can be applied to this problem with $K=1$ constraint, to show that optimality can be achieved by timesharing over $K+1=2$ pure strategies. Specifically, there exists a probability $\theta \in [0,1]$, together with two deterministic functions (called "pure strategies") of the form: \begin{align} \mbox{Pure strategy 1:}& \quad f:\mathcal{X}^2 \rightarrow\mathcal{X}^2 , \quad f(y_1,y_2)=(f_1(y_1), f_2(y_2)) \\ \mbox{Pure strategy 2:}& \quad g:\mathcal{X}^2 \rightarrow\mathcal{X}^2 , \quad g(y_1,y_2)= (g_1(y_1), g_2(y_2)) \end{align} so that the following strategy is optimal for problem 2 (and hence for problem 1): Let both devices 1 and 2 share a commonly known random variable $B \in \{0,1\}$ with $P[B=1]=\theta$, where $B$ is chosen in advance and is independent of $(X,Y_1,Y_2)$. Then:

Case 1: If $B=1$, both devices use pure strategy 1. So if device $i$ observes $Y_i$, it chooses $\hat{X}_i=f_i(Y_i)$.

Case 2: If $B=0$, both devices use pure strategy 2. So if device $i$ observes $Y_i$, it chooses $\hat{X}_i = g_i(Y_i)$.

The same structure of using only 2 pure strategies would hold even for a larger number of devices $N \geq 2$.

By the way, if you changed the problem to an unconstrained one of maximizing $P[\hat{X}_1 = X] - \gamma P[\hat{X}_1 \neq \hat{X}_2]$, then $K=0$ (there are no constraints) and so a single pure strategy is optimal. Based on this, the "drift-plus-penalty" framework later in the paper develops a sequential way of choosing pure strategies that, over time, solves the constrained problem of interest.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .