0
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Jul 5, 2011 at 19:21
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Jul 5, 2011 at 19:26
  • 1
    $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Jul 5, 2011 at 22:43
  • $\begingroup$ 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? $\endgroup$
    – Henrique de Oliveira
    Feb 6, 2014 at 20:17

1 Answer 1

Reset to default
1
$\begingroup$

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?

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Indeed. The semiring I am looking at is constructed given an information measure, which only needs to be concave and symmetric. Its associativity is equivalent to this information measure having an associativity property that says the two schemes above for measuring a ternary random variable are equivalent. This is equivalent to the information measure being the Shannon entropy. I would like to look at other information measures, such as the Reyni entropy, but ones I have found are not of the form I describe above for n-ary random variables. $\endgroup$
    – Ryan Thorngren
    Jul 6, 2011 at 19:04
  • $\begingroup$ I've edited the question hopefully to address this question. $\endgroup$
    – Ryan Thorngren
    Jul 6, 2011 at 19:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.