Hex, Bugs and More Physics | Emre S. Tasci

a blog about physics, computation, computational physics and materials…

A (Lame) Proof of the Probability Sum Rule

December 21, 2007 Posted by Emre S. Tasci

Q: Prove the Probability Sum Rule, that is:

Formula: % MathType!MTEF!2!1!+-<br />
% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn<br />
% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr<br />
% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9<br />
% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x<br />
% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiuamaabm<br />
% aabaGaamOqaaGaayjkaiaawMcaaiabg2da9maaqahabaGaamiuamaa<br />
% bmaabaGaamOqaiaacYhacaWGbbGaeyypa0JaamODamaaBaaaleaaca<br />
% WGQbaabeaaaOGaayjkaiaawMcaaiaadcfadaqadaqaaiaadgeacqGH<br />
% 9aqpcaWG2bWaaSbaaSqaaiaadQgaaeqaaaGccaGLOaGaayzkaaaale<br />
% aacaWGQbGaeyypa0JaaGymaaqaaiaadUgaa0GaeyyeIuoaaaa!4E55!<br />
\[<br />
P\left( B \right) = \sum\limits_{j = 1}^k {P\left( {B|A = v_j } \right)P\left( {A = v_j } \right)} <br />
\]<br />

(where A is a random variable with arity (~dimension) k) using Axioms:

Formula: % MathType!MTEF!2!1!+-
% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr
% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9
% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x
% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaGimaiabgs
% MiJkaadcfadaqadaqaaiaadgeaaiaawIcacaGLPaaacqGHKjYOcaaI
% XaGaaiilaiaaykW7caWGqbWaaeWaaeaacaWGubGaamOCaiaadwhaca
% WGLbaacaGLOaGaayzkaaGaeyypa0JaaGymaiaacYcacaWGqbWaaeWa
% aeaacaWGgbGaamyyaiaadYgacaWGZbGaamyzaaGaayjkaiaawMcaai
% abg2da9iaaicdacaWLjaWaamWaaeaacaaIXaaacaGLBbGaayzxaaaa
% aa!549F!
\[
0 \leqslant P\left( A \right) \leqslant 1,\,P\left( {True} \right) = 1,P\left( {False} \right) = 0 & \left[ 1 \right]
\]

Formula: % MathType!MTEF!2!1!+-
% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr
% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9
% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x
% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiuamaabm
% aabaGaamyqaiabgIIiAlaadkeaaiaawIcacaGLPaaacqGH9aqpcaWG
% qbWaaeWaaeaacaWGbbaacaGLOaGaayzkaaGaey4kaSIaamiuamaabm
% aabaGaamOqaaGaayjkaiaawMcaaiabgkHiTiaadcfadaqadaqaaiaa
% dgeacqGHNis2caWGcbaacaGLOaGaayzkaaGaaCzcamaadmaabaGaaG
% OmaaGaay5waiaaw2faaaaa!4D8F!
\[
P\left( {A \vee B} \right) = P\left( A \right) + P\left( B \right) - P\left( {A \wedge B} \right) & \left[ 2 \right]
\]

and assuming:

