Wikipedia:Reference desk/Archives/Mathematics/2018 September 9

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 9

Probability and Message Length

According to the article Inductive probability the "message length" $L$ relates to probability $P$ with $P(x)=2^{-L(x)}$ or $L(x)=-\log _{2}(P(x))$. So I presume all formulas from probability theory (for conjunction, disjunction etc) have a equivalent purely in terms of message length.

The article explicitly gives only the formula for conjunction:

$L(A\land B)=L(B)+L(A|B)=L(A)+L(B|A)$

Could you give me also the formulas of disjunction, negation, and conditional length? I'm at loss here.

$L(A\lor B)=$

$L(\neg A)=$

$L(A|B)=$

Your help would be greatly appreciated!

Cubefox (talk) 13:38, 9 September 2018 (UTC)

Well, for example, just using the formulas you've already listed (and the formula for disjunction), we have

$L(A\lor B)=-\log _{2}[P(A\lor B)]=-\log _{2}[P(A)+P(B)-P(A\land B)]=-\log _{2}[2^{-L(A)}+2^{-L(B)}-2^{-L(A\land B)}]$.

There isn't much that you can do to simplify that expression. Logarithms are great to apply to products, but they don't do anything helpful when applied to sums. Similarly,

$L(\neg A)=-\log _{2}[P(\neg A)]=-\log _{2}[1-P(A)]=-\log _{2}[1-2^{-L(A)}]$.

But conditional probability simplifies nicely:

$L(A\mid B)=-\log _{2}[P(A\mid B)]=-\log _{2}[P(A\land B)/P(B)]=-\log _{2}[2^{-L(A\land B)}/2^{-L(B)}]=L(A\land B)-L(B)$,

which is just a rewriting of the formula for $L(A\land B)$. —Bkell (talk) 16:47, 9 September 2018 (UTC)

Thanks for your efforts! Do you think there are "nice" formulas for any of the other 16 logical connectives or is conjunction the only one? --Cubefox (talk) 17:30, 9 September 2018 (UTC)

Well, $L(\top )=-\log _{2}[P(\top )]=-\log _{2}(1)=0$ and $L(\bot )$, i.e., $-\log _{2}[P(\bot )]$, i.e., $-\log _{2}(0)$, is undefined (or maybe you want to define it to be $\infty$, depending on your purposes). And I suppose you already have formulas for $L(A)$ and $L(B)$. We've discussed $L(A\land B)$, $L(A\lor B)$, and $L(\neg A)$, and clearly $L(\neg B)$ is just the same. That's eight out of the 16 logical connectives right there. You can work out formulas for the others using basic formulas from probability or set theory or Boolean algebra, along with basic properties of logarithms to convert between $P$ and $L$; but I don't expect the others to give particularly "nice" formulas in terms of $L$, because the only nontrivial thing you can do with $P(A)$ and $P(B)$ using just multiplication (so that it plays nicely with logarithms) is $P(A)P(B)$, which is $P(A\land B)$ assuming independence of $A$ and $B$. You're going to need to use addition or subtraction in order to express $P(A\odot B)$ in terms of $P(A)$ and $P(B)$ for other logical connectives $\odot$. —Bkell (talk) 05:00, 10 September 2018 (UTC)

Thanks again, I will try whether I can figure something out. (I meant the possible 16 *binary* connectives. Without conjunction and disjunction there are 14 left.) -Cubefox (talk) 08:37, 11 September 2018 (UTC)

Look at those 16 binary connectives closely. One of those 16 just returns true all the time, and another one just returns false all the time; those are what I called $\top$ and $\bot$. A third connective just returns the value of $A$, a fourth just returns the value of $B$, and two more return their negations. Six out of the 16 binary connectives just ignore one or both of their inputs. —Bkell (talk) 12:36, 11 September 2018 (UTC)

Ah okay, got it. -Cubefox (talk) 16:04, 11 September 2018 (UTC)