0
$\begingroup$

Supposing Alice and Bob share $\rho$-correlated sequences in $\{0,1\}^n$, what coding theory based schemes are available for Alice and Bod to extract sequences $A,B\in\{0,1\}^n$ respectively such that $A,B$ agree on $k(n,\rho)$ bits for cases (I am not worried about secrecy):

$(1)$ Alice and Bob communicate.

$(2)$ Alice and Bob do not communicate.

Assume Alice and Bob exchange $m(n,\rho)$ bits in total to agree on $k(n,\rho)$ bits.

What is the min rate $\lim_{n\rightarrow\infty}\frac{m(n,\rho)}{k(n,\rho)}$?

Rather more generally, completely, what is explicit formula for the curve $\lim_{n\rightarrow\infty}(m(n,\rho),k(n,\rho))\subseteq\Bbb R^2$?

$\endgroup$
2
  • $\begingroup$ Your second question may ask for how much Gacs-korner common information can be extracted in bits? $\endgroup$
    – user74969
    Commented Jun 14, 2015 at 20:21
  • $\begingroup$ Could you explain in more details in answer? $\endgroup$
    – Turbo
    Commented Jun 14, 2015 at 21:54

1 Answer 1

2
$\begingroup$

According to G-K common information $K(X;Y) = \mathop {Sup{\rm{ }}H(V)}\limits_{V = f(X) = g(Y)}$ :

Roughly speaking, it measures the amount of common randomness that can be separately extracted from either marginal of the two jointly distributed random variables from the $\rho$-correlated i.i.d. generated sequences $(A^n,B^n)$. You need to reformulate your questions in language of common information. Also, for more details, you may look at the known paper by GK:

P. Gacs and J. Korner, “Common information is far less than mutual information”, Problems of Control and Information Theory, vol. 2, no. 2, pp. 119–162, 1972.

$\endgroup$

You must log in to answer this question.

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