Probability Basics


We will start with a very intuitive sense of what probability is, and what an "event" is. For example: We are using a fair die. The usual, with six sides and numbers 1, 2, 3, 4, 5, 6 on its sides. We assume each outcome is equally probable. We throw it once: what happens is "an event." Then the probability of the event A: "4 was rolled" is 1/6. The probability of the event B: "5 was rolled" is 1/6. The probability of the event C: "an even number was rolled" is 1/2. Etc.

Basics of probability:


For any two events A, B:
Prob(A or B) = Prob(A) + Prob(B) - Prob(A and B)
From this comes a basic way to estimate probabilities: Prob(A or B) <= Prob(A) + Prob(B) or more generally:

Prob(A1 or A2 or ... or An) <= sum Prob (Ai)

Two events A, B are mutually exclusive if Prob(A and B) = 0.

Two events are independent if Prob(A and B) = Prob(A) * Prob(B).

Expectations ( =expected values ):


Expected value of a real variable X is defined as



where the sum is taken over all values x that X can take.
In words:
the expected value of a variable is the weighted sum of all its values, weighted according to the probability that they happen.

Example: You throw a die and get $10 if it comes out 1 and $0 if not.

The expected value of your reward is $10 * 1/6 + $0 * 5/6 = $10/6.

You play the lottery. You pay $1 for the ticket and win one million dollars with probability 1/(1 billion). How much do you expect to win? What's the expected balance?

Expected outcome = -$1 + Expected win.

Expected win = $1,000,000 * 1/(1 billion) + $0 * (the probability I do not win) = $1/1000 = 0.1cent.

So expected outcome = you lose 99.9 cents.

Useful properties of expectations:

Linearity of expectation:

E[a X + b Y] = a E[X] + b E[Y]

for any two events X, Y and constants a, b.

How Many Roads Must One Man Walk?

Finally, something that comes up very frequently:

Suppose you have a sequence of events, each of which happens with probability p, independent of the previous ones. What is the expected number of tries in the sequence you must observe until you see an event you like.

Examples:

Flip a coin several times. How many tries until it comes out heads.

Throw a pair of die. How many tries until they give you {6,6}?

Play the lottery. How many tries until you win?

Probability event i happens is (1 - p)i - 1p In this case you need to wait i steps. So the expected number of steps to wait is:



It's a standard summation that adds up to 1/p. [A cute or painful algebra exercise, depending on how you do it, I guess...]

so:

Fact: If you have a sequence of independent events, each succeeding with probability p, the expected number of tries until the first success is 1/p.

Or slightly more generally:

Fact: If you have a sequence of independent events, each succeeding with probability at least p, the expected number of tries until the first success is at most 1/p.

[The last one is useful if you are doing sampling without replacement, so the probabilities changes as you go along.]