Information Theory of "decision machines" - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T11:31:45Z http://mathoverflow.net/feeds/question/69558 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/69558/information-theory-of-decision-machines Information Theory of "decision machines" Ryan Thorngren 2011-07-05T18:10:14Z 2011-07-20T19:22:11Z <p>Hello, everyone. I am considering the following type of situation.</p> <p>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. </p> <p>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))$.</p> <p>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</p> <p>$S(p_3)+(1-p_3)S(p_1/(1-p_3))=S(p_1)+(1-p_1)S(p_2/(1-p_1))$,</p> <p>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.</p> <p>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.</p> <p>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.</p> <p>Thanks.</p> http://mathoverflow.net/questions/69558/information-theory-of-decision-machines/69586#69586 Answer by Andreas Blass for Information Theory of "decision machines" Andreas Blass 2011-07-05T23:34:50Z 2011-07-05T23:34:50Z <p>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 <code>$x_1$</code> and then about <code>$x_2$</code> or from asking first about <code>$x_3$</code> and then about <code>$x_1$</code>, also reduce (as one would expect) to the entropy associated to $X$, namely <code>$-\sum_{i=1}^3 p_i\log p_i$</code>. 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?</p>