Transcript 8 - Rice University

Expectations
Krishna.V.Palem
Kenneth and Audrey Kennedy Professor of Computing
Department of Computer Science, Rice University
1
Contents
 Discussion of tutorial solutions
 Expectations & In-class exercise
 Sum of Expectations
 In-class exercise
 Project Discussion
2
Discussion of tutorial solutions
3
Contents
 Discussion of tutorial solutions
 Expectations & In-class exercise
 Sum of Expectations
 In-class exercise
 Project Discussion
4
In-class exercise -1
 Let us change gears and move to a new topic
 Consider the following exercise
 Divide yourselves into teams of 2 and each person (A & B) gets
equal number of chips, say 30
 Each group will be given a coin to toss
 If you get a head, person A gets 2 chips from person B
 If you get a tail, person B gets 2 chips from person A
 After 20 rounds, how many more chips do you think each of
you will earn (i.e. number of extra chips than the given 30
chips)?
 Let us test it out for ourselves.
5
Maintain the record of your game in the following way
Play this game for 20 rounds
Toss
Outcome
Number of
chips each
player has
1
2
3
Observe these numbers
4
5
.
.
.
19
20
6
Can you now take a guess
of your earnings after 50,100
or 1000 turns?
Can you now take a guess
of your earnings after 50
turns, 100 turns, 1000 turns ?
Answering this question is very important to get
an idea of how much you are going to earn.
Let us use probability
i
p
HEAD=0
½
TAIL=1
½
First let us calculate the earnings each player can expect in one turn
So a player has ½ chance of earning 2 chips
He has ½ chance of losing 2 chips
So we can expect to earn (½ * 2)- (½ * 2) = 0 more chip at the end of every turn on an average
7
Very important
Let us see another example
This time we will consider another randomizing device – our friendly die
Maintain a similar record till 20 throws in the following format
Earnings
Outcome
Earning
1
3
2
3
1
3
2
2
4
2
3
5
1
4
6
1
5
Throw
6
7
8
9
8
10
Outcome
Number of
chips till that
point
We again visit the same question.
Can you now take a guess
of your earnings after 20
turns, 50 turns, 100 turns ?
This time we know that the probability function of a die can be represented as
i
p(i)
1
1/6
2
1/6
3
1/6
4
1/6
5
1/6
6
1/6
There is a 1/6th chance of winning 3 chips
There is a 1/6th chance of winning 3 chips
There is a 1/6th chance of winning 2 chips
There is a 1/6th chance of winning 2 chip
There is a 1/6th chance of winning 1 chip
There is a 1/6th chance of winning 1 chip
On an average we can expect (1/6)*3 + (1/6)*3 + (1/6)*2 + (1/6)*2+ (1/6)*1 + (1/6)*1
= 2 chips every throw
9
What does this mean ?
What do we mean when we say that the earning per game is 2 chips?
To understand this, let us first consider the following question.
Consider an unbiased coin toss.
The probability of obtaining a HEAD = ½
But for n trials of the experiment do we always get n/2 HEADs and n/2 TAILs ?
Consider the following experiment:
Toss a coin 5, 10, 50, 100, 500, 1000 … 10000 times.
At each point collect the data regarding number of HEADs and number of TAILs.
Now let us analyze data obtained from one such experiment.
10
Number of HEADs and TAILs
10000
Heads
Tails
Magnitude of Winnings
1000
100
10
1
5
10
20
50
100
500
1000
2000
5000
Number of Trials
What do you observe as the number of trials grows large ?
11
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 ?
12
What do we mean when we say that the earning per game is 2 chips?
That does not seem right!!
To understand this, let us first consider the following question.
Consider an unbiased coin toss.
The probability of obtaining a HEAD = ½
But for n trials of the experiment do we always get n/2 HEADs and n/2 TAILs ?
Consider the following experiment:
Toss a coin 5, 10, 50, 100, 500 … 9999 times.
At each point collect the data regarding number of HEADs and number of TAILs.
Conclusion
It means that as the number of trials(n) grows “large” then it can be expected that
the earnings will be equal to 2* n
13
Expectation
Consider the following table
14
Event
Random
variable
(x)
Earning
e(x)
Probability
P(x)
Event 1
x=1
3
1/6
Event 2
x=2
3
1/6
Event 3
x=3
2
1/6
Event 4
x=4
2
1/6
Event 5
x=5
1
1/6
Event 6
x=6
1
1/6
We can also define the earnings for each roll
(or event) as a function of the random variable.
So let us calculate the
Expected earning OR
Average earning per Event (E)
It can be written according to the
previous intuition as
e(1)*P(1) + e(2)*P(2) + … e(6)*P(6)
=(3+3+2+2+1+1)*1/6 = 2
Expectation
Precise mathematical definition of expectation
For a given experiment, there is an event space that is defined.
A random variable x is defined which takes a distinct value for each event in the event space.
A function f can be defined on the event space and thus on the random variable x
The expected value of f is defined as
n
E ( x)   f ( x  i )  P( x  i )
i 1
Where i is the number of events
In-class exercise 2: Expectation
Using the definition of expectation, solve the following problem
An American roulette wheel has 38 places where the ball may land, all equally likely.
A winning bet on a single number pays 35-to-1, meaning that the original stake is not lost,
and 35 times that amount is won, so you receive 36 times what you've bet.
This means that if you bet $1 on a specific one of the 38 places
(i) If you lose, you lose the amount you bet
(ii) If you win, you win 35 times the bet amount plus you keep you keep the amount you bet
Question:
1. What is the expected amount of money you will be left with after each game? (Assume $1 bets)
A) -$0.0263
Contents
 Discussion of tutorial solutions
 Expectations & In-class exercise
 Sum of Expectations
 In-class exercise
 Project Discussion
