Thursday, August 16, 2018

Probability and Boolean Logic

To understand probability, it is helpful to understand boolean logic. In this post, I will review both and show the connections. This is a first draft of the explanation I have in mind. I welcome suggestions to improve the presentation of these ideas.

A probability is a real number between 0 and 1 inclusive. This number represents uncertain knowledge of an outcome. The sum of the probabilities of all possible outcomes of an event is 1.

A classic example is the event of flipping of a coin. There are two possible outcomes: heads and tails. Without performing any experiments, we would estimate the probability of heads as 0.5 and tails as 0.5.

Boolean logic relies on variables that have two possible values (true/false and 1/0 are the most popular; we'll rely on true/false for the rest of this post). These variables can be combined and manipulated using the andor, and not operators. The not operator has one argument, and returns true if the argument is false and false if the argument is true. The and operator has two arguments, returning true if they are both true and false otherwise. The or operator has two arguments, returning false if they are both false and true otherwise.

We can extend boolean logic to reason about probabilities. We will give arithmetic definitions of the three boolean operators for use with probabilities:
  • x and y -> x * y (multiplication)
  • x or y -> x + y (addition)
  • not x -> -x (negation)
So if we do two coin tosses, the probability of getting heads twice is:
  • heads and heads
  • 0.5 * 0.5
  • 0.25
The same reasoning applies to getting tails twice, yielding the same probability (0.25). The probability of getting either heads twice or tails twice is:
  • heads and heads or tails and tails
  • 0.25 + 0.25
  • 0.5
Let's extend this line of reasoning to another example: the rolling of a six-sided die. I'll use fractions to describe the probabilities in order to avoid gratuitous repeating decimals. The probability of any particular value showing up is 16. To calculate the probability of a member of a set of values showing up, we can add them up individually, as this is just an or operation. So the probability of a 1 or a 4 is 16   + 16   =  26.

This gets more interesting when we want to compute probabilities such as "anything except a 6". Since that is equivalent to not, we calculate 66   - 16   =  56. An alternative is to sum the probabilities of those values, but using not makes the calculation much simpler.

In general, by using not we can greatly simplify our calculations. Consider calculating the probability of getting 16 or less when rolling three dice. If we view it as "not (17 or 18)", the calculation becomes:
  • p(18) = p(6, 6, 6) = p(6) * p(6) * p(6) = 16   * 16  1 =  1216.
  • p(17) = p(6, 5, 5) + p(5, 6, 5) + p(5, 5, 6) = 3216.
  • p(16 or less) = not (p(17) or p(18)) = 1 - (1216  + 3216) = 1 - (4216) = 2122165354.
Two important caveats:
  1. To represent and as multiplication, the events must be independent of each other. This applies, for example, to coin flipping, because nothing about the first flip has any causative effect on the outcome of the second flip. 
  2. To represent or as addition, the events must be mutually exclusive. For example, a die roll cannot be both a 1 and a 4 at the same time.


So, to conclude for now, I personally find it helpful to leverage the convertibility between boolean logic and probability to simplify my calculations and save effort.