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.
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).
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.
Linearity of expectation:
E[a X + b Y] = a E[X] + b E[Y]
for any two events X, Y and constants a, b.
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.]