Chapter 6
Discrete Probability

 Modified: 

© Ray Wisman

Resources

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/index.html - Index to the Rosen text Web site learning resources.

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/chapter6/self_assessments.html - Chapter self-assessment with answers and explanations .

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/chapter6/extra_examples.html - Extra examples with solutions.

Poker probability - http://en.wikipedia.org/wiki/Poker_probability

Permutations and Combinations - http://easycalculation.com/statistics/permutation-combination.php

The difference between probability and odds (from http://mathforum.org/library/drmath/view/56706.html).

Probability of a successful event is defined as:

           Successful # events
p(x) =     Total # events

The probability of drawing an ace from a single deck of 52 cards is 4/52 = 1/13 (or about 0.077 = 7.7%).

 

Odds are given as:

Events for : Events against

Odds of 1:1 would be read as "one TO one", not "one OUT OF one." (The words "out of" seem to imply total chances, which is probability, not odds.)

Total events = Events for + Events against

Events against = Total events - Events for

Odds of drawing an ace in a deck of cards is 4:(52-4) = 4:48 = 1:12.

 

6.1 An Introduction to Discrete Probability

Finite Probability

Definitions

Experiment (in probability theory)

A procedure that yields one of a set of possible outcomes

Example

Flipping a coin.

Rolling a die.

Others?

Sample Space - All Possible Outcomes

A mathematical set containing all the possible outcomes of a probability experiment.

S is often used to denote the sample space

Example

A coin has 2 possible outcomes.

S = {Heads, Tails}

|S| = 2

Question 6.1

For a die, what is:

S =

|S| =

You have a 5, 10 and 25 cent coin in your pocket.

Pulling out a coin, what is:

S =

|S| =

 

Successful Outcomes

A mathematical set containing all the possible outcomes that meet some criteria for success.

Criteria for success is determined prior to executing the experiment.

E is often used to denote the set of successful outcomes.

E ⊆ S

Example

Flip a head

E = {H}

|E| = 1

E ⊆ S = {H, T}

Example

You have a Euro 5, 10 and 20 cent coin in your pocket.

What is E, the event of pulling out a 5 or 10 cent coin?

E = {5, 10}

|E| = 2

E ⊆ S = {5, 10, 20}

Question 6.2

Roll an odd number on a die.

What is:

S =

E =

|E| =

 

Definition 1

Probability function  p(E) =

S is a finite sample space (i.e., a finite set of all possible outcomes from an experiment)

All outcomes in S are equally likely to occur when the experiment is executed

E is a set containing all the successful outcomes, and E ⊆ S

Note:

  • The function p's domain is the set E, where E ⊆ S
  • The function p's range is a value r, where r∈ R, and 0 ≤ r ≤ 1

 

Examples

What is the probability of flipping a head?

S = {H, T}

|S| = 2

E = {H}

|E| = 1

p(E) = = 1/2

 

What is the probability of a die landing with a 2 or 5?

S = {1, 2, 3, 4, 5, 6}

|S| = 6

E = {2, 5}

|E| = 2

p(E) = = 2/6 = 1/3

 

What is the probability that a card selected from a regular 52-card deck is a Jack?

S = {2C, 3C, ..., KC, AC, 2D, 3D, ..., KD, AD, 2H, 3H, ..., KH, AH, 2S, 3S, ..., KS, AS}

|S| = 52

E = {JC, JD, JH, JS}

|E| = 4

p(E) = = 4/52 = 1/13

 

Question 6.3

  1. You have a Euro 5, 10 and 20 cent coin in your pocket.

    What is the probability of pulling out one coin that is a 5 or 10 cent coin?

    S = {5, 10, 20}

    |S| = 3

    E = {5, 10}

    |E| = 2

    p(E) = =

     

  2. What is the probability that the sum of the numbers on two dice is odd?

    S = {1+1,1+2,1+3,1+4,1+5,1+6,
            2+1,2+2,2+3,2+4,2+5,2+6,
            3+1,3+2,3+3,3+4,3+5,3+6,
            4+1,4+2,4+3,4+4,4+5,4+6,
            5+1,5+2,5+3,5+4,5+5,5+6,
            6+1,6+2,6+3,6+4,6+5,6+6}

    |S| = 36

    E = {1+2,1+4,1+6,
            2+1,2+3,2+5,
            3+2,3+4,3+6,
            4+1,4+3,4+5,
            5+2,5+4,5+6,
            6+1,6+3,6+5}

    |E| = 18

    p(E) = =

     

  3. What is the probability that random number between 1-200 is even?

    S =

    |S| =

    E =

    |E| =

    p(E) = =

     

  4. What is the probability of flipping a coin six times and getting six heads?

    S = {TTTTTT, TTTTTH, ..., THHHHH, HHHHHH}

    |S| = 2*2*2*2*2*2 = 26 = 64

    E =

    |E| =

    p(E) = =

     

  5. What is the probability that Sally wins the one prize in a drawing where 10 people buy one ticket each?

    S =

    | S | =

    E =

    | E | =

    p(E) = =

     

  6. What is the probability that Sally wins 1st, 2nd AND 3rd prizes in a drawing where 10 people buy a ticket each and the name is returned to the barrel?

    S = {(Sally, Sally, Sally), (Sally, Person1, Person9), (Person4,Person5,Person10), ... }

    | S | = 10 ways to win 1st prize, 10 ways to win 2nd and 10 ways to win 3rd, 10*10*10

    E =

    | E | =

    p(E) = =

  7. What is the probability that Sally wins exactly one of 1st, 2nd OR 3rd prizes in a drawing where 10 people buy a ticket and the name is returned to the barrel?

    S = {(Sally, Sally, Sally), (Sally, Person1, Sally), (Person4,Person5,Person9), ... }

    | S | = 10 ways to win 1st prize, 10 ways to win 2nd and 10 ways to win 3rd, 10*10*10

    E = { (Sally, 9 others, 9 others), (9 others, Sally, 9 others), (9 others, 9 others, Sally) }

    | E | = 81 + 81 + 81

    p(E) = =

  8. What is the probability that Sally, Dick and Fred win 1st, 2nd and 3rd prizes respectively in a drawing where 10 people enter and the name is returned to the barrel (i.e. more than one prize per person)?

    S = {(Sally, Sally, Sally), (Sally, Dick, Fred), (Person4,Person5,Person10), ... }

    | S | = 10 ways to win 1st prize, 10 ways to win 2nd and 10 ways to win 3rd, 10*10*10

    E = { (Sally, Dick, Fred) }

    | E | =

    p(E) =   =

  9. What is the probability that Sally, Dick and Fred win 1st, 2nd and 3rd prizes respectively in a drawing where 10 people enter and the name is NOT returned to the barrel (i.e. only one prize per person)?

    S = {(Sally, Dick, Fred), (Person4,Person5,Person10), ...

    | S | = 10 ways to win 1st prize, 9 ways to win 2nd and 8 ways to win 3rd, 10*9*8

    E =

    | E | =

    p(E) =   =

  10. What is the probability that Sally and Fred each win one of 3 prizes in a drawing where 10 people enter and the name is returned to the barrel?

    S = {(Sally, Sally, Sally), (Sally, Fred, Person3), (Person4,Person5,Person10), ... }

    | S | = 10 ways to win 1st prize, 10 ways to win 2nd and 10 ways to win 3rd, 10*10*10

    E = {(Sally, -, Fred), (Fred, -, Sally), ...

    Note that (Sally, -, Fred) ≠(Fred, -, Sally), a permutation

    P(3,2) = 6

    1 2 3
    Sally Fred -
    Sally - Fred
    - Sally Fred
    Fred Sally -
    Fred - Sally
    - Fred Sally

    The - name occurs 8 ways other than Sally or Fred

    | E | = 6 * 8 = 48

    p(E) = =

  11. What is the probability that Sally, Dick and/or Fred win all 4 prizes in a drawing where 10 people enter and the name is returned to the barrel?

    S = {(Sally, Sally, Sally, Sally), (Sally, Dick, Fred,person5), (Person4,Person5,Person10,Fred), ... }

    | S | = 10 ways to win 1st prize, 10 ways to win 2nd, 10 ways to win 3rd, and 10 for 4th, 104

    E = {(Sally, Sally, Sally, Sally), (Sally, Sally, Fred, Sally), (Fred, Sally, Fred, Dick), ... }

    | E | = 34

    p(E) =   =

  12. What is the probability of drawing one card, the Ace of diamonds, from a deck of 52 cards?

    |S| =

    |E| =

    p(E) = =

     

  13. What is the probability of getting the Ace of diamonds in a poker hand?

    |S| = C(52,5)

    |E| =

    Pick 1 Ace of diamonds = 1

    Pick the 4 cards from the remaining 51 = C(51,4)

    1*C(51,4)

    p(E) = =

     

  14. What is the probability of getting 4 Aces in a poker hand?

    |S| = C(52,5)

    |E|

    Pick 4 Aces from 4 Aces

    C(4,4) = 4!/4!(4-4)! = 1

    Note that {AH, AC, AS, AD} = {AD,AH,AC,AS}, order does not matter, a combination.

    Pick 1 card from the remaining 48

    C(48,1)

    C(4,4)*C(48,1) = C(48,1)

    p(E) = =

     

  15. What is the probability of getting 3 Aces in a poker hand?

    |S| = C(52,5)

    |E|

    Pick 3 Aces from 4 Aces

    C(4,3)

    Pick the 2 cards from the remaining 48

    C(48,2)

    Reason only 48 is the fourth Ace must be excluded to prevent picking 4 Aces.

    C(4,3) * C(48,2)

    p(E) = =

     

  16. What is the probability of getting 3 cards of the same suit in a poker hand?

    |S| = C(52,5)

    |E|

    Pick 3 from 13 suit cards

    C(13,3)

    Pick 1 suit from 4

    C(4,1)

    Pick the 2 cards from the remaining 39 choices

    C(39,2)

    52 - 13 = 39 because must exclude all cards in the same suit as selected.

    C(13,3) * C(4,1) * C(39,2)

    p(E) = =

     

  17. What is the probability of getting 5 cards of the same suit in a poker hand?

    |S| = C(52, 5)

    |E|

    Pick ? from 13 suit cards

    C(13, ?)

    Pick ? suit from 4

    C(4, ?)

    |E| = C(13, ?) * C(4, ?)

    p(E) = =

     

  18. What is the probability of getting 3 cards of the same kind (e.g. Jacks) in a poker hand? We count full houses as 3 of a kind.

    |S| = C(52,5)

    |E|

    Pick 1 from 13 kinds

    C(13,1)

    Pick 3 suits from 4

    C(4,3)

    Pick 2 cards from the remaining 48

    C(48,2)

    Not C(49,2) because would allow picking 4 of a kind.

    C(13,1)*C(4,3)*C(48,2) = 58656

    There are 3744 full houses, which normally would be subtracted (Inclusion/Exclusion principle).

    p(E) = =

     

  19. What is the probability of getting 2 pair in a poker hand?

    |S| = C(52,5)

    |E|

    Pick 2 kinds from 13 kinds = C(13,2)

    Pick 2 suits from 4 = C(4,2) for first pair

    Pick 2 suits from 4 = C(4,2) for second pair

    Pick the 1 card from the remaining 44 = C(44,1)

    C(44,1) because must exclude the 8 cards from which the 2 pair are drawn or could get 3 of a kind.

    C(13,2) * C(4,2) * C(4,2) * C(44,1) = 123552

    p(E) = =

  20. What is the probability of a die never coming up an even number when rolled 6 times?

    S = {(1,1,1,1,1,1), (1,1,1,1,1,2), ..., (6,6,6,6,6,6)}

    |S| = 66 = 46656

    E = {(1,1,1,1,1,1), (1,1,1,1,1,3), ..., (5,5,5,5,5,5) }

    |E|  = 36 = 729

    p(E) =   = 729/46656 = 1/64

     

  21. In a lottery, what is the probability that a person picks the correct 6 numbers out of 40?

    The correct 6 form a set, therefore, the order they appear in the set does not matter.

    Is this a counting problem of the form of a permutation or of the form of a combination?

    |S| = C(40, 6) = 3,838,380 6-digit combinations

    |E| =

    p(E) = =

    How many tickets should you buy with a different set of 6 digits to increase your odds of winning to 100%

    |E| / 3,838,380 = 1   

    What is |E|?

    How many tickets should you buy with a different set of 6 digits to increase your odds of winning to 1%

    |E| / 3,838,380 = 0.01

    What is |E|?

     

  22. In a lottery, what is the probability that a person picks exactly one correct of the correct 6 numbers out of 40?

    |S| = C(40, 6)

    |E|

    6 numbers in winning set, 34 non-winning number

    Pick one of the 6 numbers in winning set, C(6, 1) = 6

    Pick 5 of the 34 numbers not in winning set, C(34, 5) 

    |E| = 6*C(34,5)

    p(E) = = 0.434958

     

The Probability of Combinations of Events

Theorem 1

For E and event in sample space S, probability of event E

p( E ) = 1 - p( E )

Example

What is the probability that 10 bits will contain at least one 0?

The complementary event E is that the 10 bits contain no 0's.

S = {0000000000, 0000000001, ..., 1111111110, 1111111111}

|S| = 1024

One out of 210 = 1024 ways.

E = {1111111111}

|E| = 1

p(E) = 1/1024

By Theorem 1

p( E ) = 1 - p( E )

p( E ) = 1 - 1/1024 = 1023/1024

 

Example

The probability of getting the Ace of diamonds in a poker hand

|S| = C(52,5) = 2,598,960

|E|

Pick 1 Ace of diamonds = 1

Pick the 4 cards from the remaining 51 = C(51,4)

1*C(51,4)

p(E) = = 249,900/2,598,960 = 0.096

 

Question 6.4

What is the probability of not getting the Ace of diamonds in a poker hand?

 

Theorem 2

Events E1, E2 in sample space S,

p( E1 ∪ E2  ) = p( E1 ) + p( E2  ) - p( E1 ∩ E2  )

Probability of E1 OR  E2

Example

What is the probability that a die is odd OR greater than 4?

Solution

S = {1, 2, 3, 4, 5, 6}

|S| = 6

E1 an odd number, {1,3,5}.

p(E1) = | E1 | / |S| = 3/6

E2 a number greater than 4, {5,6}.

p(E2) = | E2 | / |S| = 2/6

E1 ∪ E2 an odd number OR greater than 4

E1 ∪ E2 = {1, 3, 5} U {5, 6} = {1, 3, 5, 6}

| E1 ∪ E2 | = 4

E1 ∩ E2 an odd number AND greater than 4, {1,3,5} ∩  {5,6}.

E1 ∩ E2 = { 5 }

p( E1 ∩ E2  ) = |E1 ∩ E2| / |S| = 1 / 6

p( E1 ∪ E2  ) = p( E1 ) + p( E2  ) - p( E1 ∩ E2  ) 

= 3/6 + 2/6 - 1/6

= 4/6

Theorem 2

Events E1, E2 in sample space S,

p( E1 ∪ E2  ) = p( E1 ) + p( E2  ) - p( E1 ∩ E2  )

Example

Probability that a positive integer ≤ 100 is divisible by 2 OR 5?

Solution

S = {1, 2, 3, ..., 99, 100}

|S| = ?

E1 is a positive integer  ≤  100 divisible by 2.

E1 = {2, 4, 6, ..., 100}

| E1 | = 50

p(E1) = | E1 | / |S| = 50/100

E2  is a positive integer  ≤  100 divisible by 5.

E2 = {5, 10, 15, 20, ..., 100}

| E2 | = 20

p(E2) = | E2 | / |S| = 20/100

E1 ∩ E2 is a positive integer  ≤  100  divisible by both 2 AND 5 (i.e. 10)

E1 ∩ E2 = { 10, 20, 30, 40 , 50, 60, 70, 80, 90, 100}

p( E1 ∩ E2  ) = |E1 ∩ E2| / |S| = 10 / 100

E1 ∪ E2 = ??

|E1 ∪ E2| = ??

p( E1 ∪ E2  )

= p( E1 ) + p( E2  )  - p( E1 ∩ E2  ) 

= 50/100 + 20/100 - 10/100

= 60/100 = 3/5

Question 6.5

S is the set of numbers between 1 and 10.

E1 is the set of odd numbers between 1 and 10.

E1 = ?

|E1| = ?

p(E1)= ?

E2 is the set in which 3 divides a number between 1 and 10?

E2 = ?

|E2| = ?

p(E2)=?

E1 ∩ E2  = ?                                     Odd 1-10 number AND divisible by 3.

p( E1 ∩ E2  )=?

p( E1 ∪ E2  ) = ?                               The probability a number 1-10 divisible by 3 OR it is an odd number.

Theorem 2

E1, E2 events in sample space S,

p( E1 ∪ E2  ) = p( E1 ) + p( E2  ) - p( E1 ∩ E2  )

 

6.2 Probability Theory

Assigning Probabilities

Definitions

equally likely - when each element in S (the sample space) has the same probability of being the outcome of an experiment

fair - a probability experiment where any outcome in S is equally likely to occur

biased - when some elements in S have higher probability of being the outcome of an experiment as compared to other elements in S

 

Requirements for assigning a probability to each outcome in S (the sample space)

p(s) is a function
  • Domain

    all the elements in S

  • Range

p(s) : S → R+ where R+ ≤ 1

or it can be written as

0 ≤ p(s) ≤ 1, ∀s ∈ S

= 1

Note, there exists two probability functions p

  1. p(E)

    has domain as E, where E ⊆ S, i.e., E is a set of specific outcomes in S

  2. p(s)

    has domain as s, where s ∈ S, i.e., s is a specific outcome in the sample space S

 

Example

Flipping a fair coin

S = { H, T }, where H represents heads, and T represents tails

E = { H } or E = { T }

All possible single experiment outcomes

Assignment of probability:

p(H) = 1/2

p(T) = 1/2

= p(H) + p(T) = 1/2 + 1/2 = 1

Note: here we are using the function p(s) whose domain is an element s ∈ S = {H, T}

Definition 1

uniform distribution

for sample space S

size |S| = n

∀s ∈ S : p(s) = 1/n

which means all the outcomes in S are equally likely

Question 6.6

S of a die = {1, 2, 3, 4, 5, 6}

|S| = ?

∀s ∈ S : p(s) = 1 / ?

Does a fair die have a uniform distribution?

 

Definition 2

Probability of E is the sum of the probabilities of the outcomes in E.

where E ⊆ S, then p(E) =  

Example

The probability of rolling an odd number with an unbiased die (each number equally likely)

S = {1, 2, 3, 4, 5, 6}

E = {1, 3, 5}

E = event of rolling an odd number with the unbiased die

p(E) = = p(1) +  p(3) +  p(5) = 1/6 + 1/6 + 1/6 = 1/2

Note:

the left hand side of '=' uses p(E) whose domain is a set E ⊆ S

the right hand side of '=' uses p(s) whose domain is an element s ∈ S

 

Question 6.7

The probability of rolling a number greater than 4 with an unbiased die

S = {1, 2, 3, 4, 5, 6}

E = ?

p(E) = = ?

 

Definition

random selection

Selecting an element from S where S has a uniform distribution

(i.e. when selecting any particular element from S is equally likely as selecting any other)

Example

The probability of rolling an odd number with a biased die (weighted)

Biased because 3 turns up twice as often as each other number
S = {1, 2, 3, 4, 5, 6}
All possible single experiment outcomes:

E = {1}, E = {2}, E = {3}, E = {4}, E = {5}, or E = {6}

Assignment of probability (probability distribution for the biased die):

p(1) = 1/7

p(2) = 1/7

p(3) = 2/7

p(4) = 1/7

p(5) = 1/7

p(6) = 1/7

Note: here using the function p(s) whose domain is an element s ∈ S

p(E), the odds of rolling an odd number with the biased die

E = {1, 3, 5}

p(E) = = p(1) +  p(3) +  p(5) = 1/7 + 2/7 + 1/7 = 4/7

Question 6.8

What is wrong with the following assignment of probability for a biased die?

p(1) = 1/6

p(2) = 1/6

p(3) = 2/6 = 1/3

p(4) = 1/6

p(5) = 1/6

p(6) = 1/6

 

 

Combinations of Events

Recall Theorem 2  is a general definition of the probability when two events can occur simultaneously OR not.

E1, E2 events in sample space S,

p( E1 ∪ E2  ) = p( E1 ) + p( E2 ) - p( E1 ∩ E2  )

Example

What is the probability that a fair die is

  1. odd OR
  2. greater than 4?

Solution

S = {1, 2, 3, 4, 5, 6}

|S| = 6

E1 = {1, 3, 5}, an odd number.

|E1| = ?

E2 = {5, 6}, a number greater than 4.

|E2| = ?

E1 ∩ E2 = {1,3,5} ∩  {5,6}, an odd number AND greater than 4.

E1 ∩ E2 = { 5 }

p(E1) = | E1 | / |S| = 3/6

p(E2) = | E2 | / |S| = 2/6

p( E1 ∩ E2  ) = |E1 ∩ E2| / |S| = 1 / 6

E1 ∪ E2 = {1, 3, 5} U {5, 6} = {1, 3, 5, 6}

p( E1 ∪ E2  )

= p( E1 ) + p( E2  ) - p( E1 ∩ E2  ) 

= 3/6 + 2/6 - 1/6

= 4/6

For E1 and E2 events in sample space S,

p( E1 ∪ E2  ) = p( E1 ) + p( E2 ) - p( E1 ∩ E2  )

Question 6.9.1

S = {1, 2, 3, 4, 5, 6}

E1 = {1, 3, 5}

E2 = {5, 6}

E1 ∪ E2 = {1,3,5} ∪ {5,6} = ?

|E1 ∪ E2| = ?

|E1 ∪ E2| / | S | = ?

 

When E1 ∩ E2 = ∅

p( E1 ∪ E2  ) = p( E1 ) + p( E2 )

Theorem 1 - defines the probability only when events are disjoint (i.e. do not intersect).

For E1, E2 ,..., En disjoint events in sample space S,

p( E1 ∪ E2 ∪ ... ∪ En ) = p( E1 ) + p( E2  )  + ... + p( En  )

Example

What is the probability that a fair die is less than 3 OR greater than 4?

S = {1, 2, 3, 4, 5, 6}

E1 = {1,2}, number less than 3.

E2 = {5,6}, number greater than 4.

E1 ∩ E2 = {1,2} ∩ {5,6}

E1 ∩ E2 = ∅

p(E1) = | E1 | / |S| = 2/6

p(E2) = | E2 | / |S| = 2/6

p( E1 ∩ E2  ) = |E1 ∩ E2| / |S| = 0

E1 ∪ E2 = {1, 2} U {5, 6} = {1, 2, 5, 6}

p( E1 ∪ E2  )

= p( E1 ) + p( E2  ) - p( E1 ∩ E2  ) 

= 2/6 + 2/6 - 0

= 4/6

 

Conditional Probability

Definition 3

Conditional probability, the probability of E given F

E and F events and p(F) > 0

p( E | F ) = p( E ∩ F ) / p( F )

Question 6.9.2

What is the probability of flipping a fair coin an odd number of T's?

THH
THT
TTH
TTT

Example 1

Conditional probability when

  1. a coin flipped 3 times
  2. the first toss is a Tail
  3. AND an odd number of Tails

Flipping coin 3 times, 23 possible outcomes (product rule).

      {

S =

 

       }
HHH
HHT
HTH
HTT		 THH
THT
TTH
TTT

|S| = 8

F, the first of three tosses is a tail, T.

F = {THH, THT, TTH, TTT}

|F| = 4

p(F)

= |F| / |S|

= 4 / 8 = 1/2

E, event that odd number of T in 3 tosses.

E = {HHT, HTH, THH, TTT}

|E| = 4

E | F  = { THH, TTT }              E given F

E ∩ F  =  {HHT, HTH, THH, TTT} ∩ {THH, THT, TTH, TTT} = {THH, TTT}

p( E ∩ F )

= | E ∩ F | / | S |

= 2/8 = 1/4

p( E | F )

= p( E ∩ F ) / p( F )

= 1/4 / 1/2

= 2/1 * 1/4

= 2/4

= 1/2

 

Conditional probability, the probability of E given F

E and F events and p(F) > 0

p( E | F ) = p( E ∩ F ) / p( F )

Question 6.9.3

What is the probability of exactly two 0's below?

{0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111}

 

Example 2

Conditional Probability

  1. random 4-bit string
  2. given first bit is 0
  3. AND contains exactly two 0s

S, 4-bit string

{0000,0001,0011,0100,0101,0110,0111,1000,1001,1011,1100,1101,1110,1111}

|S| = 24 = 16 possible outcomes.

F, first bit is 0.

F = {0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111}

|F| = 8

p(F) = |F| / |S|

       = 8 / 16 = 1/2

E, exactly two 0s.

E =  {1100, 1010, 1001, 0101, 0011, 0110}

E ∩ F = { 0011, 0101, 0110 }

p( E ∩ F ) = | E ∩ F | / | S |

        = 3 / 16

p( E | F )

= p( E ∩ F ) / p( F )

= 3/16 / 1/2

= 2/1 * 3/16

= 6 / 16

= 3 / 8

 

Conditional probability, the probability of E given F

E and F events and p(F) > 0

p( E | F ) = p( E ∩ F ) / p( F )

Example 3

Conditional Probability

  1. coin is flipped five times
  2. given the first flip is heads
  3. AND exactly four heads appear?

S, coin flipped five times, 25 = 32 possible outcomes.

|S| = 32

F, given the first flip is heads, H.

|F| = 24 = 16

p(F) = |F| / |S| = 16/32 = 1/2

E, exactly four heads appear in 5 tosses.

E = {HHHHT, HHHTH, HHTHH, HTHHH, THHHH}

|E| = C(5,4) = 5

E ∩ F = {HHHHT, HHHTH, HHTHH, HTHHH}

p( E ∩ F )

= |E ∩ F| / |S|

= 4/32 = 1/8

p( E | F )

= p( E ∩ F ) / p( F )

= 1/8 / 1/2 = 2/8 = 1/4

 

Question 6.10.1

What is the probability of one B?

{BG, GB, GG, BB}

Question 6.10.2

Conditional probability:

  1. a family planning 3 children
  2. their first child is a boy
  3. probability they will have exactly 2 boys?

S = {BBB, BBG, BGB, BGG, GBB, GBG, GGB, GGG}

|S| =

F =                                              first child is a boy

|F| =

p(F) =

E =                                              has 2 boys

|E| =

E ∩ F =                                        has 2 boys AND first child is a boy

|E ∩ F| =

p( E ∩ F ) = |E ∩ F| / |S| =

p( E | F ) = p( E ∩ F ) / p( F ) =

 

Example 4

Conditional probability

  1. random 4-bit string
  2. given first bit is 0
  3. AND contains at least two consecutive 0s

S, random 4-bit string

|S| = 24 = 16 possible outcomes.

F, is first bit is 0.

F = {0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111}

|F| = 24 = 8

p(F) = |F| / |S| = 8/16 = 1/2

E, contain at least two consecutive 0s.

E1 = { 0010, 0100, 0011, 1001, 1100}        5 ways with 2 consecutive 0s AND

E2 = {0001, 1000}                                      2 ways with 3 consecutive 0s AND

E3 = {0000}                                                1 way with 4 consecutive 0s    

E = E1 U E2 U E3 =  {0000, 0001, 0010, 0011, 0100, 1000, 1100, 1001}

E ∩ F = { 0000, 0001, 0010, 0011, 0100 }

p( E ∩ F ) = 5/16

p( E | F )

= p( E ∩ F ) / p( F )

= 5/16 / 1/2 = 5/8

 

Independence

Independent - occurrence of one event does not make it more or less likely that the other event occurs.

Examples - independent

Rolling a 6 on a die the first time and rolling a 6 the second time are independent.

Drawing two cards with replacement from a deck of cards.

Drawing a red card, placing it back in the deck, drawing another red card are independent.

Examples - dependent

Rolling a 6 on a die the first time and getting an 8 as the sum of the numbers on the first and second rolls are dependent.

Drawing two cards without replacement from a deck of cards.

Drawing and keeping a card and drawing another card are dependent.

 

Question 6.11

You just flipped a coin to heads.

What is the probability the next flip is a heads?

Question 6.12

Does knowing that the first coin flip was heads alter the probability of the second flip being a heads?

Is each flip independent or dependent?

Question 6.13

Does knowing that the first flip was heads alter the probability getting 2 heads in two flips?

Is each flip independent or dependent?

 

Conditional probability, the probability of E given F

E and F events and p(F) > 0

p( E | F ) = p( E ∩ F ) / p( F )

Definition 4

Independent events E and F iff

p( E ∩ F ) = p( E ) p( F )

When E and F are independent:

p( E | F ) 

= p( E ∩ F ) / p( F )

=  p( E ) p( F ) /  p( F )

= p( E )

Makes sense because if E and F are independent, F does not affect E.

Example

Spin a fair spinner numbered 1 to 7 twice.

Are they independent?

What is the probability of getting a 2 and 5 of respective spins?

p(2) = 1/7

p(5) = 1/7

p( 2 ∩ 5 ) = p(2) * p(5) = 1/7 * 1/7 = 1/49

Question 6.14.1

Spin a fair spinner numbered 1 to 7, and toss a fair coin.

Are they independent?

What is the probability of spinning an odd number and flipping a head in one attempt of each?

 

Definition 4

Independent events E and F iff

p( E ∩ F ) = p( E ) p( F )

Example 1

In family of two children, is having at least one Girl independent of having two Girls?

The sex of two births has 4 equally likely outcomes

S = {GG, GB, BG, BB}

F at least one is a Girl.

F = {GB, BG, GG}

p(F) = 3/4

E is two Girls.

E = {GG}

p(E) = 1/4

E ∩ F = {GG}

p( E ∩ F ) = 1/4

p( F ) p( E ) = 1/4 * 3/4 = 3/16

p( E ∩ F ) ≠ p( F ) p( E )        Not independent

Independent events E and F iff

p( E ∩ F ) = p( E ) p( F )

p(E|F) = p( E ∩ F ) / p(F) = 1/4 / 3/4 = 1/3 ≠ 1/4 = p(E)

 

Example 2

Are E and F independent?

S, random 4-bit string.

24 = 16 equally likely possible strings.

F is event 4-bit string begins with a 1.

8 strings starting with 1.

p(F) = 8/16 = 1/2

E is event string contains even number of 1s.

8 have even number of 1s, {1001, 1010, 1100, 1111, 0000, 0011, 0101, 0110}

p(E) = 8/16 = 1/2

E ∩ F = {1001, 1010, 1100, 1111}

p( E ∩ F ) = 4/16 = 1/4

p( E ) p( F ) = 1/2 * 1/2 = 1/4

p( E ∩ F ) = p( E ) p( F )        Independent

Independent events E and F iff

p( E ∩ F ) = p( E ) p( F )

p(E|F) = p( E ∩ F ) / p(F) = 1/4 / 1/2 = 1/2 = p(E)

 

Example 3

Are E and F independent?

S, random 4-bit string.

24 = 16 possible outcomes.

F is first bit is 0.

p(F) = 8/16 = 1/2

E is 4-bit string contain at least two consecutive 0s.

8 possible ways {0000, 0001, 0010, 0011, 0100, 1000, 1001, 1100}.

p(E) = 8/16 = 1/2

E ∩ F = { 0000, 0001, 0010, 0011, 0100 }

p( E ∩ F ) = 5/16

p( F )p( E ) = 1/2 * 1/2 = 1/4

p( E ∩ F )≠ p( E ) p( F )                 Not independent

 

Question 6.14.2

Are E and F independent?

  1. random 4-bit string
  2. first bit is 0
  3. contains exactly two 0s

S, random 4-bit string

|S| = 24 = 16 possible outcomes.

F, first bit is 0.

F = {0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111}

|F| = 8

p(F) = 8/16 = 1/2

E, contains exactly two 0s.

E =  {1100, 1010, 1001, 0101, 0011, 0110}

|E| = C(4,2) = 6

p(E) = 6/16 = 3/8

E ∩ F = { 0011, 0101, 0110 }

p( E ∩ F ) = ?

p( E ∩ F )= p( E ) p( F ) = ?

Independent events E and F iff

p( E ∩ F ) = p( E ) p( F )

 

Bernoulli Trials and the Binomial Distribution

Definitions

Bernoulli trial has only two possible outcomes.

If p is probability of one outcome then q is the probability of the other where:

p + q = 1

 

Mutually independent intuitively means that one event occurs independent of another event.

For example, in tossing a coin twice, the first toss results does not influence the second.

Theorem 2

Probability of k successes in n independent Bernoulli trials, with probability success p and failure q = 1-p is

C(n,k) pk qn-k

Example 1

Unbiased coin with a probability for heads, p

p(H) = 1/2

q(T) = 1/2

Assuming 7 tosses are independent, what is the probability of exactly 4 heads?

For any one combination of 7 flips, probability of 4 heads and 3 tails

p4 * q3 = 1/24 * 1/23 = 1/27

or 7 heads, or 1 head and 6 tails, etc. (because p=q=1/2)

|S| = 27 = 128 possible outcomes {HHHHHHH, HHHHHHT, ...}.

|E| = C(7,4) ways 7 flips can have 4 heads (or tails).

For all combinations of 7 flips and 4 heads, probability is:

p(E) = C(7,4) * p4 * q3

        = C(7,4) * 1/24 * 1/23

        = C(7,4) * 1/27

 = 7!/4!3! * 1/128

 =  35 * 1/128 = 35/128

Theorem 2

Probability of k successes in n independent Bernoulli trials, with probability success p and failure q = 1-p is

C(n,k) pk qn-k

Example 2

A coin is biased for, p, Heads with a probability

p(H) = 2/3

q(T) = 1/3

Assuming 7 tosses are mutually independent, what is the probability of exactly 4 heads?

For any one combination of 7 flips, probability of 4 heads and 3 tails is:

(2/3)4 * (1/3)3

|S| = 27 = 128 possible outcomes {HHHHHHH, HHHHHHT, ...}.

|E| = C(7,4) ways 7 flips can have 4 heads (or tails).

pk = p4 = probability of 4 successes (heads) = 2/34

qn-k = q7-4 = q3 = probability of 3 failures (tails) = 1/33

For all combinations of 7 flips producing 4 heads, probability is:

p(E) = C(7,4) * p4 * q3

        = C(7,4) * 2/34 * 1/33

        = 7!/4!3! * 16/81 * 1/27

        =  (35 * 16) / 2187

        = 560/2187

Question 6.14.1

Suppose the probability of having a girl is p=0.6 and and q=0.4 for having a boy.

What is the probability of having 3 girls in a family of 5 children, assuming the sex of each child is independent of the others?

Just set up according to Theorem 2.

Theorem 2

Probability of k successes in n independent Bernoulli trials, with probability success p and failure q = 1-p is

C(n,k) pk qn-k

 

Definition 5

Random variable is a function that assigns a real number to every possible outcome.

Example

Flip a coin 3 times.

t is one of the 23 possible outcomes of flipping a coin 3 times.

t ∈{HHH, HHT, HTH, HTT, THH, THT, TTH, TTT}

X(t) is random variable (i.e. a function of t) that we define here to assign the number of Heads that occur for outcome t.

t

X(t)
HHH X(HHH) = 3
HHT X(HHT) = 2
HTH X(HTH) = 2
THH X(THH) = 2
HTT X(HTT) = 1
TTH X(TTH) = 1
THT X(THT) = 1
TTT X(TTT) = 0

Question 6.15

From table above, what is X(HTH)?

A spinner has numbers 1, 2, and 3.

Spin the spinner two times.

t is one of the 32 possible outcomes.

Define X(t), the random variable for the sum that occur for outcome t?

t

X(t)
1 1 X(1 1) =             
1 2  
1 3  
2 1  
2 2  
2 3  
3 1  
3 2  
3 3  

 

Definition 6

Distribution of a random variable X on sample space S is the set of pairs:

(r, p(X=r)) ∀r ∈ X(S) where p(X=r) is the probability that X takes the value r.

Example - Continued

t is one of the 23 = 8 possible outcomes of flipping a coin 3 times.

X(t), the random variable for the number of heads that occur for outcome t.

Probability is 1/8 for each of the 8 possible outcomes of t, HHH, HHT, ....

t

X(t) = r
HHH X(HHH) = 3
HHT X(HHT) = 2
HTH X(HTH) = 2
THH X(THH) = 2
HTT X(HTT) = 1
TTH X(TTH) = 1
THT X(THT) = 1
TTT X(TTT) = 0

X(t) = r

 X(t) distribution
X(HHH) = 3 p(X=3) = 1/8
X(HHT) = X(HTH) = X(THH) = 2 p(X=2) = 3/8
X(HTT) = X(TTH) = X(THT) = 1 p(X=1) = 3/8
X(TTT) = 0 p(X=0) = 1/8

 

Question 6.16

A spinner has numbers 1, 2, and 3.

Spin the spinner two times.

t is one of the 32 possible outcomes.

X(t), the random variable for the sum that occurs for outcome t.

What is the probability for each of the possible outcomes of t?

Complete X(t) distribution.

t

X(t)
1 1 X(1 1) = 2   
1 2 X(1 2) = 3
1 3 X(1 3) = 4
2 1 X(2 1) = 3
2 2 X(2 2) = 4
2 3 X(2 3) = 5
3 1 X(3 1) = 4
3 2 X(3 2) = 5
3 3 X(3 3) = 6

 

X(t) = r

 X(t) distribution
X(1 1) = 2 p(X=2) = 1/9
X(1 2) = X(2, 1) = 3 p(X=3) = 2/9
   
   
   

 

Example

X is sum of a pair of dice numbers.

X((1,5)) = 6

|S| = 62 = 36 possible outcomes.

Random variable X takes the following values (only one representative pair is listed):

X(t) X(t) distribution
X((1,1)) = 2, there is 1 outcome
X((1,2)) = X((2,1)) = 3, there are 2 outcomes
X((1,3)) = X((3,1)) = X((2,2)) = 4, there are 3 outcomes
X((1,4)) = 5 ... there are 4 outcomes
X((1,5)) = 6 ... there are 5 outcomes
X((1,6)) = 7 ... there are 6 outcomes
X((2,6)) = 8 ... there are 5 outcomes
X((3,6)) = 9 ... there are 4 outcomes
X((4,6)) = X((6,4)) = X((5,5)) = 10 there are 3 outcomes
X((5,6)) = X((6,5)) = 11 there are 2 outcomes
X((6,6)) = 12 there is 1 outcome		 p(X=2) = 1/36
p(X=3) = 2/36
p(X=4) = 3/36
p(X=5) = 4/36
p(X=6) = 5/36
p(X=7) = 6/36
p(X=8) = 5/36
p(X=9) = 4/36
p(X=10) =3/36
p(X=11) = 2/36
p(X=12) = 1/36

Question 6.17

X((1,6)) = X((5,2)) = ?

p(X=7) = ?

What is the probability of tossing a sum of: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 OR 12?

What is the probability of tossing a sum of: 2 OR 12?

What is the probability of tossing a sum of: 2 OR 12 OR 7?

Probability of E is the sum of the probabilities of the outcomes in E.

where E ⊆ S, then p(E) =  

 

Probability of a Collision in Hashing Functions

Definition 3

modulus

a= b mod m

a= b % m

a is the remainder of b divided by m

Question 6.18

  1. a = 17 mod 5 = 17 % 5 =?
  2. a = 103 mod 4 = 103 % 4 = ?

Example

Hashing - under certain conditions, can produce O(1) search.

Hash (or dictionary) function maps a key to some other value.

For example, a dictionary maps an key word to the definition of that word.

Remember Java HashMap?

 

Hash function h(k) maps a key k to m storage locations.

h(k) = k mod m

 

Example

h(k) = k mod 5

h(4) = 4 mod 5 = 4

h(19) = 19 mod 5 = 4

All k values hashed to 5 locations.

h(k) = k mod 5 k
0 0, 5, 10, 15...
1 1, 6, 11, 16...
2 2, 7, 12, 17...
3 3, 8, 13, 18...
4 4, 9, 14, 19...

Question 6.19

h(k) = k mod 5                 Assume k is uniformly distributed.

S = {0, 1, 2, 3, 4}            The locations.

What is h(23)?

∀s ∈ S, p(s) = ?

 

Example

What is the probability that no two hash keys collide (i.e. map to the same integer storage location)?

h(k) = k mod 5

maps all keys to an integer 0-4.

Probability of not colliding with another key:

Free p(Not colliding)
5 5/5
4 4/5
3 3/5
2 2/5
1 1/5

Because the keys are independent (assumed), the probability of all 5 keys mapping to different locations (0 collisions) is:

p5 = 5/5 * 4/5 * 3/5 * 2/5 * 1/5 = 0.0384

 If adding 5 keys, the probability that there is at least one collision is:

1 - p5 = 1 - 0.0384 = 0.9616

Question 6.20

What are some of the implications for a hash table using this method?

 

Monte Carlo Algorithms

Definitions

Deterministic algorithms, given the same inputs, always make the same choices; there is no randomness.

Useful in accounting and other well-defined and understood processes.

Example

Compute your taxes. IRS does not reward random returns.

Nondeterministic algorithms, are probabilistic, making some random choices.

Useful in modeling systems that are not completely understood or difficult to solve deterministically.

Example

Compute the area of the Mona Lisa's face.

To determine the area using Monte Carlo methods:

  1. Determine the area of the frame, lets say 4 square meters.
  2. Randomly throw darts at the picture, lets say 100 darts hit the picture.
  3. Note the number of darts inside the face boundaries, lets say 25.
  4. Can estimate the face area of 25/100 = 1/4 of the frame or 1 square meter total.

Throwing more darts increases the accuracy of the estimate.

 

Decision problems have either true or false answers.

Example

The computer chip is good.

Monte Carlo algorithms, are probabilistic.

For decision problems, asks a series of independent questions, each with a known probability.

Example

Chip manufacturer sometimes tests complete batches and replaces defective chips.

Untested chips known to have failure with 0.1 probability.

1000 processor chips are received by you.

To determine if all 1000 are good requires 1000 tests, or O(n) for n chips.

Want to determine if chips have not been tested already.

Without testing all 1000.

Solution:

Ask question "Has this chip not been tested?" until confident all have been tested.

for i := 1 to k

Remove and test one chip at random.

If a bad chip is found, answer "true" to question "Has this chip not been tested?" and stop.

If a good chip is found, answer "unknown" and continue.

If no "true" answer then the answer is "false" (i.e. conclude all chips have been tested).

Question is what value of k? How many chips to test.

k=1000 tests all chips, which we'd like to avoid.

Probability chip is bad but untested is 0.1

Probability chip is good but untested is 1 - 0.1 = 0.9

Testing different chips is independent.

Probability of testing k chips and getting answer "unknown" is 0.9k

Testing 66 chips has probability of 0.966 = 0.001 the answer is "unknown", the chips were tested by the manufacturer.

Probability of 0.001 (1 in 1000) that the chips were not tested.

Note that because each test is independent, the result is valid for any number of chips in a shipment.

Cost of checking 66 chips is O(66) = O(1)

Cost of checking n chips is O(n)

 

6.3 Bayes' Theorem

Introduction

Often would like to know probability an event occurs based on partial evidence.

Example

Can write a spam identifier program by knowing:

  1. words used in known spam (e.g. Rolex)
  2. percentage of email that is known spam (84% last count)
  3. percentage of spam in which each email word occurs (e.g. Rolex is in 12.5% of spam)
  4. percentage of non-spam in which each email word occurs (e.g. Rolex is in .5% of non-spam)

Bayes' Theorem

Theorem 1

Bayes' Theorem  

E and F events from sample space S

p(E) ≠ 0 and p(F) ≠ 0


p(F | E) =

Example - Probability an email is Spam given it contains "Rolex"

          

Example

What is the probability an email is spam given it contains "Rolex" ?

The probability, can be computed by Bayes' Theorem:

Rolex, email contains "Rolex"

Spam, email is spam.

p(Spam | Rolex), conditional probability of email being spam (Spam) given that it contains "Rolex" (Rolex)

p(Rolex | Spam), conditional probability contains "Rolex" given its Spam

p(Rolex | Spam), conditional probability contains "Rolex" given its NOT Spam

Data

250 of 2000 emails contain "Rolex" given they are Spam

p(Rolex | Spam) = 250/2000 = 0.125

5 of 1000 emails contain "Rolex" given they are not Spam

p(Rolex | Spam) = 5/1000 = 0.005

p(Spam) = 1/2, assuming any email is equally likely to be spam.

p(Spam) = 1/2, probability NOT spam

        = 0.125 / (0.125+0.005) ≈ 0.962

p(Spam | Rolex) ≈ 0.962

Probability email is spam given that it contains "Rolex"

Question 20a

p(Spam | Rolex) ≈ 0.962

What should the spam filter do with an email containing "Rolex"?

Example

Determine probability an email is spam given it contains "stock" and "undervalued".

Stock contains "stock"

Undervalued contains "undervalued"

Data

2000 spam emails

400 contain "stock"

200 contain "undervalued"

1000 non-spam emails

60 contain "stock"

25 contain "undervalued"

Assuming equally likely any email to be Spam.

2000 spam emails

Probability contains "stock"

p( Stock | Spam ) = 400/2000 = 0.2

Probability contains "undervalued"

p( Undervalued | Spam ) = 200/2000 = 0.1

1000 non-spam emails

Probability contains "stock"

p(Stock | Spam ) = 60/1000 = 0.06

Probability contains "undervalued"

p( Undervalued | Spam ) = 25/1000 = 0.025

p(Spam | Stock ∩ Undervalued) ≈ 0.93

probability an email with "stock" and "undervalued" is spam.

 

6.4 Expected Value and Variance

Expected Value

Definition 1

Expected value of random variable X(s) on sample space S is:

Example

What is E(X)?

S = { 1, 2, 3, 4, 5, 6 }

X(s), a random variable that assigns the die number rolled.

s ∈ S, X(s) = {1, 2, 3, 4, 5, 6}

∀s ∈ S, p(s) = 1/6

s X(s) p(s) p(s)*X(s)
1 1 1/6 1/6
2 2 1/6 2/6
3 3 1/6 3/6
4 4 1/6 4/6
5 5 1/6 5/6
6 6 1/6 6/6
Sum 21/6

E(X) = 1/6*1 + 1/6*2 + 1/6*3 + 1/6*4 + 1/6*5 + 1/6*6

        = 1/6(21) = 21/6 = 7/2

7/2 is the expected (average) value when tossing a die.

 

Example

Coin flipped 3 times.

What is E(X)?

S = { HHH, HHT, HTH, HTT, THH, THT, TTH, TTT }

X random variable assigns value of the number of Heads.

s ∈ S, X(s) = {3, 2, 2, 1, 2, 1, 1, 0}

∀s ∈ S, p(s) = 1/8

s X(s) p(s) p(s)*X(s)
HHH 3 1/8 3/8
HHT 2 1/8 2/8
HTH 2 1/8 2/8
HTT 1 1/8 1/8
THH 2 1/8 2/8
THT 1 1/8 1/8
TTH 1 1/8 1/8
TTT 0 1/8 0/8
Sum 12/8

E(X) = 1/8*3 + 1/8*2 + 1/8*2 + 1/8*1 + 1/8*2 + 1/8*1 + 1/8*1 + 1/8*0

        = 12/8 = 3/2

3/2 is expected (average) number of heads in three tosses.

 

Question 6.21

A coin has a 1 and a 2 on opposite sides. Toss 2 times.

S = {(1,1), (1,2), (2,1), (2,2) }

X assigns value of the sum of the tosses.

s ∈ S, X(s) = { 2, ?, ?, ? }

∀s ∈ S, p(s) = { 1/4, ?, ?, ?}

E(X) = ?

s X(s) p(s) p(s)*X(s)
(1,1) 2 1/4 (1/4)*2
       
       
       
Sum  

Example

X is sum of a pair of dice numbers.

62 = 36 possible outcomes.

Random variable X takes the following values:

X(t) X(t) distribution
X((1,1)) = 2 there is 1 outcome
X((1,2)) = X((2,1)) = 3 there are 2 outcomes
X((1,3)) = X((3,1)) =X((2,2)) = 4 there are 3 outcomes
X((1,4)) = 5 ... there are 4 outcomes
X((1,5)) = 6 ... there are 5 outcomes
X((1,6)) = 7 ... there are 6 outcomes
X((2,6)) = 8 ... there are 5 outcomes
X((3,6)) = 9 ... there are 4 outcomes
X((4,6)) = X((6,4)) = X((5,5)) = 10 there are 3 outcomes
X((5,6)) = X((6,5)) = 11 there are 2 outcomes
X((6,6)) = 12 there is 1 outcome		 p(X=2) = 1/36
p(X=3) = 2/36
p(X=4) = 3/36
p(X=5) = 4/36
p(X=6) = 5/36
p(X=7) = 6/36
p(X=8) = 5/36
p(X=9) = 4/36
p(X=10) =3/36
p(X=11) = 2/36
p(X=12) = 1/36

What is E(X)?

S = { (1,1), (1,2), (2,1), ..., (6,6) }

X random variable assigns value of the sum of two dice.

s ∈ S, X(s) = {2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6,
                      7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 11, 11, 12}

p(X=2) = p(X=12) = 1/36
p(X=3) = p(X=11) = 2/36
p(X=4) = p(X=10) = 3/36
p(X=5) = p(X=9)   = 4/36
p(X=6) = p(X=8)   = 5/36
p(X=7) =               = 6/36

∀s ∈ S, p(s) = 1/36

E(X) = 2*1/36 + 3*2/36 + 4*3/36 + 5*4/36 + 6*5/36 +

           7*6/36 + 8*5/36 + 9*4/36 + 10*3/36 + 11*2/36 + 12*1/36

        = 1/36(2+6+12+20+30+42+40+36+30+22+12)

        = 252/36 = 7

 

Theorem 2

The expected number of successes when n independent Bernoulli trials are performed, where p is the probability of success on each trial, is np.

Example

A coin is biased for 3/4 heads.

What is the expected number of heads when a coin is flipped 100 times?

n = 100

p(H) = 3/4

np = 100 * 3/4 = 300/4 = 75

 

Average-Case Computational Complexity

Definition 1

Expected value of random variable X(aj) on all possible algorithm inputs, aj, is the average-case complexity of an algorithm.

Example - linear search

procedure linear search (x: integer, a1, a2, ..., an) Comparisons

i := 1

  

while (i ≤ n and x ≠ ai)

 2n

i := i + 1

  

if i ≤ n then

1

location := i

  

else

 1

location := 0

  

Average case complexity

p is probability x is in list a1, a2, ..., an.

p/n is probability x=ai, the ith element.

q = 1 - p is probability x not in list.

2i+1 is number of comparisons when in list, x=ai, the ith element.

n+1 possible inputs, n numbers in the list and a number not in the list.

E, the expected number of comparisons

E = 3*p/n + 5*p/n + ... + (2n+1)*p/n + (2n+2)q
  = p/n*(3+5+...+(2n+1))  + (2n+2)q
  = p/n*((n+1)2 - 1) + (2n+2)q
  = p(n+2) + (2n+2)q

p=0, x not in list, worst case complexity

2n+2 comparisons when x not in list.

E = 0(n+2) + (2n+2)1 = 2n+2

p=1, x in list

When x in list, would expect to find, on average, in the middle, requiring 1/2 (2n) = n while iterations

E = 1(n+2) + (2n+2)0 = n + 2

p=1/2, x in list

E = 1/2*(n+2) + (2n+2)*1/2 = (n/2+1)+(n+1) = (3n + 4)/2

 

Variance

Expected value is the average value.

The average return on $5 lottery ticket is negative.

Variance is how widely values are distributed.

A lottery ticket is nearly always worth nothing but on rare occasions worth millions. Large variance.

 

Definition 4

Variance of random variable X(s) on sample space S is:

X(s) defined is value of event s

s = HHT

X(s) = 2, number of heads

p(s) is probability of event s

p(HHT) or p(X=2) = C(3,2) / 8 = 3/8

Expected value of random variable X

Definition

Standard deviation of X is:

Theorem 6

Variance of random variable X(s) on sample space S is:

V(X) = E(X2) - E(X)2

Example - Variance of the value of a die

X is die number rolled.

E(X)?

S = { 1, 2, 3, 4, 5, 6 }

s ∈ S, X(s) = {1, 2, 3, 4, 5, 6}

∀s ∈ S, p(s) = 1/6

E(X) = 1/6(1 +2 + 3 + 4 + 5 + 6) = 21/6 = 7/2

E(X2)?

E(X2) = 1/6(12 + 22 + 32 + 42 + 52 + 62) = 91/6

V(X) = E(X2) - E(X)2

 = 91/6 - (7/2)2 = 35/12

E(X), the average value of the die is 3 1/2

V(X), the variance is 35/12 or nearly 3.

 

Example - What is the variance of the number of heads when flipping a fair coin 3 times?

X is the number of heads in 3 tosses.

E(X)?

S = { HHH, HHT, HTH, HTT, THH, THT, TTH, TTT }

∀s ∈ S, p(s) = 1/23 = 1/8

s ∈ S, X(s) = {3, 2, 2, 1, 2, 1, 1, 0}

E(X) = 1/8*(3 + 2 + 2 + 1 + 2 + 1 +1 + 0) = 12/8 = 3/2

E(X2)?

E(X2) = 1/8(32 + 22 + 22 + 12 + 22 + 12 +12 + 02) = 24/8 = 3

V(X) = E(X2) - E(X)2

 = 3 - (3/2)2 = 3 - 9/4 = 3/4

E(X), the average value is 3/2.

V(X), the variance is 3/4.

 

Example - What is the variance on the sum of a pair of fair dice?

X is sum of a pair of dice numbers.

62 = 36 possible outcomes.

Random variable X takes the following values (only one representative pair is listed in some cases):

X(t) X(t) distribution
X((1,1)) = 2 there is 1 outcome
X((1,2)) = X((2,1)) = 3 there are 2 outcomes
X((1,3)) = X((3,1)) =X((2,2)) = 4 there are 3 outcomes
X((1,4)) = 5 ... there are 4 outcomes
X((1,5)) = 6 ... there are 5 outcomes
X((1,6)) = 7 ... there are 6 outcomes
X((2,6)) = 8 ... there are 5 outcomes
X((3,6)) = 9 ... there are 4 outcomes
X((4,6)) = X((6,4)) = X((5,5)) = 10 there are 3 outcomes
X((5,6)) = X((6,5)) = 11 there are 2 outcomes
X((6,6)) = 12 there is 1 outcome		 p(X=2) = 1/36
p(X=3) = 2/36
p(X=4) = 3/36
p(X=5) = 4/36
p(X=6) = 5/36
p(X=7) = 6/36
p(X=8) = 5/36
p(X=9) = 4/36
p(X=10) =3/36
p(X=11) = 2/36
p(X=12) = 1/36

E(X)?

S = { (1,1), (1,2), (2,1), (1,3), (3,1), (2,2), ..., (5,6), (6,5), (6,6) }

∀s ∈ S, p(s) = 1/62 = 1/36

s ∈ S, X(s) = {2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6,
                      7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 11, 11, 12}

E(X) =(2+3*2+4*3+5*4+6*5+7*6+8*5+9*4+10*3+11*2+12)/36 = 252/36 = 7

E(X2)?

E(X2) =(22+32*2+42*3+52*4+62*5+72*6+82*5+92*4+102*3+112*2+122)/36

          = (4+9*2+16*3+25*4+36*5+49*6+64*5+81*4+100*3+121*2+144)/36

          = 1974/36

V(X) = E(X2) - E(X)2

 = 1974/36 - 72 = 54 - 49 = 5

E(X), the average value is 7

V(X), the variance is 5

Note that 7+5 = 12

               7-5 = 2

 

Question 6.22

A coin has a 1 and a 2 on opposite sides. Toss 2 times.

S = {(1,1), (1,2), (2,1), (2,2)}

X assigns value of the sum of the tosses.

s ∈ S, X(s) = {2, 3, 3, 4}

∀s ∈ S, p(s) = {1/4, 1/4, 1/4, 1/4}

s X(s) p(s) p(s)*X(s)
(1,1) 2 1/4 (1/4)*2 = 2/4
(1,2) 3 1/4 (1/4)*3 = 3/4
(2,1) 3 1/4 (1/4)*3 = 3/4
(2,2) 4 1/4 (1/4)*4 = 4/4
Sum 12/4

E(X) = ?

E(X2) = ?

V(X) = E(X2) - E(X)2 = ?

 

Theorem 6

Variance of random variable X(s) on sample space S is:

V(X) = E(X2) - E(X)2