# Upper bound on the expected number of correct bits via a "lossy compression"

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?

• 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\}$. Oct 2, 2021 at 6:32
• 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}.$$ Oct 2, 2021 at 6:40
• Do you have a specific regime of $(n,s)$ in mind? Like, $s$ fixed and $n$ large, or $s = n/3$ and $n$ large? Oct 2, 2021 at 8:50
• 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. Oct 2, 2021 at 9:05
• 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.
– Hhan
Oct 2, 2021 at 11:08

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.
• 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.