<p>Let <span class="math-container">$f(n,s)$</span> denote the answer.</p>
<p>Claim: We have <span class="math-container">$f(n,s) = \frac{n}{2}+\Theta(\sqrt{sn})$</span> for any fixed <span class="math-container">$s$</span> as <span class="math-container">$n \to \infty$</span>. More precisely, <span class="math-container">$\lim_{n \to \infty} \frac{f(n,s)-\frac{n}{2}}{\sqrt{n}} = \Theta(\sqrt{s})$</span> for <span class="math-container">$s \ge 1$</span>.</p>
<p>Proof: For the lower bound, have the compressor divide into <span class="math-container">$s$</span> (nearly) equal pieces and output the (string of length <span class="math-container">$s$</span> consisting of the) majority bits in each piece (breaking ties arbitrarily), and the decompressor outputting each bit of the compressed string <span class="math-container">$n/s$</span> times (contiguously). For the upper bound, we assume for ease that each compressed string comes from the same number (namely, <span class="math-container">$2^{n-s}$</span>) of initial strings. Then, letting <span class="math-container">$|x\cap w|$</span> denote the number of bits <span class="math-container">$x,w$</span> have in common, just note that maximizing <span class="math-container">$\frac{1}{2^{n-s}}\sum_{x \in A} |x \cap w|$</span> over subsets <span class="math-container">$A \subseteq \{0,1\}^n$</span> of size <span class="math-container">$2^{n-s}$</span> yields <span class="math-container">$\frac{n}{2}+O(\sqrt{ns})$</span> (to see this, we can WLOG that <span class="math-container">$w = 0^n$</span> and then just fill <span class="math-container">$A$</span> with the <span class="math-container">$2^{n-s}$</span> strings with the most <span class="math-container">$0$</span>'s). <span class="math-container">$\square$</span></p>
<p>The proof probably allows one to take <span class="math-container">$s$</span> up to <span class="math-container">$\log n$</span>, but I'll leave the details. I also think it should extend to larger alphabets.</p>

CC BY-SA 4.0
2021-10-03T15:51:32.750Z
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.
Hhan
CC BY-SA 4.0
2021-10-02T13:19:46.187Z
2021-10-02T13:19:46.187Z
mathworker21
<p>Consider the following &quot;compression problem&quot; for a pair <span class="math-container">$(C,D)$</span> of algorithms: <span class="math-container">$C$</span> receives a uniformly random <span class="math-container">$x \in \{0,1\}^n$</span> and outputs a smaller bit string <span class="math-container">$y \in \{0,1\}^s$</span>. Algorithm <span class="math-container">$D$</span> receives <span class="math-container">$y$</span> as input and outputs an <span class="math-container">$n$</span>-bit string <span class="math-container">$\hat x$</span> that is an attempt to approximate <span class="math-container">$x$</span>. More precisely, the goal of this pair of algorithms is to maximise the expected number of coordinates of <span class="math-container">$\hat x$</span> that agree with <span class="math-container">$x$</span>, that is, <span class="math-container">$$\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].$$</span></p>
<p>I am trying to find an upper bound on this value, maximising over all <span class="math-container">$(C,D)$</span>, in terms of <span class="math-container">$n$</span> and <span class="math-container">$s$</span>; for concreteness, we can assume the algorithms are deterministic and computationally unbounded (or, equivalently, <span class="math-container">$y = f(x)$</span> and <span class="math-container">$\hat x = g(y)$</span> for arbitrary functions <span class="math-container">$f$</span> and <span class="math-container">$g$</span>).</p>
<p>Intuitively, since the &quot;compressed string&quot; <span class="math-container">$y$</span> reveals <span class="math-container">$s$</span> bits of information about <span class="math-container">$x$</span>, we should not be able to recover significantly more than <span class="math-container">$s$</span> bits of <span class="math-container">$x$</span> with certainty. Indeed, this suggests the strategy of setting <span class="math-container">$y = (x_1, \ldots, x_s)$</span>, which leads to an expectation of <span class="math-container">$s + (n-s)/2 = (n+s)/2$</span> correct bits by guessing the remainder arbitrarily. Ideally, we would like to show an upper bound of <span class="math-container">$(s + n)/2 + O(1)$</span>. (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.)</p>
<p>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 <span class="math-container">$x$</span> exactly. Is the solution to this (or a similar) problem known?</p>

