Transcript Document

Expectations, Permutations &
Combinations
Krishna.V.Palem
Kenneth and Audrey Kennedy Professor of Computing
Department of Computer Science, Rice University
1
Contents
 In-class exercise on Expectations
 Law of Large Numbers
 Fairness
 Permutations and Combinations
 In-class exercise
2
In-class Exercise: Application of
Expectation
Consider the simple board without any snakes or ladders
7
8
9
6
5
4
1
2
3
Question: Calculate the expected number of rolls to reach or cross 9 from 5
3
Solution
Consider the following
Denote expected number of rolls to reach 9 from square i as E(i)
Therefore E(8) = 1
Because once you are at square 8 then independent of the outcome
of the die the game is complete in one roll
Consider you are at square 7 and we have to calculate E(7)
7
1/6
8
5/6
1
4
9
If you are in square 7, there is a 1/6 chance that
you end up in square 8 (from which it will take E(8)
rolls to complete the game)
But there is a 5/6 chance that you complete the game
in one roll from square 7
7
1/6
8
5/6
1
That means E(7) = probability(roll from 7 ->9) * number of rolls
+ [probability(roll from 7 ->8)
* probability(roll from 8->9)]*number of rolls
(can also be obtained from the transition diagram)
Hence, E(7)
= (5/6) * (1)+ [(1/6)* 1]*(2) = 7/6
9
1/6
1/6
Using a similar technique, we can compute that
Expected
Number of
Rolls
5
E(6)
49/36
E(5)
343/216
6
7
1/6
5/6
8
4/6
1
9
Transition graph for E(6)
The one with a snake
Question: Calculate the expected number of rolls to reach or cross 9 from 5 with a snake present
6
Transition Diagram for snake
1/6
1/6
5
1/6
1/6
1/6
7
6
3/6
8
4/6
1
9
7
1
Complete solution will be posted online
Calculating expected number of rolls
Step 1
So in this case, also because square 8 will lead to the completion of game no matter what
E(8) = 1
Step 2
But because of the snake, when you land on square 7 you automatically move to square 5
Therefore E(7) = E(5)
Step 3
Let us see for square 6. Use the previous methodology
From the transition diagram,
E(6) = (1/6)*(E(7)+1) + [1/6*1](2) + (4/6)*(1)
But we know E(7) =E(5),
E(6) = (1/6)*E(5) + (7/6)
8
Calculating expected number of rolls
Let us write the equation for E(5)
From the transition diagram,
E(5) = (1/6)*(E(6)+1) + (1/6)*(E(7)+1) + (1/6)*(E(8)+1) + 3/6
= (1/6)*( (1/6)*E(5) + 7/6 ) + (1/6)*(E(5) + 1) + 5/6
Rearranging some terms,
E(5) * [ 1 – 1/36 – 1/6 ] = 7/36 + 1 = 43/36
Therefore, E(5) = 43/29
9
Contents
 In-class exercise on Expectations
 Law of Large Numbers
 Fairness
 Permutations and Combinations
 In-class exercise
10
Law of Large Numbers
 The law of large numbers (LLN) describes the long-term
stability of the mean of a random variable.
 Given a random variable with a finite expected value, if its
values are repeatedly sampled, as the number of these
observations increases, their mean will tend to approach and
stay close to the expected value
 for example, consider the coin toss experiment. The frequency of heads (or
tails) will approach 50% over a large number of trials.
 Mathematically, as an example, it can be represented as,
if Mean is
11
, then
In-Class Exercise
 Let us perform the virtual coin toss experiment given at
http://nlvm.usu.edu/en/nav/frames_asid_305_g_3_t_5.html
 Let ‘x’ be the random variable denoting the number of heads
in a coin toss
 x=1 if result is head and x=0 if result is tails
 Observe the value of ‘x’ for n=10, 20, 50, 100, 500, 1000,
using the virtual coin toss
 For each ‘n’, compute the difference between x that is
observed and its expected value x (µ = np).
What do you observe as the value of ‘n’ increases?
12
Number of HEADs and TAILs
10000
Heads
Tails
Magnitude of Outcomes
1000
100
10
1
5
10
20
50
100
500
1000
2000
Number of Trials
What do you observe as the number of trials grows large ?
13
5000
9999
Relative Frequencies of Heads and Tails
Heads
Tails
0.65
0.6
Ideal
Relative Frequency
0.55
0.5
0.45
0.4
0.35
0.3
5
10
20
50
100
500
1000
2000
5000
9999
Number of Trials
Can you observe that as the number of trials grows “large” the result of the experiment
tends to agree with the ideal case ?
14
Contents
 In-class exercise on Expectations
 Law of Large Numbers
 Fairness
 Permutations and Combinations
 In-class exercise
