Reanimator Ltd

High-performance coding by Eddie Edwards

When Is This Expression True?

15 Nov 2013, 13:14 UTC

Probability theory can be confusing sometimes. I think this confusion comes from a belief that one has intuitive insight into how it works, when one really doesn't. Counter-intuitive results abound. But worse is results that seem "obvious" but which are only true in some cases.

A good example is the following expression, which I simply wrote down one night because it was "obvious":

p(A|C) = p(A|B)p(B|C) + p(A|!B)p(!B|C)

Being a good boy, I decided not to use this expression before I proved it. I failed to prove it. I pushed symbols around for an hour and got nowhere. So I posted about it on Facebook and got no less than six mathematicians involved (five of them Cambridge graduates; one of them even a Cambridge PhD!) And we were all fairly stumped!

I promised those guys (Dave C, Dave H, Graham, Cedrick, Willem) I'd write up the conclusions, so here you are.


A, B and C are boolean-valued random variables. Since they are boolean-valued we can draw them using a Venn diagram. (This turns out not to help very much.)

We can also write a truth table for A,B,C as follows, and label the primal probabilities:

A B C p
0 0 0 a
0 0 1 b
0 1 0 c
0 1 1 d
1 0 0 e
1 0 1 f
1 1 0 g
1 1 1 h

So p(A&B&C)=h, p(!A&!B&!C)=a, etc.

And a quick recap of conditional probabilities: by definition,

p(A|B) = p(A&B)/p(B)

Easy examples and counterexamples

In the Venn diagram, if A is enclosed in B, then p(A|!B) = 0, so the expression reduces to

p(A|C) = p(A|B)p(B|C)

If B is also enclosed in C then this represents an algebraic truth about the ratios of the areas in the Venn diagram. Area(A)/Area(C) = Area(A)/Area(B) * Area(B)/Area(C).

So A in B in C, equivalently p(A|!B) = p(B|!C) = 0, is an example where the expression definitely works. Unfortunately not much else can be deduced just by looking at the Venn diagram (C in B in A also works, by similar logic).

But the expression certainly does not always hold. A counterexample is if B and C are independent, that is, p(B|C) = p(B) and p(!B|C) = p(!B). Then the expression reduces to:

p(A|C) = p(A|B)p(B|C) + p(A|!B)p(!B|C)
       = p(A|B)p(B) + p(A|!B)p(!B)
       = p(A&B) + p(A&!B)
       = p(A)

But this states that A and C are independent. Since this does not hold in general, the expression fails to work in this case.

General constraint

Dave H managed to do some algebraic gymnastics on the full expression, using the primal truth table probabilities. This goes something like this:

p(A|C) = (f+h)/(b+d+f+h)
p(A|B) = (g+h)/(c+d+g+h)
p(A|!B) = (e+f)/(a+b+e+f)
p(B|C) = (d+g)/(b+d+f+h)
p(!B|C) = (b+f)/(b+d+f+h)

Expression is therefore:
(f+h)/(b+d+f+h) = (g+h)/(c+d+g+h).(d+g)/(b+d+f+h) + (e+f)/(a+b+e+f).(b+f)/(b+d+f+h)

Cancel b+d+f+h on both sides and raise denominators:
(f+h)(c+d+g+h)(a+b+e+f) = (g+h)(d+h)(a+b+e+f) + (e+f)(b+f)(c+d+g+h)

Combine products of (a+b+e+f):
0 = [(g+h)(d+g) - (f+g)(c+d+g+h)](a+b+e+f) + (e+f)(b+f)(c+d+g+h)
  = [gd+hd+gg+hg - fc-fd-fg-fh-gc-gd-gg-gh](a+b+e+f) + (e+f)(b+f)(c+d+g+h)
  = [gd-hc - f(c+d+g+h)](a+b+e+f) + (e+f)(b+f)(c+d+g+h)

Combine products of (c+d+g+h):
0 = (gd-hc)(a+b+e+f) + [(e+f)(b+f) - f(a+b+e+f)](c+d+g+h)
  = (gd-hc)(a+b+e+f) + [eb+fb+ef+ff - fa-fb-fe-ff](c+d+g+h)
  = (gd-hc)(a+b+e+f) + (eb-fa)(c+d+g+h)

(gd-hc)/(c+d+g+h) = (fa-eb)/(a+b+e+f)

