4
$\begingroup$

This question is related to some undergraduate research on summary generation of documents of which I am a part of. I am trying to estimate $P(A_1|A_2 \cup A_3 \cup A_4...A_k)$, where I know the values $P(A_i|A_j)\ \forall i,j \in\{1,2,...,n\}$. I understand that it is not possible to evaluate this probability exactly. Are there methods that relate to the approximation of such an expression under certain assumptions? Eg: Assuming event $A_2,A_3$ are independent. I would be glad if someone could point me to such resources. (webpages,books,papers,etc)

$\endgroup$
  • $\begingroup$ Do you also know the probabilities of $P(A_i)$ individually? $\endgroup$ – owen88 Jan 20 '18 at 9:07
  • $\begingroup$ No, I do not. If I did, then you get a formula for $P(A|B_1\cup B_2...\cup B_k)$ and the problem is trivial. $\endgroup$ – bat_of_doom Jan 20 '18 at 13:15
  • $\begingroup$ For a fixed $j$, how many $P(A_j|A_i)$ are non zero ? Your approach might still work if the underlying linear system is very sparse. $\endgroup$ – yultan Jan 20 '18 at 15:28
  • $\begingroup$ Ah sorry, that approach was nonsense. $A_i$s are not disjoint! $\endgroup$ – bat_of_doom Jan 20 '18 at 15:42
0
$\begingroup$

Hm... maybe we reduce the problem to: $$ Pr(A_{1}|A_{2}\cup A_{3}\cup...)=\frac{Pr(A_{1}\cap (A_{2}\cup A_{3}\cup...))}{Pr(A_{2}\cup A_{3}\cup...)} $$ Which is then... $$ Pr(A_{1}|A_{2}\cup A_{3}\cup...)=\frac{Pr((A_{1}\cap A_{2})\cup (A_{1}\cap A_{3})\cup (A_{1}\cap A_{4})...))}{Pr(A_{2}\cup A_{3}\cup...)} $$ And if... $$ Pr(A_{2}\cup A_{3}\cup...)\approx 1 $$ then... $$ Pr(A_{1}|A_{2}\cup A_{3}\cup...)\approx\Pr((A_{1}\cap A_{2})\cup (A_{1}\cap A_{3})\cup (A_{1}\cap A_{4})...)) $$ Which really depends on the mutual information (i.e. overlap in the venn diagram) between $A_{1}$ and the other events.

$\endgroup$
  • $\begingroup$ The assumption $Pr(A_2\cup A_3...)=1$ won't work in my case. Plus, the final expression you gave is not really much of a reduction to an expression using just $Pr(A_i|A_j)$. I understand that evaluating this expression exactly without more information is not possible. But I need a reasonable estimate. $\endgroup$ – bat_of_doom Jan 20 '18 at 16:10
  • $\begingroup$ Right, yeah I thought it wasn't much, but I think you need more information for any more significant improvements in simplification. I mean if we had independence between events or mutual exclusivity this would help. But assuming either doesn't make sense given the problem formulation. $\endgroup$ – Campbell Jan 20 '18 at 17:45
0
$\begingroup$

Maybe the principle of inclusion-exclusion

https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle?wprov=sfla1

or the Bonferroni inequalites

https://en.wikipedia.org/wiki/Boole%27s_inequality?wprov=sfla1

can help you to establish a connection between the expression and the set of given conditional probabilities.

$\endgroup$
  • $\begingroup$ These inequalities are interesting, but the answer is not complete. Please also add how do I use the Bonferroni inequalities for k>2, as I only know P(A|B). For k=2, I suppose I could implement an approximation for $P(A_i)$ within the program, and then the Bonferroni bound for k=2 is straightforward. $\endgroup$ – bat_of_doom Jan 24 '18 at 8:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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