17
Expectation of a sum
 Till now we have been referring to the expectation of a single
quantity
 Suppose we need to evaluate the expected value of the sum of two
dice throws
 Consider the following exercise
 Each person will get a pair of dice, say die 1 and die 2
 The first round
 Each player rolls each die separately 20 times and calculates the expected
value of each individual dice
 The second round
 Each player rolls both the dice at once 20 times and calculates the expected
value of the total
 Simplifying assumption: Use 1/6th as the probability for each
outcome of the die
18
Expectation of a sum
 Let us first try to evaluate mathematically what the expected
value of the sum might be.
Recall the basic formula for expectation
The expected value of f is defined as
n
E ( x)   f ( x  i )  P( x  i )
i 1
19
Where i is the number of events
Analysis of data
Let us check if the mathematical derivation is in fact correct
Roll
Die 1 outcome
Die 2 outcome
1
2
..
Calculate the expected outcome of each die from the above data
Roll
Die 1 + Die 2
1
2
..
20
Calculate the expected value of the outcome of both the dice together
Joint Probability
 Recall that we studied about joint or composite events
 For example, a roll of a die is a single event
 But roll of two dice simultaneously is a joint or composite event
consisting of two simple events
 The probability of such an event can be expressed a joint
probability function as follows :
 Consider the roll of two dice where
 x : Random variable that denotes the outcome of the first die
 y : Random variable that denotes the outcome of the second die
 then
 Probability that x = i and y=j is denoted as p(x=i,y=j)
 In fact in this case p(x=i,y=j) = p(x=i) * p(y=j)
Here p(x=i,y=j) is called the joint probability of the two random variables x and y
21
Let us define the following variables
x : Random variable that denotes the outcome of the first die
y : Random variable that denotes the outcome of the second die
z : Random variable that denotes the outcome of the sum of both the dice
Therefore we can say that
z = x+y
Using the formula for calculating expectation of z
E ( z )  E ( x  y )   k  p( z  k ) 
kz
 (i  j )  p( x  i, y  j )
k i  jz
Cover all possible
combinations of x and y
  (i  j )  p ( x  i, y  j )
ix j y
22
  (i  j )  p ( x  i, y  j )
ix j y
Joint probability in this
case is the product of the two
probabilities
  (i  j )  p( x  i )  p( y  j )
ix j y
Rearranging some terms
  (i  p ( y  j ))  ( j  p ( y  j ))  p ( x  i )
ix j y
Rearranging some terms


   i  p ( y  j )   j  p ( y  j )   p ( x  i )