We can replace symbols as follows:

p(A&B&!C)p(!A&B&C) - p(A&B&C)p(!A&B&!C)   p(!A&!B&!C)p(A&!B&C) - p(!A&!B&C)p(A&!B&!C)
--------------------------------------- = -------------------------------------------
                  p(B)                                       p(!B)

This is also equivalent to:

p(A&!C|B)p(!A&C|B) - p(A&C|B)p(!A&!C|B) = p(!A&!C|!B)p(A&C|!B) - p(!A&C|!B)p(A&!C|!B)

It should be noted that if you exchange A<->!A, B<->!B and/or C<->!C then the expression remains unchanged (except for a possible change of sign). This implies that the original expression holds not only for p(A|C) but also p(A|!C), p(!A|C) and p(!A|!C) (by exchanging variables with their negations). This is what we would hope/expect.

Now what?

What does this constraint mean? It seems like some kind of residual, conditional on B, has to be equal to some kind of residual, conditional on !B. The residual appears to be some kind of cross-product term. If we consider (a,b) and (e,f) as vectors, the residual will be zero if those vectors are parallel (i.e. e = k.a and f = k.b for some constant k), and our expression will hold. If those vectors are non-parallel, then things are trickier if we want our expression to hold.

For the case where residual is zero we can introduce constants k and m, set e=ka, f=kb, g=mc,h=md, and the truth table is:

A B C p
0 0 0 a
0 0 1 b
0 1 0 c
0 1 1 d
1 0 0 ka
1 0 1 kb
1 1 0 mc
1 1 1 md

Keeping in mind that we must have (ka+kb+mc+md) = 1-(a+b+c+d) we get that:

(k+1)(a+b) + (m+1)(c+d) = 1
=> m = [1 - (k+1)(a+b)]/(c+d) - 1

So that, given a,b,c,d and k, m is already determined.

Transition Matrix Solution

Another way to get a solution with residual zero is as follows:

A B C p
0 0 0 (1-x)ac
0 0 1 x(1-b)c
0 1 0 (1-x)(1-a)(1-d)
0 1 1 xb(1-d)
1 0 0 (1-x)a(1-c)
1 0 1 x(1-b)(1-c)
1 1 0 (1-x)(1-a)d
1 1 1 xbd

This table sums to 1 by construction, and has (a,b) || (e,f) and (c,d) || (g,h) also by construction.

These figures represent a process whereby C is picked at random (p(C) = x, p(!C) = 1-x), then B copies C, possibly incorrectly:

p(!B|!C) = a (true negative)
p(B|!C) = (1-a) (false positive)
p(!B|C) = (1-b) (false negative)
p(B|C) = b (true positive)

then A copies B, possibly incorrectly:

p(!A|!B) = c (true negative)
p(A|!B) = (1-c) (false positive)
p(!A|B) = (1-d) (false negative)
p(A|B) = d (true positive)

The process of picking C is independent of the process for adding errors to B is independent of the process for adding errors to A. The truth table above is the final result, and it can be verified that it obeys the original expression.

Family of Other Solutions

So we've pretty much covered all the solutions with zero residual. This family of solutions corresponds to A being related to B via a transition matrix, and B related to C via a transition matrix. Then the original expression (plus its permutations) says that A is related to C by the product of the two transition matrices.

If we set the transition matrices to special cases we retrieve the easy geometric cases "A in B in C" (no false positives, some false negatives) and "C in B in A" (no false negatives, some false positives).

But ... our solution has 5 degrees of freedom (DOF). The full truth table has 7DOF (eight variables which must sum to exactly 1). The constraint Dave H worked out reduces this to 6DOF. But out solution has one DOF fewer because we force the residual to be zero.

There is therefore an entire 6DOF family of solutions with non-zero residual. But it's not clear if this family is a large set of coincidences, or if it has a meaningful interpretation.

Over to you, the reader ...

Please log in if you wish to edit or delete comments you make.

Formatting help & Commenting policy

The only thing keeping my cat from eating me is the dicnfreefe in our respective sizes and the fact that I feed her on a regular basis. We both know that if either of those changes, all bets are off. commented:

The only thing keeping my cat from eating me is the dicnfreefe in our respective sizes and the fact that I feed her on a regular basis. We both know that if either of those changes, all bets are off.

on 18 Oct 2016, 12:29 UTC