CC BY-SA 4.0
2021-10-02T06:32:36.407Z
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\}$.
Marcel Dall'Agnol
CC BY-SA 4.0
2021-10-02T06:40:40.083Z
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}.$$
Marcel Dall'Agnol
CC BY-SA 4.0
2021-10-02T08:50:42.953Z
Do you have a specific regime of $(n,s)$ in mind? Like, $s$ fixed and $n$ large, or $s = n/3$ and $n$ large?
mathworker21
CC BY-SA 4.0
2021-10-02T09:05:05.770Z
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.
mathworker21
CC BY-SA 4.0
2021-10-02T10:23:19.007Z
Ah, yes. I had two regimes in mind, $s = O(\sqrt{n})$ and (mainly) $s = O(\log n)$ with $n$ large. While it would be nice to see the $s > 1$ case (maybe output the majority bit of $x \oplus z^{(i)}$ for some fixed $z^{(1)},\ldots,z^{(s)}$?), this answers the question for $s = O(1)$. Incidentally, earlier we found that the "approximate recovery" version of [Fano's inequality](https://arxiv.org/pdf/1901.00555.pdf) yields an upper bound of $\frac{n}{2} + O(n^{2/3})$, so it is between $n^{1/2}$ and $n^{2/3}$ for constant $s$. (There should be a simpler way to show tight bounds, though.)
Marcel Dall'Agnol
CC BY-SA 4.0
2021-10-02T10:31:19.300Z
At the end of the day we were hoping to compute this for large (exponential-sized) rather than binary alphabets, so the bound I was hoping for might still hold (since likely deviations around the mean should be a smaller interval). In any case, I'll be happy to accept your comment if you post it as an answer -- otherwise I'll try to update the question.
Marcel Dall'Agnol
CC BY-SA 4.0
2021-10-02T11:08:51.660Z
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
CC BY-SA 4.0
2021-10-02T16:43:52.780Z
Does the decompressor, algorithm D, know the length n ahead of time, or does D need to somehow guess the length from the length and values of the compressed string y ?
David Cary
<it.information-theory><kolmogorov-complexity><upper-bounds>
Upper bound on the expected number of correct bits via a "lossy compression"
Marcel Dall'Agnol
# Upper bound on the expected number of correct bits via a "lossy compression"

(Asked by: username_0 on 2021-10-02)

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?

**Tags:** it.information-theory, kolmogorov-complexity, upper-bounds

> **Comments:**
> **username_0**: 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\}$.  
> **username_0**: 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}.$$  
> **username_1**: Do you have a specific regime of $(n,s)$ in mind? Like, $s$ fixed and $n$ large, or $s = n/3$ and $n$ large?  
> **username_1**: 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.  
> **username_0**: Ah, yes. I had two regimes in mind, $s = O(\sqrt{n})$ and (mainly) $s = O(\log n)$ with $n$ large. While it would be nice to see the $s > 1$ case (maybe output the majority bit of $x \oplus z^{(i)}$ for some fixed $z^{(1)},\ldots,z^{(s)}$?), this answers the question for $s = O(1)$. Incidentally, earlier we found that the "approximate recovery" version of [Fano's inequality](https://arxiv.org/pdf/1901.00555.pdf) yields an upper bound of $\frac{n}{2} + O(n^{2/3})$, so it is between $n^{1/2}$ and $n^{2/3}$ for constant $s$. (There should be a simpler way to show tight bounds, though.)  
> **username_0**: At the end of the day we were hoping to compute this for large (exponential-sized) rather than binary alphabets, so the bound I was hoping for might still hold (since likely deviations around the mean should be a smaller interval). In any case, I'll be happy to accept your comment if you post it as an answer -- otherwise I'll try to update the question.  
> **username_2**: For a fixed $s>1$, as a simple generalization of @username_1, 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.  
> **username_3**: Does the decompressor, algorithm D, know the length n ahead of time, or does D need to somehow guess the length from the length and values of the compressed string y ?  

---

## 1 answers

### Answer by username_1 on 2021-10-02. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_2**: 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.  

---

