<p>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$.</p>

<p>This gives me a simple probability distribution on $S'$: $p(a) = p(A) + p(B)$.</p>

<p>By the Kraft inequality, again, there is a coding that corresponds to this distribution, so that I can use an algorithm like <a href="http://en.wikipedia.org/wiki/Arithmetic_coding" rel="nofollow">arithmetic coding</a> to achieve acode of length $- \log p(a) = - \log p(A) + p(B)$.</p>

CC BY-SA 3.0
2014-05-08T20:02:25.777Z
2014-05-08T20:02:25.777Z
Peter
<p>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.</p>

<p>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.</p>

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

<p>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?</p>

CC BY-SA 3.0
2013-01-15T14:54:43.330Z
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.
MSalters
CC BY-SA 3.0
2013-01-15T15:42:23.227Z
@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.
Peter
CC BY-SA 3.0
2013-01-15T15:59:51.510Z
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.
MSalters
CC BY-SA 3.0
2013-01-16T10:29:49.813Z
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).
Peter
<coding-theory>
Ambivalent Coding
Peter
# Ambivalent Coding

(Asked by: username_0 on 2013-01-14)

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?

**Tags:** coding-theory

> **Comments:**
> **username_1**: 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.  
> **username_0**: @username_1: 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.  
> **username_1**: 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.  
> **username_0**: 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).  

---

## 1 answers

### Answer by username_0 on 2014-05-08. Score: 1 | Accepted answer

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](http://en.wikipedia.org/wiki/Arithmetic_coding) to achieve acode of length $- \log p(a) = - \log p(A) + p(B)$.


---

