13
$\begingroup$

I am stuck with this problem that looks like it should be a counting argument. Consider two binary strings $A$ and $B$. String $A$ is of length $n$ and $B$ is of length $2n$.

Alice has both strings $A$ and $B$ and wants to send one single message to Bob (who doesn't get to see the strings at all) telling him approximately how close $A$ is to every substring of $B$ of length $n$. In particular, for every substring of $B$ of length $n$, Bob wants to be able to work out the Hamming distance between $A$ and that substring to within a multiplicative factor of $2$ just from this single message.

As an example, let $A = 101$ and $B = 011001$. The true Hamming distances are $2, 2, 1, 1$. Bob, having received the message from Alice, has to output 4 numbers. Bob's outputs values must be in the range 2 to 4 for the first two numbers and 1 to 2 for the next two.

Assuming that Alice and Bob can agree on a determinisic protocol beforehand, how many bits does Alice have to send to Bob?

Now posted to https://mathoverflow.net/questions/264959/a-communication-complexity-problem-for-finding-near-matches .

$\endgroup$
  • 1
    $\begingroup$ Why not 1 to 4 for hamming distance 2? Are you only interested in one sided estimates? $\endgroup$ – kodlu Mar 11 '17 at 14:26
  • $\begingroup$ @kodlu I defined them as one sided estimates although I would be very happy with an answer that covered two sided estimates instead if that were any easier to come up with. $\endgroup$ – felipa Mar 11 '17 at 15:18
  • $\begingroup$ "how many bits does Alice have to send to Bob?" So you're looking for a protocol that gives the minimun length for the worst case, or for the protocol that gives the minimum average bits? $\endgroup$ – leonbloy Mar 14 '17 at 18:59
  • $\begingroup$ @leonbloy I am looking for the minimum length in the worst case or an approximation for this. However, anything non-trivial one can say about the question would be interesting. $\endgroup$ – felipa Mar 14 '17 at 19:39
  • $\begingroup$ The case $B=A^2$ looks interesting. Also, let $h_S(i)=H(S,S_i S_{i+1} \ldots S_n S_1 \ldots S_{i-1})$. If $h_B(i)$ is "small" for "small" $i$, then that would help. $\endgroup$ – Aravind Mar 16 '17 at 16:50
4
+25
$\begingroup$

This is not a complete answer up to a function in closed form or trivial summation, but just a reduction to a pure combinatorial problem.

Is it possible to send data at all? Yes, Alice can send just a concatenation of $A$ and $B$ and be happy doing nothing. This takes $3n$ bits. There is a trivial way to save 1 bit. Note that $A$ and $B$ give the same sequence as $\overline{A}$ and $\overline{B}$, where $\overline{S}$ means string $S$ with each character flipped (i. e., 0 becomed 1 and 1 becomes 0). So we can throw away the first character $a_0$ of $A$ assuming it to be zero (otherwise replace $A$ and $B$ with $\overline{A}$ and $\overline{B}$ correspondingly). So we have $3n - 1$ bits. This approach I call trivial.

Is it possible to save significant number of bits with no information loss? The best way to do it is the following. Let $D = D(A, B)$ be a desired sequence of distances. Let Alice and Bob just enumerate all possible such sequqnces, i. e., all sequences $D_i$ such that there is at least one pair $(A_i, B_i)$ such that $D_i = D(A_i, B_i)$. Then Alice sends to Bob just a zero-based serial number of $D$. So new question is: how many different sequences can be produced by all pairs of $A$ and $B$ of length $n$ and $2n$ correspondingly? There is a related question for the case when length of $B$ is $2n-1$. Note that if Bob doesn't know $n$ then Alice can append leading zeros to the number to make the length of her message an information about $n$. I have reason to say that the number of difference sequences is greater than $2^n$, so the length of the message with serial number of the sequence reflects the value of $n$.

Now let see how it is possible to save even more information using allowed one-sided error of Bob's result. Let Alice after computing the sequence $D$ transform it into a sequence $T = T(D)$ in the following way and send a serial number of $T$. Each 0 remains to be 0. Each 1 is replaced by 2, and each 2 remains to be 2. Each 3, 4, 5 are replaced by 6, and each 6 remains to be 6 etc. I. e., each number $2^k - 1, 2^k, \ldots, 2^{k + 1} - 3$ is replaced by $2^{k + 1} - 2$, and $2^{k + 1} - 2$ is not changed. It is easy to see that taking the sequence $T$ instead of the sequence $D$ Bob makes an allowed one-sided error. So the desired question is: how many different sequences $T(D(A, B))$ there are for each $n$? Also it is possible that information about $n$ should be added somehow.

And the third version of the problem is about two-sided error allowed. I suggest the same idea: let Alice transform $D$ into $T' = T'(D)$ in the following way and send a serial number of $T'$. Each 0 remains to be 0. Each 1, 2, 3 and 4 become 2. Each 5, 6, $\ldots$, 20 becomes 10. So, each $\frac{4^k - 1}{3}, \frac{4^k - 1}{3} + 1, \ldots, \frac{4^{k + 1} - 4}{3}$ becomes $\frac{2\cdot 4^k - 2}{3}$. It is easy to see that taking sequence $T'$ instead of sequence $D$ Bob makes an allowed two-sided error. So the new question is: how many different sequences $T'(D(A, B))$ there are for each $n$? Also it is possible that information about $n$ should be added somehow.

And finally I give some computational results and compare them with trivial one. $$\begin{array}{|c|r|l|r|l|r|l|} \hline n & \#D & \frac{\log_2 \#D}{3n - 1} & \#T & \frac{\log_2 \#T}{3n - 1} & \#T' & \frac{\log_2 \#T'}{3n - 1} \\\hline 1 & 4 & 1 & 4 & 1 & 4 & 1 \\\hline 2 & 21 & 0.878463 & 8 & 0.6 & 8 & 0.6 \\\hline 3 & 124 & 0.869275 & 41 & 0.669694 & 14 & 0.475919 \\\hline 4 & 825 & 0.88075 & 132 & 0.640399 & 23 & 0.411233 \\\hline 5 & 6024 & 0.896893 & 326 & 0.596338 & 109 & 0.483442 \\\hline 6 & 47391 & 0.913666 & 700 & 0.555954 & 363 & 0.500225 \\\hline 7 & 395944 & 0.929747 & 2698 & 0.569884 & 1149 & 0.508308 \\\hline 8 & 3396881 & 0.943295 & 9129 & 0.57201 & 3230 & 0.50684 \\\hline 9 & 30095408 & 0.955502 & 31348 & 0.574465 & 7209 & 0.492907 \\\hline 10 & 267147407 & 0.965278 & 102212 & 0.573835 & 14910 & 0.478069 \\\hline 11 & ? & ? & 297939 & 0.568271 & 31060 & 0.466337 \\\hline 12 & ? & ? & 742605 & 0.557207 & 62634 & 0.455276 \\\hline \end{array} $$

It looks like sending sequence with no error tends to have no significant benefit, while allowed two-sided error reduces quantities of information approximately twice.

$\endgroup$
  • $\begingroup$ The numbers are decreasing which is very interesting! $\endgroup$ – user66307 Mar 16 '17 at 13:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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