ix  jy
jy



  i   p( y  j )  E ( y)  p( x  i)
ix 
jy

23
Substitute the formula for
expectation with E(Y)


  i   p( y  j )  E ( y)  p( x  i)
ix 
jy

Sum of probabilities is equal to 1
  i  E ( y) p( x  i)
ix
Expanding the product inside the summation
  i  p( x  i)   E ( y)  p( x  i)
ix
ix
Substitute formula for expectation of X
 E ( x)  E ( y )   p ( x  i )
ix
 E ( x)  E ( y )
Sum of probabilities is equal to 1
E ( z )  E ( x  y )  E ( x)  E ( y )
24
Is a very important result
Lessons Learnt
 How can you relate the expectations of individual dice and the
total ?
 The expectation of the total is the sum of the individual expectations
 How do you mathematically prove it ?
 Use the formula for expectation
 Because it is a linear summation,
The expectation of a sum is equal to the sum of expectation
 But what are the conditions when this statement holds ?
 This statement holds under all conditions
 That means that this law can be applied on any set of random variables
25
Generalizing the result
 Prove that the expectation of sum of n random variables is
equal to the sum of expectation of the n random variables.
 That is prove the following
 Let X1, X2, X3…. Xn be n random variables
 Let Z = X1 + X2 + X3…. + Xn
n
To prove: E ( Z )   E ( X i )
i 1
26
Contents
 Discussion of tutorial solutions
 Expectations & In-class exercise
 Sum of Expectations
 In-class exercise
 Project Discussion
27
Field Goal Percentage vs. Free Throw Percentage
A case study of applied probability on sports
By Yung-Seok Kevin Choi
 It is advantageous to quantify different aspects of a game to strategize
 In basketball two of the primary statistics are
 Field Goal Percentage
ratio of field goals achieved to field goals attempted
 Free Throw Percentage
 ratio of free throws achieved to free throws attempted

Problem Statement: In basketball, is field goal percentage related to free throw percentage and how does
this relationship differ between positions?
 Solution
 Collect the data from a basketball reference website
 MATLAB to analyze and parse data
 The data was organized into different bins
 MATLAB to compute conditional probabilities such as
 Made statements such as
 “given a guard’s free throw percentage in bin 6, we are 85 percent confident that his field
goal percentage falls between bins 6 and 11.”
Impartiality in Mafia
By Jose Luis Garcia

There is an interactive social game called Mafia
 The basic idea of the game is that there are two groups (Townspeople and Mafia) with each having different
advantages who attempt to use these strengths in order to incapacitate the rival group and thus win the
game.
 Is it the case that one of the two groups has more chance of winning than the other
 Specific Analysis
 What is the probability of being assigned to either mafia or townspeople?
 How many turns on average does it take to finish a game?
 Is there a group favored to win and if so which group?
 How is the win/loss probability related to the number of players?
Problem Statement: Analyze the impartiality of an interactive social game called Mafia

Solution
 Mathematical model of the game
 Define the variables (number of players, win probability etc.)
 MATLAB script to run multiple trials of the game
 Based on the ratio of townspeople to the mafia
 Define the probability of winning of the townspeople
 A card is chosen at random from a given stack (MATLAB script)
 Compute winning and losing probabilities based on multiple trials

One such Conclusion
 As the number of players is increased the probability of Mafia winning is also increased.
Probability in Currency Exchange
By Thomas Roinesdal
 The values of international currencies fluctuate every day
 Data about trading between among different currencies is available
 It will be very advantageous if one can predict the future value of the exchange rate of a currency based on
the historical trends.
Problem Statement: Is it possible to predict a currency given the historical values of other currencies?
 Solution
 Model
 Consider pairs of currencies
Example: 1 US dollar = 1.4 Singapore dollar
 Collect historical data of trends in the exchange rate
 Compute the relative frequency of different exchange rates
 Calculate conditional probabilities based on this data by applying Bayes Theorem
 Conclusion
 Based on historical data of many currency exchange rates, there was less than 30% chance of
predicting accurately a future value of a given currency
 But it was shown that some currencies are more correlated than others

END
31