15
Fairness
When do we say that an event is fair ?
Consider the event space
Event 1
When all the events in the space are equally likely ?
Event 2
Event 3
Event 4
By this interpretation, are all horse races unfair in
horse racing?
Because usually one horse is more likely to win
the race than the other.
So the question is, for a game which has unequal probabilities for different
Events, what has to be done to make it fair ?
16
Any Ideas !!
Fairness (Contd.)
So to make the horse racing fair we allocate different odds for
each horse.
This means that the horse which is more likely to win will give you the least amount in return.
This is because it was the option with the least risk
Therefore the method through which a game that is biased is made fair is by using “risk”.
17
Now no matter which horse a gambler bets, he/she will be on an equal footing with respect
to others.
Fairness (Contd.)
But what did we do here ?
We did not make the events equally likely
We made the returns or “the expectations” of all the gamblers equal.
Thus making the game fair
“A experiment is fair if the expectations of all the outcomes are equal”
18
Consider the following game
Outcome of the
toss
Probability of the
outcome
Earnings for the
player who bets on
it
HEAD
½
2 chips
TAIL
½
2 chips
According to the previous definition, the above game is fair to both the players
Now consider the following game
Outcome of the
toss
Probability of the
outcome
HEAD
2/3
TAIL
1/3
Earnings for the
player who bets on
it
Calculate the earnings for the outcomes that will make this game fair.
19
Essentially what we want is that,
The expected earning of HEAD = The expected earning of TAIL
Prob(HEAD) * Earning (HEAD) = Prob(TAIL) * Earning(TAIL)
This implies,
Earning(HEAD) : Earning(TAIL) = Prob(TAIL):Prob(HEAD)
In this example,
Earning(HEAD) : Earning(TAIL) = 1:2
Therefore to make the game fair, we have to make the earnings in the inverse ratio of the
probabilities
20
Now consider the following game
Outcome of the die
Probability of the
outcome
Earnings for the
player who bets on
it
1
p1
X1
2
p2
X2
3
p3
X3
4
p4
X4
5
p5
X5
6
p6
X6
Can you state the criteria to make the above game fair to all the players ?
21
There have been many instances when unfairness in a chance-based game was exploited to
destroy kingdoms.
This is the basis for the oldest epic story in the world. It is called Mahabharatha which was written
in India.
The Epic of Mahabharata
• Mahabharat is an important part of Hindu mythology
It is pivoted on a gambling game between the Kaurava and Pandava clans of
the royal family for the throne of Hastinapura kingdom
Kauravas challenge the honest Pandavas to a dice
game with a loaded dice in their favor.
In this unfair game played, the Pandavas lose their
entire kingdom, were humiliated and banished into22
exile for 13 years.
22
22
The Epic of Mahabharata
• Mahabharat is an important part of Hindu mythology
• longest epic in the world
It is pivoted on a gambling game between the Kaurava and Pandava clans of
the royal family for the throne of Hastinapura kingdom
Kauravas challenge the honest Pandavas to a dice
game with a loaded dice in their favor.
23
23
They return after the exile for revenge and
23
win back their lost kingdom at the epic
battle of Kurushetra
Contents
 In-class exercise on Expectations
 Law of Large Numbers
 Fairness
 Permutations and Combinations
 In-class exercise
24
Factorial
 Factorial of a non-negative integer n, denoted by n!, is the
product of all positive integers less than or equal to n.
 For example,
 Note that
25
Permutations & Combinations
 Permutation: An arrangement of elements from a set such that each
element occurs atmost once, but not all elements of the given set need to
be used
 order of arrangement of elements is important
 It is denoted by the formula
where n is total number of elements in the set and r is the number of elements to be arranged
 Combination: An un-ordered collection of distinct elements from a given
set.
 order of arrangements of elements is not important
 It is denoted by the formula
where n is total number of elements in the set and k is the number of elements to be selected
26
Example-1
 Question: There are 6 students to be seated on a row of 6
desks. How many ways can they be arranged if we don’t care
about seating orders?
Solution:
 Lets take one student. He/she can sit on any of the 6 desks
 Therefore he has 6 ways of sitting down, leaving 5 seats available for the next




