Information Theory of "decision machines"

2011-07-05T18:10:14Z

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.

Answer by Andreas Blass for Information Theory of "decision machines"

2011-07-05T23:34:50Z

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?

Information Theory of "decision machines" - MathOverflow

Information Theory of "decision machines"

Answer by Andreas Blass for Information Theory of "decision machines"