# Information Theory of “decision machines”

Hello, everyone. I am considering the following type of situation.

Suppose I have a decision machine (DM) that I can ask any yes/no question and I want to use this to measure an n-ary random variable. Measuring a binary random variable using the DM with prior probability distribution ${p,1-p}$ gives an average change in uncertainty $S(p)$. The information measures giving the average change in uncertainty for measuring n-ary random variables with the DM will be built up from $S(p)$ depending on how the measurement is done.

For example, when measuring a ternary random variable $X \in {x_1,x_2,x_3}$, with prior probability distribution $p_1,p_2,p_3$ I can first ask "is $X=x_1$?", and if the answer is no, "is $X=x_2$", after which I will certainly know the value of $X$. This will give an information measure $S(p_1)+(1-p_1)S(p_2/(1-p_1))$. Similarly I can first ask "is $X=x_3$?", followed by "is $X=x_1$"?, giving an average change in uncertainty $S(p_3)+(1-p_3)S(p_1/(1-p_3))$.

My goal is to relate this type of information measure to a particular nonassociative structure which I am studying. This "semiring" is constructed given an information measure, and the associativity of addition in the semiring is equivalent to

$S(p_3)+(1-p_3)S(p_1/(1-p_3))=S(p_1)+(1-p_1)S(p_2/(1-p_1))$,

a sort of associativity for binary information measures. Along with $S(p)=S(1-p)$, the only information measure satisfying this is the Shannon entropy.

I would like to relate features of this structure to features of other information measures, to better understand the role information theory plays in this construction, which is a sort of Witt ring in characteristic one. However, all of the measures I have found are defined for arbitrary n-ary random variables in a way that $S(p_1,...,p_n)$ is not built up by asking yes/no questions as above.

I was hoping one of you out there had some references to similar things that have been studied, because my own searches have largely come up empty-handed.

Thanks.

-
Although potentially thunder-stealing, you might get a more helpful response if you say more about the nonassociative structure and the type of relations you imagine might exist. Gerhard "The Answer May Still Flash" Paseman, 2011.07.05 – Gerhard Paseman Jul 5 '11 at 19:21
Further, this is a shot in the dark and may be unhelpful. I heard a lecture at ICM 2010 about differential privacy, which was used to measure how much a system can reveal about a population while still maintaining privacy for each individual record. If I remember more detail I will post it near this comment. Gerhard "My Memory's Good, Just Short" Paseman, 2011.07.05 – Gerhard Paseman Jul 5 '11 at 19:26
Cynthia Dwork gave the presentation. There is a goodly amount of Internet material on differential privacy. I think it may be worth half an hour or so of time looking into it. Hope this helps. Gerhard "Email Me About System Design" Paseman, 2011.07.05 – Gerhard Paseman Jul 5 '11 at 22:43
I'm not sure I understand the definition of your measure $S(p)$. It's not the number of questions, because then any binary random variable would have the same measure. If instead of asking first "is $X=x_1$", we asked is "X=x_2", would we arrive at the same measure? – Henrique de Oliveira Feb 6 '14 at 20:17

I assume your "average change in uncertainty" $S(p)$ in the case of a binary variable is meant to be the usual entropy, $-p\log p-(1-p)\log(1-p)$. In that case, your two formulas for the change in uncertainty for a 3-valued $X$, from asking first about $x_1$ and then about $x_2$ or from asking first about $x_3$ and then about $x_1$, also reduce (as one would expect) to the entropy associated to $X$, namely $-\sum_{i=1}^3 p_i\log p_i$. So I'm not sure what you mean by "this type of information measure" or where the non-associativity should come from, since it's just traditional entropy. Did you have some other function $S$ in mind?