27
person.
The next student has 5 places to sit down, given first student has already taken a
seat.
Therefore first and second student have 6x5 ways of sitting.
Next we have third student.
He/she has 4 ways of sitting down given first and second students have already
taken 2 out of 6 desk.
Example-1
 So the first 3 students have 6x5x4 ways of sitting down.
 This can be extended till we have the last student.
 If 5 students have taken 5 desks, the 6th student has no choice
but to take the last available desk. So he has 1 way of sitting
given first 5 students have taken a desk each.
 Total number of arrangements = 6x5x4x3x2x1 = 6!
28
Example-2
 Question: Using the same principle, how many different 6
letter words can you make with “potato”.
 Note: It does not need to make sense.
 For example, “otatop” is also acceptable though there is no such
word



29

Solution:
Let us restate this problem
Think of each letter as a student trying to sit at a desk. Let
the students be called as p1,o2,t3,a4,t5,o6
This is like seating the 6 students on 6 desks but its not
EXACTLY the same problem.
Can you guess why?
Example-2
 Let us take the following arrangement of students
 p1,o2,t3,a4,t5,o6 , p1,o6,t5,a4,t3,o2 , p1,o6,t3,a4,t5,o2 ,p1,o2,t5,a4,t3,o6
 Here student o2 o6 t3 t5 have taken different unique positions but
the word is still the same “potato”.
 So the number of unique words is not just 6!
 Do you know what the solution is?
 Solution: 6!/(2 x 2)
 Explanation: Let us assume that all letters are unique.
 Then, it is the same approach as finding the number of ways of
seating 6 students at 6 desks
 Number of unique words would be 6!
30
 But we know the 2 o’s and 2 t’s are not unique.
Example-2
 For every unique word, we can get 2 unique student patterns
by just interchanging the the o’s.
 Example: p1,o2,t3,a4,t5,o6 , p1,o6,t5,a4,t3,o2
 So there are 2 copies of every unique word in 6! Combinations
because of the o’s.
 Similarly for every word, we can get 2 unique student
patterns by just interchanging the t’s.
 p1,o2,t3,a4,t5,o6 , p1,o6,t5,a4,t3,o2
 So there are 2 copies of every unique word in 6! Combinations
because of the o’s.
31
 Therefore, the number of unique words is
 6! / (No of copies due to letter o)x(No of copies due to letter t)
 Solution: 6! / (2x2)
32
Contents
 In-class exercise on Expectations
 Law of Large Numbers
 Fairness
 Permutations and Combinations
 In-class exercise
33
In-class Exercise
 Card Terminology:
 face value – same number cards (2-10, J, Q, K, A)
 has 4 cards of same face value
 suite – set of cards with same symbol
 four suites – diamond, heart, spade, clubs
 each suite has 13 cards
 Q) In a standard deck of cards, compute the number of ways
you can deal each of the following five-card hands in poker.
 1. Total number of different possible hands (five cards in a hand)
 2. Number of distinct Flush (all 5 cards have the same suite)
 3. Number of distinct Four of a kind (4 same face value cards)
 A) 1. C (52,5)
2. C (13,5) * C (4,1)
34
3. C (13,1) * C (48,1)
Use of Combinations to Calculate Probabilities
 Q) Now, compute the probability of getting a flush in a five-
card poker game?
Probability
 A)
No. of favorable events
of outcome
Total no. of events
 Number of favorable events = C (13,5) * C (4,1)
 Total no. of events = C (52,5)
 Hence, Probability = C (13,5) * C (4, 1)/ C ( 52,5)
35
END
36
Take Home - II
1. Let us go back to the Monty Hall Problem. Let us redefine
the problem.
Suppose you're on a game show, and you're given the choice of three doors:
Behind one door is a car; behind the others, goats.
You pick a door, say No. 1, and the host, who knows what's behind the doors,
opens another door, say Number 3, which has a goat. He then says to you,
"Do you want to pick door Number 2?"
We know its advantageous to switch (based on lecture 3), so we will switch
to 2
Question: Can you prove the same result i.e. “Switching in the problem of
Monty hall is advantageous when compared to not switching” using Bayes
Theorem?
Generalizing the sum of
expectations result
2. Prove that the expectation of sum of n random variables is
equal to the sum of expectation of the n random variables.
 Let x1, x2, x3…. xn be n random variables
 Let z = x1 + x2 + x3…. + xn
n
To prove
E ( z )   E ( xi )
i 1