Wednesday, September 20, 2017

The Probabilistic Counterexampler

Every so often someone asks me if some piece of probabilistic reasoning works. For instance, today I got a query from a grad student whether

  1. P(A|C)>P(A|B) implies P(A|B ∨ C)>P(A|B).

Of course, I could think about it each time somebody asks me something. But why think when a computer can solve a problem by brute force?

So, last spring I wrote a quick and dirty python program that looks for counterexamples to questions like that simply by considering situations with three dice, and iterating over all the possible combinations of subsets A, B and C of the state space (with some reduction due to symmetries).

The program is still quick and dirty, but at least I made the premises and conclusions not be hardcoded. You can get it here.

For instance, for the query above, you can run:

python probab-reasoning.py "P(a,c)>P(a,b)" "P(a,b|c)>P(a,b)" 

(The vertical bars are disjunction, not conditional probability. Conditional probability uses commas.) The result is:

a={1}, b={1, 2}, c={1}
a={1}, b={1, 2, 3}, c={1}
a={1}, b={1, 2, 3}, c={1, 2}
a={1}, b={1, 2, 3}, c={1, 3}
a={1}, b={1, 2, 3}, c={1, 4}
...

So, lots of counterexamples. On the other hand, you can do this:

python probab-reasoning.py "P(a)*P(b)==P(a&b)" "P(b)>0" "P(a,b)==P(a)" 

and it will tell you no counterexamples were found. Of course, that doesn’t prove that the result is true, but in this case it is.

The general operation is that you install python (either 2.7 or 3.x) and use a commandline to run:

python probab-reason.py premise1 premise2 ... conclusions

You can use any single letter variables for events, other than P, and the operations & (conjunction), | (disjunction) and ~ (negation) between the events. You can use conditional probability P(a,b) and unconditional probability P(a). You can use standard arithmetical and comparison operators on probabilities. Make sure that you use python’s operators. For instance, equality is ==, not =. You should also use python’s boolean operations when you are not working with events: e.g., “P(a)==1 and P(b)==0.5”.

Any premise or conclusion that requires conditionalization on a probability zero event to evaluate automatically counts as false.

You can use up to five single-letter variables and you can also specify the number of sides the die has prior to listing the premises. E.g.:

python probab-reasoning.py 8 "P(a)*P(b)==P(a&b)" "P(b)>0" "P(a,b)==P(a)" 

No comments: