Probability

1 Events and probability

Example

Suppose we roll a fair six-sided die. The set of possible outcomes is W = {1,2,3,4,5,6}. We can consider many possible events, e.g. ``the result is 5'', ``the result is at least 4'', ``the result is divisible by 2''.

Since the die is fair we would say that all 6 outcomes are equally likely, with each having probability 1/6. So writing P for Probability, P(result is i) = 1/6 for i=1,2,...,6 and P(result is at least 4) = P(4,5,6) = 3/6.

1.1 Outcomes and events

Consider an experiment with a set of possible outcomes W.

The set of outcomes is called the sample space.
A particular outcome w Î W is called a sample point.
An event is a subset of W. An event A is said to occur if the outcome w satisfies w Î A.

Examples

Tossing a coin. W = {H,T}. Event ``getting a head'': A = {H}.
Rolling a die twice. W = {(i,j): i,j=1,2,...,6}. Event ``obtaining a total of 4'': A = {(1,3),(2,2),(3,1)}.
Measuring the lifetime of a lightbulb. W = [0,¥). Possible event ``the bulb is still working after t time units'': A = (t,¥).
Record the price of a share over a period of trading of length T. W = {f:[0,T] ® [0,¥]}. Possible event ``the price never falls below L'': A = {f:[0,T] ® [L,¥)}.

For example 2, if the outcome of the experiment is (2,2) then then event A occurs.

For events A,B Í W,

A Ç B corresponds to the event ``A and B''.
A È B corresponds to the event ``A or B or both''.
A^C (º W \ A) corresponds to the event ``A does not occur''.
A \ B (º A-B) corresponds to the event ``A but not B''.

1.2 Elementary probability

If the sample space W is finite and if each sample point w Î W is equally likely then we can consider the special case in which the probability of an event A is defined to be P(A) = |A|/|W|.

Example

A random number generator generates R random digits. For k = 0,1, ...,9 find the probability that:

no digit exceeds k.
k is the greatest digit generated.

Take the first sentence to mean that W = {(d₁,d₂,...,d_r): d_i = 0,1,...,9; i = 1,2,...,r} with each of the 10^r sample points equally likely.

The event of interest A_k = {(d₁,d₂,...,d_r): d_i = 0,1,...,k; i = 1,2,...,r}. Here |A_k| = (k+1)^r, so P(A_k) = |A_k|/|W| = (k+1)^r/10^r.
Write B_k for the event that k is the greatest digit generated. B_k = A_k \ A_k-1 (with A_-1 = Ø). Now A_k-1 Í A_k so |B_k| = |A_k|-|A_k-1| = (k+1)^r - k^r. Thus P(B_k) = |B_k|/|W| = (k+1)^r-k^r/10^r.

1.3 Counting

Ordered selection

Suppose we have n balls numbered 1,...,n in a box and that we choose them sequentially. There are n! possible outcomes. If only r of the balls are chosen, the number of possible outcomes is n(n-1)...(n-r+1). This procedure is called sampling without replacement.

If the balls are retuned to the box before the next choice is made, the procedure is called sampling with replacement¹. The number of possible outcomes when r choices are made is n^r.

Examples

In a group of r people, what's the probability that two or more have the same birthday? Write b_i for the birthday (day of year) of the ith person. Then W = {(b₁,...,b_r) : b_i=1,2,...,365; i = 1,2,...,r}. Assume that all 365^r outcomes are equally likely. Write A = {two or more people share a birthday}. Then A^C = {all r people have different birthdays} = 365 × 364 × ... × (365-r+1) = 365^r. Since |A| = |W|-|A^C| = 365^r - 365^r, P(A) = 1 - 365^r/365^r.

Unordered selection

Recall that no. of subsets of {1,...,n} with r elements is n r = n!/r!(n-r)!. More generally there are n!/n₁!n₂!... n_m! ways of partitioning the set {1, ...,n} into a first n₁-subset, a second n₂-subset, ..., and an mth n_m-subset, where å_k=1^m n_k = n.

Example

What is the probability of the event A that a hand in bridge (13 cards) contains 5 spades, 4 hearts, 3 diamonds and 1 club? No. of hands of cards = 52 13. No. of hands with 5S, 4H, 3D, 1C is 13 513 413 313 1, so

P(A) =

|A|

|W|

13 513 4 13 313 1

52 13

1.4 Probability measures

A collection of subsets of W is called an event space or a s-field if

W, Ø Î
A Î A^C Î
A₁, A₂, ... Î È_i=1^¥ A_i Î

Note that since A Ç B = (A^C È B^C)^C, A, B Î A Ç B Î and more generally A₁,A₂, ... Î Ç_i=1^¥A_i Î .

The informal idea is that in a particular application with sample space W, the event space corresponds to the collection of events ``of interest''. (We will se that ``of interest'' means those sets whose probabilities we may wish to know or calculate.)

Examples

= {all subsets of W}
= {Ø, W} or = {Ø, A, A^C, W} for some A Î W.

Definition A function P: is called a probability measure if

0 £ P(A) £ 1 " A Î
P(W) = 1
If A₁, A₂, ... are disjoint events in then P(È_i=1^¥) = å_i=1^¥ P(A_i). The number P(A) is called the probability of the event A. The triple (W, , P) is called a probability space.

Technical aside: formally P(A) is only defined for A Î . We will adopt the convention throughout that unless otherwise stated all subsets of interest belong to .

Proposition A probability measure P satisfies:

P(A^C) = 1-P(A)
P(Ø) = 0
If A Í B then P(A) £ P(B).
P(A È B) = P(A) + P(B) - P(A Ç B)

Proof

From II and III, 1 = P(W) = P(A È A^C) = P(A)+P(A^C), since A Ç A^C = Ø.
P(Ø) = P(W^C) = 1-P(W) (by 1) = 1-1 (by II) =0.
For A Í B, B = AÈ (B Ç A^C) (disjoint). From III, P(B) = P(A) + P(B Ç A^C) ³ P(A), since P(B Ç A^C) ³ 0 by I.
Write A È B = A È (B Ç A^C) and B = (B Ç A) È (B Ç A^C) (disjoint). From III P(A È B) = P(A) + P(B Ç A^C) (*) and P(B) = P(B Ç A) + P(B Ç A^C) (**). (iv) follows by subtracting (**) from (*) and rearranging.

Theorem (Inclusion-Exclusion formula)

i=1

A_i)

i=1

P(A_i) -

i<j

P(A_i Ç A_j) + ...

+(-1)^r-1

i₁<i₂<...<i_r

P(A_i₁ Ç ... Ç A_{i_r}) + ... + (-1)^n-1 P(A₁ Ç ... Ç A_n)

The summation å_{i₁<i₂<...<i_r} means summation over all n r sets of indices which are subsets of 1, ..., n of size r.

Proof by induction
Property (iv) of the previous theorem gives the result for n=2. Further, by (iv) again,

P(A₁ È ... È A_n)	=	P((A₁ È ... A_n-1) È A_n)
	=	P(A₁ È ... È A_n-1) + P(A_n) - P((A₁ È ... È A_n-1) Ç A_n)
	=	P(A₁ È ... È A_n-1) + P(A_n) - P((A₁ Ç A_n) È ... È (A_n-1 Ç A_n))

Now assume the result for n-1 and substitute for first and third terms to give the result.

Example A group of n people place their coats in a pile. Later they each take one coat at random from the pile. What is the probability that at least one person has their own coat?

Take as sample space the n! possible assignments of coats to people. Let A_k be the event that person k has their own coat. To get P(È_i=1ⁿ A_i use inclusion-exclusion formula.

Note that

P(A_i₁ Ç A_i₂ Ç ... Ç A_{i_r}

(n-r)!

Thus

i₁<i₂<...<i_r

p(A_i₁ Ç ... A_{i_r}

n r

(n-r)!

and so

i=1

A_i)

1 -

- ··· + (-1)⁽n-1)

1-e^-1 as n ¥

1.5 Conditional probability and independence

Sometimes we may have partial information about the outcome of an experiment. In general this partial information will change the calculation of probabilities. For example, having thrown a fair die, we may be todl that the outcome is even. Then the probability of a 1, 3 or 5 becomes zero, and the probability of a 2, 4 or 6 becomes 1/3.

Definition Provided P(B)>0, define a conditional probability of A given B, written P(A|B), by P(A|B) = P(A Ç B)/P(B).

Remark For fixed B with P(B)>0 we can define a new function Q on by Q(A) º P(A|B). It is straightforward to check that Q is a probability measure.

Example You are playing poker. Define R º ``I have a royal flush'', E º ``My hand contains Aª''. Find P(R|E).

By definition,

P(R|E) =

P(R Ç E)

P(E)
=

1/52 5

51 4/52 5
=

1

52 4
From first principles. Assume one card is Aª and consider new experiment relating only to the unknown values of the other four cards. Each of the 51 4 outcomes is equally likely and exactly one will result in a royal flush. The required condition probability is thus 1/51 4.

Note that P(R) = 4/52 5, and so P(R|E) = 13/5 P(R) > P(R). Knowledge that E has occurred changes (here increases) the probability of R occurring.

Example A hat contains three cards. One card is black on both sides, one is black on one side and white on the other, and one is white on both sides. A card is drawn at random and placed on the table. The visible side is black. What is the probability that the other side is black?

Label the faces of the cards b₁,b₂ for black-black, w₁, w₂ for white-white and b₃,w₃ for black-white. Sample space W = { (b₁,b₂),(b₂,b₁),(w₁,w₂),(w₂,w₁),(b₃,w₃),(w₃,b₃) } (first number is upper face). All six outcomes equally likely.

Define event B_U = {(b₁,b₂),(b₂,b₁),(b₃,w₃)} (black uppermost) and B_D = {(b₁,b₂),(b₂,b₁), (w₃,b₃)} (black downermost). Then

P(B_D|B_U) =

P(B_D Ç B_U)

P(B_U)

P({(b₁,b₂),(b₂,b₁)})

P(B_U)

2/6

3/6

Theorem (Properties of conditional probability)

P(A Ç B) = P(A)P(B|A) = P(B)P(A|B)
P(A Ç B Ç C) = P(A)P(B|A)P(C|A Ç B)
P(A|B Ç C) = P(A Ç B|C)/P(B|C)

Proof Immediate from definition of conditional probability.

We call events A and B independent if the occurrence of one of them does not affect the probability of the other.

Definition Events A and B are independent if P(A Ç B) = P(A)P(B). More generally, a colelction of events A_i (i Î I) are independent if P(Ç_{i Î J} A_i) = Õ_{i Î J} P(A_i) for all finite subsets J of I.

Note that A and B independent P(A|B) = P(A) and P(B|A) = P(B).

Example Two dice are thrown. The sample space W = (i,j): 1 £ i,j £ 6 has 36 equally likely outcomes. Let A₁ = {first die odd}, A₂ = {second die odd}, A₃ = { sum is odd}. Are A₁, A₂ independent? P(A₁) = P(A₂) = 18/36, P(A₁ Ç A₂) = 9/36. Then P(A₁ Ç A₂) = P(A₁)P(A₂), so yes.

Similarly A₂, A₃ and A₁,A₃ are independent so the three events are pairwise independent.

Are A₁, A₂, A₃ independent? P(A₁ Ç A₂ Ç A₃) = 0 ¹ 1/8 = P(A₁)P(A₂)P(A₃), so no.

Example You are asked a series of questions and you get each right with probability p. The outcomes of different questions are independent (A sequence of Bernoulli trials). The probability that the first correct answer is at the rth question is p_r=(1-p)^r-1p. Since å_r=1^¥ p_r=1 you've got to get a question right eventually.

Theorem (Law of Total Probability / Partition Theorem) Let B₁, B₂,...,B_n be a partition of W. Then P(A)=å_i=1ⁿ P(A|B_i)P(B_i).

[s]Proof If i ¹ j then A Ç B_i and A Ç B_j are disjoint. Then

i=1

P(A|B_i)P(B_i)=å

P(AÇ B_i) = P(

i=1

(AÇ B_i)) = P(A)

Example The probability I remember to lock my bike is 19/20. If I forget to lock it, it's stolen with probability 4/5, while if I do lock it it's stolen with probability 1/100. What is the probability that it's stolen tomorrow?

Let L={bike locked}, S={bike stolen}. Then P(L)=19/20 and P(L^C)=1/20. P(S|L)=1/100, P(S|L^C)=4/5. Now P(S)=P(S|L)P(L) + P(S|L^C)P(L^C)=99/2000=0.0495 by above theorem using the partition L, L^C.

Theorem (Bayes Formula) Let B₁,B₂,...,B_n be a partition of W. Then

P(B_i|A)=

P(A|B_i)P(B_i)

j=1

P(A|B_j)P(B_j)

[s]Proof

P(B_i|A)=

P(B_iÇ A)

P(A)

P(A|B_i)P(B_i)

j=1

P(A|B_j)P(B_j)

(top half by definition of conditional probability, bottom by previous result)

Example A diseae occurs by chance in one in every 200 people. A random person is tested; if they have the disease, the test will correctly say so with probability 0.95; if not, the test will wrongly say they do with probability 0.01. Find the probability that (i) The test says a person has the disease (ii) the person has the disease given that the test says they do.

Let D={person has disease}, A={test says they do}.

P(A)=P(A|D)P(D)+P(A|D^C)P(D^C) (using partition D, D^C) =0.95× (1/200) + 0.01 × (199/200) = 0.0147.
By Bayes formula, P(D|A)=(P(A|D)P(D)/0.0147 =0.95× (1/200)/0.0147 = 95/294 » 0.32.

Suppose instead that the person is being examined by a doctor because they are feeling ill. After the examination but before the test, the doctor reckons P(D)=0.3. Then P(A)=0.95× (3/10) + 0.01 × (7/10) = 0.292 and P(D|A)=P(A|D)P(D)/0.292 = 0.95 × (3/10)/0.292 = 285/292 » 0.976.

2 Discrete Random Variables

Example

A roulette wheel has 38 slots: 18 red, 18 black, 2 green. Suppose the red slots are labelled 1,3,...,35, the black slots 2,4,...,36 and the green 0 and 00. A gambler bets £1 on red. She wins £1 for red and loses otherwise. So W = {00, 0, 1, ..., 36} and if the outcome is w, the gambler wins X(w) where X(1)=X(3)=...=X(35)=1, X(00)=X(0)=X(2)=...=X(36)=-1. The function X:W is a discrete random variable.

Take W to be finite or countable, with P defined on all subsets of W.

Definition A discrete random variable S is a real-valued function defined on the sample space W.

Technical aside If we do not assume that W is countable then X:W is a discrete random variable on the probability space (W, , P) if

{X(w):wÎW} is a countable set
{w Î W: X(w) = x} Î " x Î

(1) ensures X is discrete (takes a countable set of values). (2) needed to ensure that the event ``X takes value X'' belongs to event space .

Example

Suppose you throw two dice: W = {(i,j): 1 £ i,j £ 6}. We can define random variables Y and Z by Y(i,j)=i+j and Z(i,j)=max(i,j).

Write R_X for the range of X, i.e. the set of values that the random variable X can take.

Let R_X={x_i: i=1,2,...} (finite or countable since W is). Write P(X=x_i)=P({X=x_i})=P({wÎW:X(w)=x_i})

w:X(w)=x_i

P({w})

Further, for A Ì , P(X Î A)=P({w Î W:X(w) Î A})

w:X(w)Î A

P({w}) =

x_iÎ A

w:X(w)=x_i

P({w})=

x_iÎ A

P(X=x_i)

Examples

In the roulette example, R_X = {-1,1}. P(X=1)=p₁+p₂+...+p₃₅ =18/38=9/19. p_i = P{outcome is i}. P(X=-1)=p₀₀+p₀+p₂ +...+p₃₆=20/38=10/19.

Dice example: R_Y={2,3,...,12}. P(Y³ 11)=P(Y=11)+P(Y=12) =2/36+1/36=1/12.

Definition The probabilities P(X=x_i), x_iÎ R_X are referred to as the (probability) distribution of the random variable X. The function p_X:R_X [0,1] defined by p_X(X_i)=P(X=x_i) is called the probability mass function of X. Sometimes we abbreviate p_X(x) to p(x). Note that since P(W)=1, å_{xÎ R_X}p_X(x)=1.

For roulette example, p(-1)=10/19, p(1)=9/19.

Examples

A random variable X with R_X={0,1} is said to have a Bernoulli distribution if P(X=1)=p, P(X=0)1-p. e.g. conduct an experiment with two outcomes called ``success'' and ``failure'' and let p be the probability of success. Associate X=1 with success, X=0 with failure.
A random variable X with R_X={0,...,n} is said to have a Binonmial distribution with parameters n and p if P(X=k) = n kp^k(1-p) ^n-k k=0,...,n. e.g. X is no. of successes in n independent trials of the experiment in (1).
A random variable X with R_X={1,2,...} is said to have a Geometric distribution with parameter p if P(X=k)=(1-p)^k-1p k=1,2,.... e.g. repeat independent trials of experiment in (1) and define X to be number of trials required to first get a success.
Suppose l>0 is fixed. A random variable X with R_X={0,1,...} is said to have a Poisson distribution with parameter l if P(X=k) = (e^-ll^k)/k! for k=0,1,2,....

It turns out that the Poisson distribution provides a good description of the numbers of ``rare'' events over some time period, e.g. no. of fatal accidents in a region in a year or number of paricles emitted by a radioactive sauce.

2.1 Expectation

Definition The expectation (or mean) of a random variable X is the number E(X) = å_{x Î R_X}xP(X=x) = å_{x Î R_X}xp_x(x) provided the sum converges absolutely. (i.e. provided å_{x Î R_X} |xP(X=x)|<¥)

Examples

Bernoulli (p) distribution: P(X=0)=(1-p), P(X=1)=p, E(X)= 0.(1-p)+1.p=p.
Poisson (l) distribution.

E(X)=

¥

å

x=0
P(X=x) =

¥

å

x=0
x

e^-ll^x

x!

(Put x-1=k) =e^-ll

¥

å

k=0

l^k

k!
= e^-ll e^l = l

2.2 Functions of random variables

If X is a discrete random variable and g:R_X is any function, then Y=g(X) is also a random variable defined by Y(w)=g(X(w)) for wÎW.

e.g. for constants a,b,c, Y₁=aX+b, Y₂=(X-c)² are random variables taking values aX(w)+b, (X(w)-c)², wÎW. In general, for Y=g(X), P(Y=y)=P(g(X)=y)=å_xg(x)=yP(X=x). The expectation of the random variable g(X) is

E(g(X)) =

yÎ R_Y

yP(g(x)=y) =

yÎ R_Y

xg(x)=y

P(X=x) =

xÎ R_X

g(x)P(X=x)

Theorem (Properties of Expectation) Suppose a and b are constants.

If X³ a (i.e. if X(w)³ a"wÎW) then E(X)³ a.
If P(X=b)=1 then E(X)=b.
E(aX+b)=aE(X)+b
E(g(X)+h(X))=E(g(X))+E(h(X))

[s]Proof

E(X) = å_{xÎ R_X}xP(X=x)³å_{xÎ R_X}aP(X=x)=a
P(X=x) = 1if x=b so E(X)=1.b+0=b 0otherwise
E(aX+b) =

å

xÎ R_X
(ax+b)P(X=x) =

a

å

xÎ R_X
xP(X=x) +b

å

xÎ R_X
P(X=x) = aE(X)+b
E(g(X)+h(X)) =

å

xÎ R_X
(g(x)+h(x))P(X=x)

=

å

xÎ R_X
g(x)P(X=x)+

å

xÎ R_X
h(x)P(X=x) = E(g(x)) + E(h(X))

Definition The variance of a random variable X, usually written Var(X), is defined by Var(X)=E((X-E(X))²). So writing µ=E(X), Var(X) = E((X-µ)²) = å_{xÎ R_X}(x-µ)²P(X=x).

The variance of a random variable means how ``spread out'' or dispersed its distribution is around its mean.

Example

Suppose X=-1with prob. 1/21with prob. 1/2 and Y=-100with prob. 1/2100with prob. 1/2. Then E(X)=E(Y)=0. Var(X)=1/2(-1-0)²+1/2(1-0)²=1, Var(Y)=1/2(-100-0)²+1/2(100-0)²=10000.

Theorem (Properties of Variance)

Var(X) ³ 0.
If a,b are constants then Var(aX+b)=a²Var(X).
Var(X)=E(X²)-[E(X)]²

[s]Proof

Var(X)=å_{xÎ R_X}(x-µ)²P(X=x) ³ å_{xÎ R_X} 0.P(X=x) = 0.
Var(aX+b) = E[(aX+b-E(aX+b))²] = E[(aX+b-aE(X)-b)²] = E[(a(X-E(X)))²] = a²Var(X)
Var(X) = E((X-µ)²) = E(X²-2µ X+µ²) = E(X²)-2µ E(X) +µ ² = E(X²) - 2µµ + µ² = E(X²)-µ²

Examples

Bernoulli (p) distribution. P(X=1)=p=1-P(X=0). E(X²) = å_{xÎ R_X}x²P(X=x)=1².p+0²(1-p)=p. Var(X) = E(X²) - (E(X))² = p-p² = p(1-p).
Poisson (l) distribution: P(X=x)=e^-l l^x/x! x=0,1,...

E(X²)

k=0

k²

e^-ll^k

= l e^-l

k=1

l^k-1

(k-1)!

l e^-l

é
ê
ê
ë

k=1

(k-1)

l⁽k-1)

(k-1)!

k=1

l^k-1

(k-1)!

ù
ú
ú
û

l e^-l

é
ê
ê
ë

k=2

l^k-2

(k-2)!

k=1

l^k-1

(k-1)!

ù
ú
ú
û

= l e^-l(l e^l + e^l) = l^l

1: surprisingly enough

This document was translated from L^AT_EX by H^EV^EA.