Boy that <a href="">rellay</a> helps me the heck out. commented:

Boy that <a href="">rellay</a> helps me the heck out.

on 19 Oct 2016, 17:41 UTC

Unlreaplelad accuracy, unequivocal clarity, and undeniable importance! [url=]vnzmdgnx[/url] [link=]jbfzgkgne[/link] commented:

Unlreaplelad accuracy, unequivocal clarity, and undeniable importance! []vnzmdgnx[/url] [link=]jbfzgkgne[/link]

on 19 Oct 2016, 23:57 UTC

I'm not <a href="">worhty</a> to be in the same forum. ROTFL commented:

I'm not <a href="">worhty</a> to be in the same forum. ROTFL

on 22 Oct 2016, 05:45 UTC

You've got to be kidding me-it's so tralnparentsy clear now! [url=]adayejv[/url] [link=]adapev[/link] commented:

You've got to be kidding me-it's so tralnparentsy clear now! []adayejv[/url] [link=]adapev[/link]

on 24 Oct 2016, 20:54 UTC

JKf77A commented:


on 02 Jan 2017, 08:44 UTC

smcupw <a href="">njdryadlhbxp</a>, [url=]qpwjichnjemi[/url], [link=]tzbaqthvbqxt[/link], commented:

smcupw <a href="">njdryadlhbxp</a>, []qpwjichnjemi[/url], []tzbaqthvbqxt[/link],

on 10 Jan 2017, 12:18 UTC

90VtlI <a href="">qsibjadcoqkn</a>, [url=]wmvgneiebrgn[/url], [link=]dyxymuydqths[/link], commented:

90VtlI <a href="">qsibjadcoqkn</a>, []wmvgneiebrgn[/url], []dyxymuydqths[/link],

on 10 Jan 2017, 12:18 UTC

2fweoR <a href="">vfrmjhuevfzw</a>, [url=]dofzugthmdid[/url], [link=]nhhujxpyvfge[/link], commented:

2fweoR <a href="">vfrmjhuevfzw</a>, []dofzugthmdid[/url], []nhhujxpyvfge[/link],

on 10 Jan 2017, 14:45 UTC

1ZtbfW <a href="">sayuhopketfn</a>, [url=]bdikpwfstxhw[/url], [link=]rqqrsdgsidlx[/link], commented:

1ZtbfW <a href="">sayuhopketfn</a>, []bdikpwfstxhw[/url], []rqqrsdgsidlx[/link],

on 10 Jan 2017, 17:09 UTC

I5Bnaq <a href="">liqfsreunswj</a>, [url=]zbdxswqhbzvc[/url], [link=]tycybojpugnp[/link], commented:

I5Bnaq <a href="">liqfsreunswj</a>, []zbdxswqhbzvc[/url], []tycybojpugnp[/link],

on 10 Jan 2017, 20:36 UTC

RV0m91 <a href="">kkpaswqtigzp</a>, [url=]qlzlrggevryf[/url], [link=]wrkepgtgwkjx[/link], commented:

RV0m91 <a href="">kkpaswqtigzp</a>, []qlzlrggevryf[/url], []wrkepgtgwkjx[/link],

on 11 Jan 2017, 05:21 UTC

3dUkIo <a href="">nxfnucaowvdz</a>, [url=]vqgmblwwjbli[/url], [link=]eleqnqjjwbwg[/link], commented:

3dUkIo <a href="">nxfnucaowvdz</a>, []vqgmblwwjbli[/url], []eleqnqjjwbwg[/link],

on 11 Jan 2017, 07:41 UTC

dzRRPP <a href="">xdxwymudinwf</a>, [url=]excfgmjpianw[/url], [link=]akyniokpqvaz[/link], commented:

dzRRPP <a href="">xdxwymudinwf</a>, []excfgmjpianw[/url], []akyniokpqvaz[/link],

on 11 Jan 2017, 08:35 UTC

nv9Ox1 <a href="">mtodjpdeisdr</a>, [url=]mtrztxzsesax[/url], [link=]mpsbpdhjnqmu[/link], commented:

nv9Ox1 <a href="">mtodjpdeisdr</a>, []mtrztxzsesax[/url], []mpsbpdhjnqmu[/link],

on 11 Jan 2017, 10:02 UTC

