# Ambivalent Coding

Consider the following situation, I want to send one of two bitstrings, A or B, to a receiver. Clearly, I can do this by sending the shortest, but is there a better way? It seems that the requirement that one of either should arrive should allow us to save on bits.

To give a specific application: say the receiver and I have a DFA, and I want to send some word in the language described by the automaton. I can do this by encoding a path over the automaton as an n-ary string. But if there are several paths over the automaton, I don't care which the receiver decodes, so long as it decodes to the right word.

Is there research into this question? Are there google-able phrases that I don't know about?

Also, if we use a probabilistic DFA, it defines a probability distribution over the words in its language. By the Kraft inequality, there exists a coding for this probability whereby the length of the code for word W is equal to the logarithm of P(W). However if we use a specific path A over the automaton to encode W, that path may only contribute part of the probability mass of P(W). Say there are two paths A and B that produce W, so that P(A) + P(B) = P(W). Is there a scheme that allows us to send a message with length log(P(W)) that decodes into either A or B?

• The domain of possible bitstrings is not restricted, in particular re length? Because if the domain of bitstrings is restricted, then it's trivially obvious that you can use a shorter encoding. Sort all bitstrings in the domain, and send the position of A instead of A. Jan 15, 2013 at 14:54
• @MSalters: I don't understand. Do you mean that any bitstring x from a restricted set can be compressed (by encoding the set and the index of x)? That's just compression, isn't it? The key point here is that I want A or B to arrive, and whether this ambivalence allows a scheme to get my message across in less than min(l(a), l(B)) bits. Jan 15, 2013 at 15:42
• Yes. Assume that the domain is all possible bitstrings except just "0". Then 1 can be coded as 0, 10 as 1, 11 as 10, etc. This is of course compression, and that answers your very question wh ether it's optimal to just send A (No, send compressed(A) instead). That would be trivial, so that's why I wanted to clarify the domain assumptions. Jan 15, 2013 at 15:59
• I guess I would say that the sender and receiver are already using some pre-arranged compression and sending the compressed messages over a basic channel. However, since the decompressor translates both A and B to the desired output, that seems like a fact you should be able to use somehow to shorten the message further. So, if it helps, we can assume that A and B are both reasonably/maximally compressed (ie. random). Jan 16, 2013 at 10:29

I can answer my own question here. The original code over $S = \{A, B, \ldots\}$ corresponds (by the Kraft inequality) to a probability distribution on $S$. I can partition S by the subsets I'm ambivalent about, so in $S'$, there's an element $a = \{A, B\}$ to denote that I don't care about the difference between $A$ and $B$.
This gives me a simple probability distribution on $S'$: $p(a) = p(A) + p(B)$.
By the Kraft inequality, again, there is a coding that corresponds to this distribution, so that I can use an algorithm like arithmetic coding to achieve acode of length $- \log p(a) = - \log p(A) + p(B)$.