5
$\begingroup$

Consider the following "compression problem" for a pair $(C,D)$ of algorithms: $C$ receives a uniformly random $x \in \{0,1\}^n$ and outputs a smaller bit string $y \in \{0,1\}^s$. Algorithm $D$ receives $y$ as input and outputs an $n$-bit string $\hat x$ that is an attempt to approximate $x$. More precisely, the goal of this pair of algorithms is to maximise the expected number of coordinates of $\hat x$ that agree with $x$, that is, $$\mathbb E_{x \sim \{0,1\}^n} [\#\{i \in [n] : x_i = \hat x_i\}] = \sum_{i = 1}^n \mathbb P_{x \sim \{0,1\}^n}[x_i = \hat x_i].$$

I am trying to find an upper bound on this value, maximising over all $(C,D)$, in terms of $n$ and $s$; for concreteness, we can assume the algorithms are deterministic and computationally unbounded (or, equivalently, $y = f(x)$ and $\hat x = g(y)$ for arbitrary functions $f$ and $g$).

Intuitively, since the "compressed string" $y$ reveals $s$ bits of information about $x$, we should not be able to recover significantly more than $s$ bits of $x$ with certainty. Indeed, this suggests the strategy of setting $y = (x_1, \ldots, x_s)$, which leads to an expectation of $s + (n-s)/2 = (n+s)/2$ correct bits by guessing the remainder arbitrarily. Ideally, we would like to show an upper bound of $(s + n)/2 + O(1)$. (There is a nontrivial strategy that achieves more than saving the prefix, but the advantage is exponentially small. I suspect not much else could be done, but would be happy to see a solution in the form of a strategy achieving a superconstant difference.)

This seems like a natural problem for an information-theoretic or Kolmogorov complexity argument, but I have not been able to find any that apply; most of them deal with the problem of recovering $x$ exactly. Is the solution to this (or a similar) problem known?

Improve this question
$\endgroup$
8
  • $\begingroup$ An alternative formulation, that makes the role of the "compressor" C and the "decompressor" D more evident, is as follows. Since the string y specifies a subset of bit strings, it is clear that D can do no better than to guess the most frequent symbol for each coordinate i. Therefore, C is equivalent to specifying a partition $\{P_y\}_{y\in\{0,1\}^n}$, and the expectation is $$\frac1{2^n} \sum_{y \in \{0,1\}^n} \sum_{i=1}^n \max\{\#\{z \in P_y : z_i=0\},\#\{z \in P_y : z_i=0\}\}.$$ The upper bound then amounts to maximising this expression over all partitions $\{P_y\}$. $\endgroup$
    – Marcel Dall'Agnol
    Commented Oct 2, 2021 at 6:32
  • $\begingroup$ As for the strategy achieving more than $(n+s)/2$, consider the case $s=1$ with the partition $P_0=\{x:x_1=0\}\cup\{10^{n−1}\} \setminus \{01^{n−1}\}$ and $P_1= \{0,1\}^n \setminus P_0= \{x:x_1=1\} \cup \{01^{n−1}\} \setminus \{10^{n−1}\}$. The best guess for $x_1$ is $y$, which is correct with probability $1−\frac1{2^{n−1}}$; and the best guess for all other $x_i$ is also $y$, which is correct with probability $\frac{2^{n−2}+1}{2^{n−1}}=\frac1{2}+\frac1{2^{n−1}}$. Then the expectation is $$\frac{n+1}{2} + \frac{n-2}{2^{n-1}} > \frac{n+1}{2}.$$ $\endgroup$
    – Marcel Dall'Agnol
    Commented Oct 2, 2021 at 6:40
  • $\begingroup$ Do you have a specific regime of $(n,s)$ in mind? Like, $s$ fixed and $n$ large, or $s = n/3$ and $n$ large? $\endgroup$
    – mathworker21
    Commented Oct 2, 2021 at 8:50
  • 2
    $\begingroup$ You can get $\frac{n+\Omega(\sqrt{n})}{2}$ when $s=1$ by having the compressor output the majority bit (break ties by erring to $0$, say), and then the decompressor outputting that bit $n$ times. $\endgroup$
    – mathworker21
    Commented Oct 2, 2021 at 9:05
  • 1
    $\begingroup$ For a fixed $s>1$, as a simple generalization of @mathworker21, the compression that dividing $n$-bit string into $s$ $n/s$-bit strings and taking the majority bit of each strings (and its pair) has $\frac{n/s + \Omega(\sqrt{n/s})}2 \cdot s = \frac{n + \Omega(\sqrt{ns})}2$-rate. $\endgroup$
    – Hhan
    Commented Oct 2, 2021 at 11:08

1 Answer 1

Reset to default
3
$\begingroup$

Let $f(n,s)$ denote the answer.

Claim: We have $f(n,s) = \frac{n}{2}+\Theta(\sqrt{sn})$ for any fixed $s$ as $n \to \infty$. More precisely, $\lim_{n \to \infty} \frac{f(n,s)-\frac{n}{2}}{\sqrt{n}} = \Theta(\sqrt{s})$ for $s \ge 1$.

Proof: For the lower bound, have the compressor divide into $s$ (nearly) equal pieces and output the (string of length $s$ consisting of the) majority bits in each piece (breaking ties arbitrarily), and the decompressor outputting each bit of the compressed string $n/s$ times (contiguously). For the upper bound, we assume for ease that each compressed string comes from the same number (namely, $2^{n-s}$) of initial strings. Then, letting $|x\cap w|$ denote the number of bits $x,w$ have in common, just note that maximizing $\frac{1}{2^{n-s}}\sum_{x \in A} |x \cap w|$ over subsets $A \subseteq \{0,1\}^n$ of size $2^{n-s}$ yields $\frac{n}{2}+O(\sqrt{ns})$ (to see this, we can WLOG that $w = 0^n$ and then just fill $A$ with the $2^{n-s}$ strings with the most $0$'s). $\square$

The proof probably allows one to take $s$ up to $\log n$, but I'll leave the details. I also think it should extend to larger alphabets.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I also used a similar approach, and I think that the same bound holds for most of the regime of $s$. To prove the statement for all $s$, it requires the approximation of the ratio of the number of Hamming sphere with radius $r$ and the number of points that has the exact Hamming weight $r$, up to the additive small error, which I failed to find. I think there should be relevant literature, though. $\endgroup$
    – Hhan
    Commented Oct 3, 2021 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.