KNtVJW <a href="">ydeemnwwozah</a>, [url=]accodpaogbuw[/url], [link=]uafzvylsxiso[/link], commented:

KNtVJW <a href="">ydeemnwwozah</a>, []accodpaogbuw[/url], []uafzvylsxiso[/link],

on 23 Jan 2017, 16:08 UTC

bOuXRU <a href="">tcternuommum</a>, [url=]yklhbelpnoyv[/url], [link=]vflzcfgmliho[/link], commented:

bOuXRU <a href="">tcternuommum</a>, []yklhbelpnoyv[/url], []vflzcfgmliho[/link],

on 23 Jan 2017, 18:31 UTC

YdOSaq <a href="">qtzvffazkkmy</a>, [url=]ohjjejrdbgug[/url], [link=]olfnnztrjiot[/link], commented:

YdOSaq <a href="">qtzvffazkkmy</a>, []ohjjejrdbgug[/url], []olfnnztrjiot[/link],

on 23 Jan 2017, 20:49 UTC

R4EAFz <a href="">kceeavusllzi</a>, [url=]dqghzsmdquhs[/url], [link=]fkxieblqaxnr[/link], commented:

R4EAFz <a href="">kceeavusllzi</a>, []dqghzsmdquhs[/url], []fkxieblqaxnr[/link],

on 23 Jan 2017, 23:16 UTC

6GoEIR <a href="">avjsgtarlrmd</a>, [url=]mmtxfsnzidzi[/url], [link=]qttyejmsfqov[/link], commented:

6GoEIR <a href="">avjsgtarlrmd</a>, []mmtxfsnzidzi[/url], []qttyejmsfqov[/link],

on 24 Jan 2017, 01:40 UTC

IVxdTD <a href="">lcfbobmxrqxa</a>, [url=]dxwmywdeecdx[/url], [link=]wnhqqzerlput[/link], commented:

IVxdTD <a href="">lcfbobmxrqxa</a>, []dxwmywdeecdx[/url], []wnhqqzerlput[/link],

on 24 Jan 2017, 04:09 UTC

x3Qf1W <a href="">piazbftkshye</a>, [url=]hqheeqxxmgwv[/url], [link=]dpawzxqwiwhz[/link], commented:

x3Qf1W <a href="">piazbftkshye</a>, []hqheeqxxmgwv[/url], []dpawzxqwiwhz[/link],

on 24 Jan 2017, 07:22 UTC

P4EKIJ <a href="">yitolhmulnxu</a>, [url=]paogymdmpveb[/url], [link=]jkwbcmokiuyj[/link], commented:

P4EKIJ <a href="">yitolhmulnxu</a>, []paogymdmpveb[/url], []jkwbcmokiuyj[/link],

on 24 Jan 2017, 09:51 UTC

knf1nF <a href="">ywmzjnlwodvc</a>, [url=]lldppgckogck[/url], [link=]tdazavmkytjc[/link], commented:

knf1nF <a href="">ywmzjnlwodvc</a>, []lldppgckogck[/url], []tdazavmkytjc[/link],

on 24 Jan 2017, 12:32 UTC

hu7q7Q <a href="">zljsekhrxxbq</a>, [url=]ubfemmjjktzq[/url], [link=]zqnjaialorsa[/link], commented:

hu7q7Q <a href="">zljsekhrxxbq</a>, []ubfemmjjktzq[/url], []zqnjaialorsa[/link],

on 25 Jan 2017, 16:00 UTC

GFB9iK <a href="">pgcetdeileui</a>, [url=]qpwhzumtvxqg[/url], [link=]ztwlfgbhwyix[/link], commented:

GFB9iK <a href="">pgcetdeileui</a>, []qpwhzumtvxqg[/url], []ztwlfgbhwyix[/link],

on 28 Jan 2017, 21:06 UTC

DRxVxn commented:


on 29 Jan 2017, 15:19 UTC

5I1d6u commented:


on 29 Jan 2017, 15:21 UTC

v6Kn5d commented:


on 31 Jan 2017, 17:39 UTC

bbqodw <a href="">yrzrjmtmbkmd</a>, [url=]renejeomohva[/url], [link=]nmglyeqopzxm[/link], commented:

bbqodw <a href="">yrzrjmtmbkmd</a>, []renejeomohva[/url], []nmglyeqopzxm[/link],

on 01 Feb 2017, 21:13 UTC