3
$\begingroup$

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.

$\endgroup$
5
  • 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

2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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