Formula: % MathType!MTEF!2!1!+-
% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr
% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9
% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x
% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiuaiaacI
% cacaWGbbGaeyypa0JaamODamaaBaaaleaacaWGPbaabeaakiabgEIi
% zlaadgeacqGH9aqpcaWG2bWaaSbaaSqaaiaadQgaaeqaaOGaaiykai
% abg2da9maaceaabaqbaeqabiGaaaqaaiaaicdaaeaacaqGPbGaaeOz
% aiaabccacaWGPbGaeyiyIKRaamOAaaqaaiaadcfadaqadaqaaiaadg
% eacqGH9aqpcaWG2bWaaSbaaSqaaiaadMgaaeqaaaGccaGLOaGaayzk
% aaaabaGaaeyAaiaabAgacaqGGaGaamyAaiabg2da9iaadQgaaaGaaC
% zcamaadmaabaGaaG4maaGaay5waiaaw2faaaGaay5Eaaaaaa!599B!
\[
P(A = v_i \wedge A = v_j ) = \left\{ {\begin{array}{*{20}c}
0 & {{\text{if }}i \ne j} \\
{P\left( {A = v_i } \right)} & {{\text{if }}i = j} \\
\end{array} & \left[ 3 \right]} \right.
\]

Formula: % MathType!MTEF!2!1!+-
% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr
% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9
% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x
% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiuaiaacI
% cacaWGbbGaeyypa0JaamODamaaBaaaleaacaaIXaaabeaakiabgIIi
% AlaadgeacqGH9aqpcaWG2bWaaSbaaSqaaiaaikdaaeqaaOGaeyikIO
% TaaiOlaiaac6cacaGGUaGaeyikIOTaamyqaiabg2da9iaadAhadaWg
% aaWcbaGaam4AaaqabaGccaGGPaGaeyypa0JaaGymaiaaxMaacaWLja
% WaamWaaeaacaaI0aaacaGLBbGaayzxaaaaaa!5054!
\[
P(A = v_1 \vee A = v_2 \vee ... \vee A = v_k ) = 1 & & \left[ 4 \right]
\] 


 

We will first prove the following equalities to make use of them later in the actual proof:

Formula: % MathType!MTEF!2!1!+-
% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr
% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9
% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x
% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiuamaabm
% aabaGaamyqaiabg2da9iaadAhadaWgaaWcbaGaaGymaaqabaGccqGH
% OiI2caWGbbGaeyypa0JaamODamaaBaaaleaacaaIYaaabeaakiabgI
% IiAlaac6cacaGGUaGaaiOlaiabgIIiAlaadgeacqGH9aqpcaWG2bWa
% aSbaaSqaaiaadMgaaeqaaaGccaGLOaGaayzkaaGaeyypa0ZaaabCae
% aacaWGqbWaaeWaaeaacaWGbbGaeyypa0JaamODamaaBaaaleaacaWG
% QbaabeaaaOGaayjkaiaawMcaaiaaxMaadaWadaqaaiaaiwdaaiaawU
% facaGLDbaaaSqaaiaadQgacqGH9aqpcaaIXaaabaGaamyAaaqdcqGH
% ris5aaaa!5B50!
\[
P\left( {A = v_1 \vee A = v_2 \vee ... \vee A = v_i } \right) = \sum\limits_{j = 1}^i {P\left( {A = v_j } \right) & \left[ 5 \right]} \]

Formula: % MathType!MTEF!2!1!+-
% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr
% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9
% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x
% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiuamaabm
% aabaGaamOqaiabgEIizpaadmaabaGaamyqaiabg2da9iaadAhadaWg
% aaWcbaGaaGymaaqabaGccqGHOiI2caWGbbGaeyypa0JaamODamaaBa
% aaleaacaaIYaaabeaakiabgIIiAlaac6cacaGGUaGaaiOlaiabgIIi
% AlaadgeacqGH9aqpcaWG2bWaaSbaaSqaaiaadMgaaeqaaaGccaGLBb
% GaayzxaaaacaGLOaGaayzkaaGaeyypa0ZaaabCaeaacaWGqbWaaeWa
% aeaacaWGcbGaey4jIKTaamyqaiabg2da9iaadAhadaWgaaWcbaGaam
% OAaaqabaaakiaawIcacaGLPaaacaWLjaWaamWaaeaacaaI2aaacaGL
% BbGaayzxaaaaleaacaWGQbGaeyypa0JaaGymaaqaaiaadMgaa0Gaey
% yeIuoaaaa!622D!
\[
P\left( {B \wedge \left[ {A = v_1 \vee A = v_2 \vee ... \vee A = v_i } \right]} \right) = \sum\limits_{j = 1}^i {P\left( {B \wedge A = v_j } \right) & \left[ 6 \right]}
\]

Proof of [5]:

Using [2], we can write:

Formula: % MathType!MTEF!2!1!+-
% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr
% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9
% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x
% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiuamaabm
% aabaGaamyqaiabg2da9iaadAhadaWgaaWcbaGaamyAaaqabaGccqGH
% OiI2caWGbbGaeyypa0JaamODamaaBaaaleaacaWGQbaabeaaaOGaay
% jkaiaawMcaaiabg2da9iaadcfadaqadaqaaiaadgeacqGH9aqpcaWG
% 2bWaaSbaaSqaaiaadMgaaeqaaaGccaGLOaGaayzkaaGaey4kaSIaam
% iuamaabmaabaGaamyqaiabg2da9iaadAhadaWgaaWcbaGaamOAaaqa
% baaakiaawIcacaGLPaaacqGHsislcaWGqbWaaeWaaeaacaWGbbGaey
% ypa0JaamODamaaBaaaleaacaWGPbaabeaakiabgEIizlaadgeacqGH
% 9aqpcaWG2bWaaSbaaSqaaiaadQgaaeqaaaGccaGLOaGaayzkaaaaaa!5D1D!
\[
P\left( {A = v_i \vee A = v_j } \right) = P\left( {A = v_i } \right) + P\left( {A = v_j } \right) - P\left( {A = v_i \wedge A = v_j } \right)
\]

where, from the assumption [3], we have

Formula: % MathType!MTEF!2!1!+-
% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr
% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9
% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x
% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiuamaabm
% aabaGaamyqaiabg2da9iaadAhadaWgaaWcbaGaamyAaaqabaGccqGH
% OiI2caWGbbGaeyypa0JaamODamaaBaaaleaacaWGQbaabeaaaOGaay
% jkaiaawMcaaiabg2da9iaadcfadaqadaqaaiaadgeacqGH9aqpcaWG
% 2bWaaSbaaSqaaiaadMgaaeqaaaGccaGLOaGaayzkaaGaey4kaSIaam
% iuamaabmaabaGaamyqaiabg2da9iaadAhadaWgaaWcbaGaamOAaaqa
% baaakiaawIcacaGLPaaacaWLjaGaaCzcamaabmaabaGaamyAaiabgc
% Mi5kaadQgaaiaawIcacaGLPaaaaaa!56BE!
\[
P\left( {A = v_i \vee A = v_j } \right) = P\left( {A = v_i } \right) + P\left( {A = v_j } \right) & & \left( {i \ne j} \right)
\]

Using this fact, we can now expand the LHS of [5] as:

Formula: % MathType!MTEF!2!1!+-
% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr
% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9
% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x
% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGceaqabeaacaWGqb
% WaaeWaaeaacaWGbbGaeyypa0JaamODamaaBaaaleaacaaIXaaabeaa
% kiabgIIiAlaadgeacqGH9aqpcaWG2bWaaSbaaSqaaiaaikdaaeqaaO
% GaeyikIOTaaiOlaiaac6cacaGGUaGaeyikIOTaamyqaiabg2da9iaa
% dAhadaWgaaWcbaGaamyAaaqabaaakiaawIcacaGLPaaacqGH9aqpca
% WGqbWaaeWaaeaacaWGbbGaeyypa0JaamODamaaBaaaleaacaaIXaaa
% beaaaOGaayjkaiaawMcaaiabgUcaRiaadcfadaqadaqaaiaadgeacq
% GH9aqpcaWG2bWaaSbaaSqaaiaaikdaaeqaaaGccaGLOaGaayzkaaGa
% ey4kaSIaaiOlaiaac6cacaGGUaGaey4kaSIaamiuamaabmaabaGaam
% yqaiabg2da9iaadAhadaWgaaWcbaGaamyAaaqabaaakiaawIcacaGL
% PaaaaeaacqGH9aqpdaaeWbqaaiaadcfadaqadaqaaiaadgeacqGH9a
% qpcaWG2bWaaSbaaSqaaiaadQgaaeqaaaGccaGLOaGaayzkaaaaleaa
% caWGQbGaeyypa0JaaGymaaqaaiaadMgaa0GaeyyeIuoaaaaa!703C!
\[
\begin{gathered}
P\left( {A = v_1 \vee A = v_2 \vee ... \vee A = v_i } \right) = P\left( {A = v_1 } \right) + P\left( {A = v_2 } \right) + ... + P\left( {A = v_i } \right) \hfill \\
= \sum\limits_{j = 1}^i {P\left( {A = v_j } \right)} \hfill \\
\end{gathered}
\]

Proof of [6]:

Using the distribution property, we can write the LHS of [6] as:

Formula: % MathType!MTEF!2!1!+-
% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr
% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9
% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x
% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGceaqabeaacaWGqb
% WaaeWaaeaacaWGcbGaey4jIK9aamWaaeaacaWGbbGaeyypa0JaamOD
% amaaBaaaleaacaaIXaaabeaakiabgIIiAlaadgeacqGH9aqpcaWG2b
% WaaSbaaSqaaiaaikdaaeqaaOGaeyikIOTaaiOlaiaac6cacaGGUaGa
% eyikIOTaamyqaiabg2da9iaadAhadaWgaaWcbaGaamyAaaqabaaaki
% aawUfacaGLDbaaaiaawIcacaGLPaaaaeaacqGH9aqpcaWGqbWaaeWa
% aeaadaWadaqaaiaadkeacqGHNis2caWGbbGaeyypa0JaamODamaaBa
% aaleaacaaIXaaabeaaaOGaay5waiaaw2faaiabgIIiApaadmaabaGa
% amOqaiabgEIizlaadgeacqGH9aqpcaWG2bWaaSbaaSqaaiaaikdaae
% qaaaGccaGLBbGaayzxaaGaeyikIOTaaiOlaiaac6cacaGGUaGaeyik
% IO9aamWaaeaacaWGcbGaey4jIKTaamyqaiabg2da9iaadAhadaWgaa
% WcbaGaamyAaaqabaaakiaawUfacaGLDbaaaiaawIcacaGLPaaaaaaa
% !7256!
\[
\begin{gathered}
P\left( {B \wedge \left[ {A = v_1 \vee A = v_2 \vee ... \vee A = v_i } \right]} \right) \hfill \\
= P\left( {\left[ {B \wedge A = v_1 } \right] \vee \left[ {B \wedge A = v_2 } \right] \vee ... \vee \left[ {B \wedge A = v_i } \right]} \right) \hfill \\
\end{gathered}
\]

from [2], it is obvious that:

Formula: % MathType!MTEF!2!1!+-
% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr
% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9
% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x
% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGceaqabeaacaWGqb
% WaaeWaaeaadaWadaqaaiaadkeacqGHNis2caWGbbGaeyypa0JaamOD
% amaaBaaaleaacaWGPbaabeaaaOGaay5waiaaw2faaiabgIIiApaadm
% aabaGaamOqaiabgEIizlaadgeacqGH9aqpcaWG2bWaaSbaaSqaaiaa
% dQgaaeqaaaGccaGLBbGaayzxaaaacaGLOaGaayzkaaaabaGaeyypa0
% JaamiuaiaacIcacaWGcbGaey4jIKTaamyqaiabg2da9iaadAhadaWg
% aaWcbaGaamyAaaqabaGccaGGPaGaey4kaSIaamiuaiaacIcacaWGcb
% Gaey4jIKTaamyqaiabg2da9iaadAhadaWgaaWcbaGaamOAaaqabaGc
% caGGPaGaeyOeI0YaaGbaaeaacaWGqbWaaeWaaeaadaWadaqaaiaadk
% eacqGHNis2caWGbbGaeyypa0JaamODamaaBaaaleaacaWGPbaabeaa
% aOGaay5waiaaw2faaiabgEIizpaadmaabaGaamOqaiabgEIizlaadg
% eacqGH9aqpcaWG2bWaaSbaaSqaaiaadQgaaeqaaaGccaGLBbGaayzx
% aaaacaGLOaGaayzkaaaaleaacaaIWaGaaGPaVpaabmaabaGaamyAai
% abgcMi5kaadQgaaiaawIcacaGLPaaaaOGaayjo+daabaGaeyypa0Ja
% amiuaiaacIcacaWGcbGaey4jIKTaamyqaiabg2da9iaadAhadaWgaa
% WcbaGaamyAaaqabaGccaGGPaGaey4kaSIaamiuaiaacIcacaWGcbGa
% ey4jIKTaamyqaiabg2da9iaadAhadaWgaaWcbaGaamOAaaqabaGcca
% GGPaaaaaa!8FC2!
\[
\begin{gathered}
P\left( {\left[ {B \wedge A = v_i } \right] \vee \left[ {B \wedge A = v_j } \right]} \right) \hfill \\
= P(B \wedge A = v_i ) + P(B \wedge A = v_j ) - \underbrace {P\left( {\left[ {B \wedge A = v_i } \right] \wedge \left[ {B \wedge A = v_j } \right]} \right)}_{0\,\left( {i \ne j} \right)} \hfill \\
= P(B \wedge A = v_i ) + P(B \wedge A = v_j ) \hfill \\
\end{gathered}
\]

then using [5], we can rearrange and rewrite the LHS of [6] as:

Formula: % MathType!MTEF!2!1!+-
% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr
% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9
% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x
% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGceaqabeaacaWGqb
% WaaeWaaeaacaWGcbGaey4jIK9aamWaaeaacaWGbbGaeyypa0JaamOD
% amaaBaaaleaacaaIXaaabeaakiabgIIiAlaadgeacqGH9aqpcaWG2b
% WaaSbaaSqaaiaaikdaaeqaaOGaeyikIOTaaiOlaiaac6cacaGGUaGa
% eyikIOTaamyqaiabg2da9iaadAhadaWgaaWcbaGaamyAaaqabaaaki
% aawUfacaGLDbaaaiaawIcacaGLPaaaaeaacqGH9aqpcaWGqbGaaiik
% aiaadkeacqGHNis2caWGbbGaeyypa0JaamODamaaBaaaleaacaaIXa
% aabeaakiaacMcacqGHRaWkcaWGqbGaaiikaiaadkeacqGHNis2caWG
% bbGaeyypa0JaamODamaaBaaaleaacaaIYaaabeaakiaacMcacqGHRa
% WkcaGGUaGaaiOlaiaac6cacqGHRaWkcaWGqbGaaiikaiaadkeacqGH
% Nis2caWGbbGaeyypa0JaamODamaaBaaaleaacaWGPbaabeaakiaacM
% caaeaacqGH9aqpdaaeWbqaaiaadcfadaqadaqaaiaadkeacqGHNis2
% caWGbbGaeyypa0JaamODamaaBaaaleaacaWGQbaabeaaaOGaayjkai
% aawMcaaaWcbaGaamOAaiabg2da9iaaigdaaeaacaWGPbaaniabggHi
% Ldaaaaa!7DE8!
\[
\begin{gathered}
P\left( {B \wedge \left[ {A = v_1 \vee A = v_2 \vee ... \vee A = v_i } \right]} \right) \hfill \\
= P(B \wedge A = v_1 ) + P(B \wedge A = v_2 ) + ... + P(B \wedge A = v_i ) \hfill \\
= \sum\limits_{j = 1}^i {P\left( {B \wedge A = v_j } \right)} \hfill \\
\end{gathered}
\]

Final Proof :

Before proceeding, I will include two assumptions about the Universal Set (this part is the main reason for the proof to be lame by the way).

Define the universal set U as the set that includes all possible values of some random variable X. All the other sets are subsets of U and for an arbitrary set A, we assume that:

Formula: % MathType!MTEF!2!1!+-
% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr
% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9
% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x
% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGceaqabeaacaWGbb
% Gaey4jIKTaamyvaiabg2da9iaadgeaaeaacaWGbbGaeyikIOTaamyv
% aiabg2da9iaadwfaaaaa!403E!
\[
\begin{gathered}
A \wedge U = A \hfill \\
A \vee U = U \hfill \\
\end{gathered}
\]

Furthermore, we will be assuming that, a condition that includes all the possible outcomes(/values) for a variable A is equivalent to the universal set. Let A have arity k, then:

Formula: % MathType!MTEF!2!1!+-
% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr
% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9
% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x
% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGceaqabeaadaqada
% qaaiaadohacaWGVbGaamyBaiaadwgacaaMc8Uaam4yaiaad+gacaWG
% UbGaamizaiaadMgacaWG0bGaamyAaiaad+gacaWGUbGaaGPaVlaadI
% facqGHNis2daagaaqaamaadmaabaGaamyqaiabg2da9iaadAhadaWg
% aaWcbaGaaGymaaqabaGccqGHOiI2caWGbbGaeyypa0JaamODamaaBa
% aaleaacaaIYaaabeaakiabgIIiAlaac6cacaGGUaGaaiOlaiabgIIi
% AlaadgeacqGH9aqpcaWG2bWaaSbaaSqaaiaadUgaaeqaaaGccaGLBb
% GaayzxaaaaleaacaWGvbaakiaawIJ-aaGaayjkaiaawMcaaaqaaiab
% g2da9maabmaabaGaam4Caiaad+gacaWGTbGaamyzaiaaykW7caWGJb
% Gaam4Baiaad6gacaWGKbGaamyAaiaadshacaWGPbGaam4Baiaad6ga
% caaMc8UaamiwaaGaayjkaiaawMcaaaqaamaabmaabaGaam4Caiaad+
% gacaWGTbGaamyzaiaaykW7caWGJbGaam4Baiaad6gacaWGKbGaamyA
% aiaadshacaWGPbGaam4Baiaad6gacaaMc8UaamiwaiabgIIiApaaya
% aabaWaamWaaeaacaWGbbGaeyypa0JaamODamaaBaaaleaacaaIXaaa
% beaakiabgIIiAlaadgeacqGH9aqpcaWG2bWaaSbaaSqaaiaaikdaae
% qaaOGaeyikIOTaaiOlaiaac6cacaGGUaGaeyikIOTaamyqaiabg2da
% 9iaadAhadaWgaaWcbaGaam4AaaqabaaakiaawUfacaGLDbaaaSqaai
% aadwfaaOGaayjo+daacaGLOaGaayzkaaaabaGaeyypa0ZaaeWaaeaa
% caWGvbaacaGLOaGaayzkaaaaaaa!A18B!
\[
\begin{gathered}
\left( {some\,condition\,X \wedge \underbrace {\left[ {A = v_1 \vee A = v_2 \vee ... \vee A = v_k } \right]}_U} \right) \hfill \\
= \left( {some\,condition\,X} \right) \hfill \\
\left( {some\,condition\,X \vee \underbrace {\left[ {A = v_1 \vee A = v_2 \vee ... \vee A = v_k } \right]}_U} \right) \hfill \\
= \left( U \right) \hfill \\
\end{gathered}
\]

You can think of the condition (U) as the definite TRUE 1.

Now we can begin the proof of the equality

Formula: % MathType!MTEF!2!1!+-<br />
% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn<br />
% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr<br />
% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9<br />
% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x<br />
% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiuamaabm<br />
% aabaGaamOqaaGaayjkaiaawMcaaiabg2da9maaqahabaGaamiuamaa<br />
% bmaabaGaamOqaiaacYhacaWGbbGaeyypa0JaamODamaaBaaaleaaca<br />
% WGQbaabeaaaOGaayjkaiaawMcaaiaadcfadaqadaqaaiaadgeacqGH<br />
% 9aqpcaWG2bWaaSbaaSqaaiaadQgaaeqaaaGccaGLOaGaayzkaaaale<br />
% aacaWGQbGaeyypa0JaaGymaaqaaiaadUgaa0GaeyyeIuoaaaa!4E55!<br />
\[<br />
P\left( B \right) = \sum\limits_{j = 1}^k {P\left( {B|A = v_j } \right)P\left( {A = v_j } \right)} <br />
\]<br />

using the Bayes Rule

Formula: % MathType!MTEF!2!1!+-
% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr
% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9
% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x
% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiuamaabm
% aabaGaamyqaiaacYhacaWGcbaacaGLOaGaayzkaaGaeyypa0ZaaSaa
% aeaacaWGqbWaaeWaaeaacaWGbbGaey4jIKTaamOqaaGaayjkaiaawM
% caaaqaaiaadcfadaqadaqaaiaadkeaaiaawIcacaGLPaaaaaaaaa!44AC!
\[
P\left( {A|B} \right) = \frac{{P\left( {A \wedge B} \right)}}
{{P\left( B \right)}}
\]

we can convert the inference relation into intersection relation and rewrite RHS as:

Formula: % MathType!MTEF!2!1!+-
% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr
% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9
% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x
% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGceaqabeaadaaeWb
% qaamaalaaabaGaamiuamaabmaabaGaamOqaiabgEIizlaadgeacqGH
% 9aqpcaWG2bWaaSbaaSqaaiaadQgaaeqaaaGccaGLOaGaayzkaaaaba
% GaamiuamaabmaabaGaamyqaiabg2da9iaadAhadaWgaaWcbaGaamOA
% aaqabaaakiaawIcacaGLPaaaaaGaamiuamaabmaabaGaamyqaiabg2
% da9iaadAhadaWgaaWcbaGaamOAaaqabaaakiaawIcacaGLPaaaaSqa
% aiaadQgacqGH9aqpcaaIXaaabaGaam4AaaqdcqGHris5aaGcbaGaey
% ypa0ZaaabCaeaacaWGqbWaaeWaaeaacaWGcbGaey4jIKTaamyqaiab
% g2da9iaadAhadaWgaaWcbaGaamOAaaqabaaakiaawIcacaGLPaaaaS
% qaaiaadQgacqGH9aqpcaaIXaaabaGaam4AaaqdcqGHris5aaaaaa!60EA!
\[
\begin{gathered}
\sum\limits_{j = 1}^k {\frac{{P\left( {B \wedge A = v_j } \right)}}
{{P\left( {A = v_j } \right)}}P\left( {A = v_j } \right)} \hfill \\
= \sum\limits_{j = 1}^k {P\left( {B \wedge A = v_j } \right)} \hfill \\
\end{gathered}
\]

using [6], this is nothing but:

Formula: % MathType!MTEF!2!1!+-
% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr
% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9
% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x
% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGceaqabeaacaWGqb
% WaaeWaaeaacaWGcbGaey4jIK9aaGbaaeaadaWadaqaaiaadgeacqGH
% 9aqpcaWG2bWaaSbaaSqaaiaaigdaaeqaaOGaeyikIOTaamyqaiabg2
% da9iaadAhadaWgaaWcbaGaaGOmaaqabaGccqGHOiI2caGGUaGaaiOl
% aiaac6cacqGHOiI2caWGbbGaeyypa0JaamODamaaBaaaleaacaWGRb
% aabeaaaOGaay5waiaaw2faaaWcbaGaamyvaaGccaGL44paaiaawIca
% caGLPaaaaeaacqGH9aqpcaWGqbWaaeWaaeaacaWGcbaacaGLOaGaay
% zkaaaaaaa!5642!
\[
\begin{gathered}
P\left( {B \wedge \underbrace {\left[ {A = v_1 \vee A = v_2 \vee ... \vee A = v_k } \right]}_U} \right) \hfill \\
= P\left( B \right) \hfill \\
\end{gathered}
\]

Leave a Reply